调度(生产过程)
作业车间调度
地铁列车时刻表
算法
批处理
作者
Ji Tian,Qian Wang,Ruyan Fu,Jinjiang Yuan
标识
DOI:10.1016/j.tcs.2016.01.001
摘要
We consider the online scheduling on m unbounded drop-line batch machines with delivery times. Here a drop-line batch machine can process several jobs in a batch so that the processing time of a batch is equal to the longest processing time of the jobs in the batch, the jobs in a batch have the same starting time, and the completion time of a job is equal to the sum of its starting time and its processing time. Once the processing of a job is completed on the machine, we immediately deliver it to the destination. The objective is to minimize the time by which all jobs have been delivered. For this problem, we present a best possible online algorithm with a competitive ratio of 1 + α m , where α m is the positive root of the equation α 2 + m α - 1 = 0 . Unbounded drop-line batch scheduling.Minimizing the maximum delivery completion time.Best possible online algorithm.
科研通智能强力驱动
Strongly Powered by AbleSci AI