OPTIMAL PREEMPTIVE SEMI-ONLINE ALGORITHM FOR SCHEDULING TIGHTLY-GROUPED JOBS ON TWO UNIFORM MACHINES

Yiwei Jiang () and Yong He
Additional contact information
Yiwei Jiang: Faculty of Science, Zhejiang Sci-Tech University, Hangzhou 310018, P. R. China
Yong He: Department of Mathematics and State Key Lab of CAD & CG, Zhejiang University, Hangzhou 310027, P. R. China

Asia-Pacific Journal of Operational Research (APJOR), 2006, vol. 23, issue 01, 77-88

Abstract: In this paper, we consider a semi-online preemptive scheduling problem on two uniform machines, where we assume that all jobs have sizes betweenpandrpfor somep > 0andr ≥ 1. The goal is to maximize the continuous period of time (starting from time zero) when both machines are busy. We present an optimal semi-online algorithm for any combination of the job size ratiorand machine speed ratios.

Keywords: Semi-online; scheduling; uniform machines; preemption; competitive ratio (search for similar items in EconPapers)
Date: 2006
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S0217595906000772
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:23:y:2006:i:01:n:s0217595906000772

Ordering information: This journal article can be ordered from

DOI: 10.1142/S0217595906000772

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