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

Ming Liu, Chengbin Chu, Yinfeng Xu and Feifeng Zheng

European Journal of Operational Research, 2010, vol. 201, issue 3, 693-700

Abstract: 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 .

Keywords: Online; scheduling; Delivery; time; Competitive; analysis; Single; machine (search for similar items in EconPapers)
Date: 2010
References: View complete reference list from CitEc
Citations: View citations in EconPapers (9)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377-2217(09)00201-X
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:201:y:2010:i:3:p:693-700

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().