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

https://doi.org/10.1016/j.tcs.2007.11.006Get rights and content
Under an Elsevier user license
open archive

Abstract

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, qjpj, 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 2, and the result is the best possible.

Keywords

Scheduling
On-line algorithm
Single machine
Delivery time

Cited by (0)

Research supported by NSFC (10671183) and NFSC-RGC (70731160633).