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

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

On-Line Batchwise Workpiece Scheduling with Restriction of Time Interval

Studies the problem of on-line batchwise workpiece scheduling on m identical parallel machines of which the objective is to minimize the makespan,i.e.,the time for finishing the last workpiece in a batch. In such a case all the workpieces arrive in batches and each batch has exactly m workpieces to which the processing time required for each one depends on the time the batch containing it just arrives.It supposes that the processing time be restricted in a time interval.When a batch of workpieces arrives we shall schedule them immediately without interruption though no information is provided for subsequent batches.An on-line heuristic listing algorithm for batchwise workpieces scheduling is thus proposed according to LPT rule by which the workpieces in next batch will be scheduled immediately if all workpieces in a batch have already been scheduled.The worst case was analyzed with the competitive ratio given.