An on-line algorithm for the single machine unbounded parallel-batching scheduling with large delivery times

We consider the on-line version of the single machine unbounded parallel-batching scheduling with delivery times of jobs. Each jobʼs information, such as processing time pjpj and delivery time qjqj, is not known in advance and becomes known at its arrival time. Once the processing of a job is completed, we deliver it to the destination. Here, the time is continuous. The objective is to minimize the time by which all jobs have been delivered. In this paper, we consider job system with large delivery times, i.e., qj⩾pjqj⩾pj, for each job JjJj. We provide an on-line algorithm with a competitive ratio (5+1)/2≈1.618 and show that any on-line algorithm has a competitive ratio of at least (3+1)/2≈1.366.

► On-line scheduling on a batch machine with large delivery times is considered. ► Any on-line algorithm for this problem has a competitive ratio of at least 3+12. ► An on-line algorithm with a competitive ratio 5+12 is provided.