An Improved Online Algorithm for the Online Preemptive Scheduling of Equal-Length Intervals on a Single Machine with Lookahead

Wenjie Li and Jinjiang Yuan ()
Additional contact information
Wenjie Li: School of Mathematical Sciences, Luoyang Normal University, Luoyang, Henan 471022, P. R. China†School of Mathematics and Statistics, Zhengzhou University, Zhengzhou, Henan 450001, P. R. China
Jinjiang Yuan: #x2020;School of Mathematics and Statistics, Zhengzhou University, Zhengzhou, Henan 450001, P. R. China

Asia-Pacific Journal of Operational Research (APJOR), 2015, vol. 32, issue 06, 1-9

Abstract: This paper studies the online preemptive scheduling of equal-length intervals on a single machine with lookahead. Let p be the length (processing time) of all intervals. In the problem, at every time point t, online algorithms can foresee all the intervals that will arrive in the time segment (t,t + L) for a certain L. When L = p, Zheng et al. [Comput- ers & Operations Research, 2013] established a lower bound of 2 and provided an online algorithm with a competitive ratio of 3. In this paper, we provide for this problem an improved online algorithm with a competitive ratio of 2.

Keywords: Scheduling; online algorithm; equal-length intervals; lookahead (search for similar items in EconPapers)
Date: 2015
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S0217595915500475
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:32:y:2015:i:06:n:s0217595915500475

Ordering information: This journal article can be ordered from

DOI: 10.1142/S0217595915500475

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 ().