An optimal online algorithm for single machine scheduling with bounded delivery times

We study an online scheduling problem on a single machine with delivery times. The problem is online in the sense that all jobs arrive over time. Each job’s characteristics, such as processing time and delivery time, become known at its arrival time. Preemption is not allowed and once the processing of a job is completed we delivery it to the destination by a vehicle. The objective is to minimize the time by which all jobs have been delivered. In this paper, we assume that all jobs have bounded delivery times, which means that given a certain positive number β⩾12, for each job JjJj, we have a release time rj⩾0rj⩾0 and βqj⩽pjβqj⩽pj, where pj,qjpj,qj denote the processing time and the delivery time of job JjJj, respectively. We use 1|online,rj,βqj⩽pj|Lmax1|online,rj,βqj⩽pj|Lmax to denote the problem for short, where LmaxLmax denote the time by which all jobs have been delivered. We prove a lower bound of competitive ratios for all online algorithms and propose an optimal online algorithm with a competitive ratio of 125+β2+2β+1-β.