A Best Possible Deterministic On-Line Algorithm for Minimizing Maximum Delivery Time on a Single Machine

Source abstract

We consider a single-machine on-line scheduling problem where jobs arrive over time. A set of independent jobs has to be scheduled on the machine, where preemption is not allowed and the number of jobs is unknown in advance. Each job becomes available at its release date, which is not known in advance, and its characteristics, i.e., processing requirement and delivery time, become known at its arrival. The objective is to minimize the time by which all jobs have been delivered. We propose and analyze an on-line algorithm based on the following idea: As soon as the machine becomes available for processing, choose an available job with highest priority, and schedule it if its processing requirement is not too large. Otherwise, postpone the start of this job. We prove that our algorithm has performance bound $(\sqrt{5}+1)/2 \approx 1.61803$, and we show that there cannot exist a deterministic on-line algorithm with a better performance ratio for this problem.