SEMI-ONLINE MACHINE COVERING

Sheng-Yi Cai ()
Additional contact information
Sheng-Yi Cai: School of Mathematics and Information Science, Wenzhou University, Wenzhou 325035, P. R. China

Asia-Pacific Journal of Operational Research (APJOR), 2007, vol. 24, issue 03, 373-382

Abstract: This paper investigates two different semi-online versions of the machine covering, which is the problem of assigning a set of jobs to a system ofm(m ≥ 3)identical parallel machines so as to maximize the earliest machine completion time. In the first case, we assume that the largest processing times is known in advance. In the second case, we assume that the total processing times of all jobs is known in advance. For each version we propose a semi-online algorithm and investigate its competitive ratio. The competitive ratio of each algorithm is$\frac{1}{m-1}$, which is shown to be the best possible competitive ratio for each semi-online problem.

Keywords: Analysis of algorithm; competitive ratio; semi-online; scheduling; machine covering (search for similar items in EconPapers)
Date: 2007
References: View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S0217595907001255
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:24:y:2007:i:03:n:s0217595907001255

Ordering information: This journal article can be ordered from

DOI: 10.1142/S0217595907001255

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