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 β ≥ frac(1, 2), for each job J_j, we have a release time r_j ≥ 0 and β q_j ≤ p_j, where p_j, q_j denote the processing time and the delivery time of job J_j, respectively. We use 1 | online, r_j, β q_j ≤ p_j | L_max to denote the problem for short, where L_max 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 frac(1, 2) fenced(sqrt(5 + β² + 2 β) + 1 - β).