工件按加工长度不增序到达的最小化最大流程在线分批排序

Online parallel batching scheduling for nonincreasing-processing-time jobs to minimize the maximum flow-time

研究单处理机工件按加工长度不增顺序到达的在线分批排序问题.工件按时在线到达,目标是最小化最大流程.流程时间是指工件的完工时间与到达时间的差值,它体现了工件在系统内的逗留时间.对于批容量有界的情形,给出了一个竞争比为(?)的最好可能的在线算法;对于批容量无界的情形,给出了一个竞争比为2^(1/2)的最好可能的在线算法.

We consider on-line scheduling on a parallel batching machine where the jobs come with the noninereasing-processing times. In this paper online means that jobs arrive over time. The objective is to minimize the maximum flow time of these jobs. The flow-time of a job means that its completion time minus its arrival time. It reflects the time of the job staying in the system. For the bounded model, we give a best possible algorithm with competitive ratio 1＋√5/2. For the unbounded model, we also give a best possible algorithm with competitive ratio √2.