Scheduling jobs with equal-processing-time on parallel machines with non-identical capacities to minimize makespan
Jun-Qiang Wang and
Joseph Y.-T. Leung
International Journal of Production Economics, 2014, vol. 156, issue C, 325-331
Abstract:
We consider the problem of scheduling a set of equal-processing-time jobs with arbitrary job sizes on a set of batch machines with different capacities. A job can only be assigned to a machine whose capacity is not smaller than the size of the job. Our goal is to minimize the schedule length (makespan). We show that there is no polynomial-time approximation algorithm with an absolute worst-case ratio less than 2, unless P=NP. We then give a polynomial-time approximation algorithm with an absolute worst-case ratio exactly 2. Moreover, we give a polynomial-time approximation algorithm with asymptotic worst-case ratio no more than 3/2. Finally, we perform a computational experiment and show that our approximation algorithm performs very well in practice.
Keywords: Batch machines; Makespan; NP-hard; Approximation algorithm; Absolute worst-case ratio; Asymptotic worst-case ratio (search for similar items in EconPapers)
Date: 2014
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (9)
Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0925527314002023
Full text for ScienceDirect subscribers only
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:eee:proeco:v:156:y:2014:i:c:p:325-331
DOI: 10.1016/j.ijpe.2014.06.019
Access Statistics for this article
International Journal of Production Economics is currently edited by Stefan Minner
More articles in International Journal of Production Economics from Elsevier
Bibliographic data for series maintained by Catherine Liu ().