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

作者：Wang, Jun-Qiang^*; Leung, Joseph Y. -T.

来源：International Journal of Production Economics, 2014, 156: 325-331.

DOI：10.1016/j.ijpe.2014.06.019

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

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.

• 出版日期2014-10
• 单位西北工业大学