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