A best on-line algorithm for single machine scheduling with small delivery times

We consider a single machine on-line scheduling problem with delivery times. All jobs arrive over time. Each job’s characteristics, such as processing time and delivery time, become known at its arrival time. Once the processing of a job is completed we deliver 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 small delivery times, i.e., for each job Jj, qj≤pj, where pj and qj denote the processing time and the delivery time of Jj, respectively. We provide an on-line algorithm with a competitive ratio of , and the result is the best possible.