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