工件具有区间限制的批在线调度

摘要：

研究同构并行机上的批在线调度问题,目标函数是使最大完成时间(最后一个工件的完成时间makespan)最小.工件以批方式到达且每个批中有m个工件,每个工件的加工时间随其批的到达而给定且限定在某个时间区间上.当一批工件到达时,在对其后批的信息不了解的情况下,要立即对该批中的工件进行调度,调度过程中不允许中断.针对这一问题,给出了一个批在线启发式列表调度算法,在同一批中的工件按LPT规则调度,当一批中的全部工件被调度完后,调度下一批中的工件.对算法的最坏情况进行了分析并给出了算法的竞争率.

关键词：批在线列表调度、竞争率、同构并行机、批工件列、最大完成时间、加工时间

所属期刊栏目：27

分类号：TP301.6(计算技术、计算机技术)

资助基金：国家重点基础研究发展计划973计划70425003;中国科学院资助项目70171030;60274049;高等学校优秀青年教师教学科研奖励计划教育司[2002]383

在线出版日期：2006-08-11（万方平台首次上网日期，不代表论文的发表时间）

页数：共3页

页码：728-730