## 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 language | English (US) |
---|---|

Pages (from-to) | 325-331 |

Number of pages | 7 |

Journal | International Journal of Production Economics |

Volume | 156 |

DOIs | |

State | Published - Oct 2014 |

## All Science Journal Classification (ASJC) codes

- General Business, Management and Accounting
- 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