Online scheduling on the unbounded drop-line batch machines to minimize the maximum delivery completion time

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.