An Online Scheduling Problem on a Drop-Line Parallel Batch Machine with Delivery Times and Limited Restart

This paper studies online scheduling on an unbounded drop-line parallel batch machine with delivery times and limited restarts. A drop-line parallel batch machine is a system that can process some jobs simultaneously as a batch. Jobs in a batch have the same starting time and the completion time of a job is equal to its starting time plus its processing time. Limited restarts mean that a running batch containing at least one restarted job cannot be restarted again. The objective is to minimize the time by which all jobs have been delivered. We prove that any online algorithm has a competitive ratio of at least 1 + alpha, where alpha(alpha approximate to 0.5188) is the positive solution of the equation x(x + x(2) + x(3) + 1) = 1. We provide a best possible (1 + alpha)-competitive online algorithm for the problem. Furthermore, we study the restricted problem with small delivery times and provide a best possible online algorithm with a competitive ratio of 3/2.