单机上带有可变前瞻区间的分批在线排序问题

Online scheduling on single batch machine with variable lookahead interval

本文研究单台无界平行批处理机上带有可变前瞻区间的在线排序问题。工件按时在线到达,目标是最小化时间表长。在时刻t,在线算法能够预见到(t,t+Δ(t)]内到达工件的信息,这里前瞻区间的长度△(t)=βp;(t)并非定长,其中p;(t)表示在t时刻及之前到达工件的最大加工时长,β∈(0,1)是常数。本文对于工件加工时长的一般情形,给出了当0 <β≤1/6时最好可能的在线算法;对于工件加工时长被限制在一个区间的情形,给出了当0 <β<1时最好可能的在线算法。

This paper investigates the online scheduling on an unbounded parallelbatch machine with variable lookahead interval to minimize makespan.Online means that jobs arrive over time.At any time t,an online algorithm can foresee the information of the jobs arriving in(t,t+Δ(t)],where Δ(t)=βp;(t) is the length of the lookahead interval which is not invariable,p;(t) is the maximum processing time of the jobs arriving at or before t and β∈(0,1) is a constant.On the general case of processing time,we give an online algorithm which is the best possible for 0 <β≤1/6.When the processing times of all jobs are restricted in an interval,we give the best possible online algorithm for 0 <β<1.