Scheduling jobs with equal-processing-time on parallel machines with non-identical capacities to minimize makespan

Jun Qiang Wang, Joseph Y.T. Leung

Research output: Contribution to journalArticlepeer-review

26 Scopus citations

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.

Original languageEnglish (US)
Pages (from-to)325-331
Number of pages7
JournalInternational Journal of Production Economics
Volume156
DOIs
StatePublished - Oct 2014

All Science Journal Classification (ASJC) codes

  • Business, Management and Accounting(all)
  • Economics and Econometrics
  • Management Science and Operations Research
  • Industrial and Manufacturing Engineering

Keywords

  • Absolute worst-case ratio
  • Approximation algorithm
  • Asymptotic worst-case ratio
  • Batch machines
  • Makespan
  • NP-hard

Fingerprint Dive into the research topics of 'Scheduling jobs with equal-processing-time on parallel machines with non-identical capacities to minimize makespan'. Together they form a unique fingerprint.

Cite this