SEMI-ON-LINE SCHEDULING PROBLEM FOR MAXIMIZING THE MINIMUM MACHINE COMPLETION TIME ON THREE SPECIAL UNIFORM MACHINES

Run-Zi Luo () and Shi-Jie Sun ()
Additional contact information
Run-Zi Luo: Mathematics Department, Shanghai University, Shanghai 200444, P. R. China
Shi-Jie Sun: Mathematics Department, Shanghai University, Shanghai 200444, P. R. China

Asia-Pacific Journal of Operational Research (APJOR), 2005, vol. 22, issue 02, 229-237

Abstract: In this paper, we investigate a semi-on-line version for a special case of three machinesM1,M2,M3where the processing time of the largest job is known in advance. A speedsi(s1= s2= 1, 1 ≤ s3= s)is associated with machineMi. Our goal is to maximize theCmin— the minimum workload of three machines. We give aCmin3algorithm and prove its competitive ratio is$\max\!\big\{2,\frac{3s+2}{2+s}\big\}$and the algorithm is the best possible for1 ≤ s ≤ 2. We also claim the competitive ratio of algorithmCmin3is tight.

Keywords: Scheduling; semi-on-line; competitive ratio (search for similar items in EconPapers)
Date: 2005
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S0217595905000558
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:22:y:2005:i:02:n:s0217595905000558

Ordering information: This journal article can be ordered from

DOI: 10.1142/S0217595905000558

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