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

The online single machine problem \(1|\text{online },r_j, \beta q_j \leq p_j| L_{\max}\) is studied. Given is a set of jobs \(j=1,\ldots,n\) with processing times \(p_j\), release dates \(r_j\) and delivery times \(q_j\) which are bounded by the processing times (i.e. \(\beta q_j \leq p_j\) for all jobs \(j\) for some constant \(\beta \geq 0.5\)). All these jobs have to be processed on a single machine without preemption such that the time when all jobs are delivered is minimized. The problem is considered in an online version where it is assumed that all characteristics of each job become only known at its release date. After providing the lower bound \(0.5 ( \sqrt{5+\beta^2+2 \beta}+1-\beta)\) for the competitive ratio of any online algorithm, an optimal online algorithm achieving this bound is presented.