有界平行批处理机的在线排序问题

Online Scheduling on Bounded Parallel-batch Machines

主要研究的是在线运输排序问题,即研究m台有界平行批处理机上考虑工件运输的在线排序问题.工件按时间在线到达,即一个工件只有在被释放之后才能知道它的一切信息.这些工件首先要在平行批处理机上分批加工,然后加工完成的工件再被一个运输车辆运送给某个顾客.当车辆的容量是充分大的时候,给出一个最好可能的在线算法,其竞争比为(5(1/2)+1)/2;当车辆的容量有限时,给出一个竞争比为(5(1/2)+3)/2的在线算法.

In this paper, we consider the online scheduling problem on mbounded parallel-batch machine with job deliver- y. All jobs arrive over time. The jobs are first processed in batches on one of bounded parallel-batch machines and then the completed jobs are delivered in batches by a vehicle to some customer. When the capacity of the vehicle is infinite, we present a best possible online algorithm with the competitive ratio of （√-＋1）/2. When the capacity of the vehicle is finite, we give an online algorithm with the competitive ratio of （√5＋ 3）/2.