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 , for each job Jj, we have a release time rj[greater-or-equal, slanted]0 and [beta]qj[less-than-or-equals, slant]pj, where pj,qj denote the processing time and the delivery time of job Jj, respectively. We use 1online,rj,[beta]qj[less-than-or-equals, slant]pjLmax to denote the problem for short, where Lmax 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 .