Effective heuristic for makespan minimization in parallel batch machines with non-identical capacities

Zhao Hong Jia, Kai Li, Joseph Y.T. Leung

Research output: Contribution to journalArticlepeer-review

25 Scopus citations

Abstract

We consider the problem of scheduling a set of n jobs with arbitrary job sizes on a set of m parallel batch machines with non-identical capacities; the objective is to minimize the makespan. The problem is known to be NP-hard. A heuristic based on the First-Fit-Decreasing (FFD) rule is presented as well as a meta-heuristic based on Max-Min Ant System (MMAS). The performances of the two heuristics are compared with a previously studied heuristic by computational experiments. The results show that both proposed algorithms outperform the previously studied heuristic. Moreover, the MMAS heuristic obtains better solutions compared with the FFD heuristic.

Original languageEnglish (US)
Pages (from-to)1-10
Number of pages10
JournalInternational Journal of Production Economics
Volume169
DOIs
StatePublished - Nov 1 2015

All Science Journal Classification (ASJC) codes

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

Keywords

  • Heuristic
  • Makespan
  • Max-Min Ant System
  • NP-hard
  • Non-identical machine capacity
  • Parallel batch machines

Fingerprint

Dive into the research topics of 'Effective heuristic for makespan minimization in parallel batch machines with non-identical capacities'. Together they form a unique fingerprint.

Cite this