A POSTERIOR COMPETITIVENESS FOR LIST SCHEDULING ALGORITHM ON MACHINES WITH ELIGIBILITY CONSTRAINTS

Hark-Chin Hwang, Soo Y. Chang () and Yushin Hong
Additional contact information
Hark-Chin Hwang: Department of Industrial Engineering, Chosun University, 375 Susuk-Dong, Dong-Gu, Gwangju 501-709, South Korea
Soo Y. Chang: Industrial Engineering Department, Division of Electrical and Computer Engineering, Pohang University of Science and Technology, San 31 Hyoja-Dong, Pohang, Kyungbook 790-784, South Korea
Yushin Hong: Industrial Engineering Department, Division of Electrical and Computer Engineering, Pohang University of Science and Technology, San 31 Hyoja-Dong, Pohang, Kyungbook 790-784, South Korea

Asia-Pacific Journal of Operational Research (APJOR), 2004, vol. 21, issue 01, 117-125

Abstract: We consider the on-line problem of schedulingnindependent jobs onmidentical machines under the machine eligibility constraints, where each job has its own specified subset of machines which are eligible for processing it. We investigate a greedy algorithm LS and prove its posterior competitiveness ratio is$\log_2\frac{4}{\lambda}m-\frac{1}{\lambda}$, where λ is the number of machines eligible for processing the job with the latest completion time.

Keywords: On-line parallel machine scheduling; machine eligibility; competitive ratio (search for similar items in EconPapers)
Date: 2004
References: View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S0217595904000084
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:21:y:2004:i:01:n:s0217595904000084

Ordering information: This journal article can be ordered from

DOI: 10.1142/S0217595904000084

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