Online Single Machine Scheduling to Minimize the Maximum Starting Time

Lingfa Lu and Liqi Zhang ()
Additional contact information
Lingfa Lu: School of Mathematics and Statistics, Zhengzhou University, Zhengzhou, Henan 450001, P. R. China
Liqi Zhang: College of Information and Management Science, Henan Agricultural University, Zhengzhou, Henan 450003, P. R. China

Asia-Pacific Journal of Operational Research (APJOR), 2017, vol. 34, issue 05, 1-9

Abstract: In this paper, we consider the online single machine scheduling problem to minimize the maximum starting time of the jobs. For the non-preemptive model, we show that there is no determined or randomized online algorithm with a bounded competitive ratio. For the preemption-resume model, we show that the well-known SRPT rule yields an optimal schedule. For the preemption-restart model, we show that any determined online algorithm has a competitive ratio of at least 2 and present an online algorithm with the best-possible competitive ratio of 2.

Keywords: Scheduling; restarts; online algorithm; competitive ratio (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S0217595917500221
Access to full text is restricted to subscribers

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:wsi:apjorx:v:34:y:2017:i:05:n:s0217595917500221

Ordering information: This journal article can be ordered from

DOI: 10.1142/S0217595917500221

Access Statistics for this article

Asia-Pacific Journal of Operational Research (APJOR) is currently edited by Gongyun Zhao

More articles in Asia-Pacific Journal of Operational Research (APJOR) from World Scientific Publishing Co. Pte. Ltd.
Bibliographic data for series maintained by Tai Tone Lim ().