An improved meta-heuristic for makespan minimization of a single batch machine with non-identical job sizes

Zhao Hong Jia, Joseph Y.T. Leung

Research output: Contribution to journalArticlepeer-review

20 Scopus citations

Abstract

We consider the problem of minimizing the makespan on a single batch machine with non-identical job sizes, where several jobs can be simultaneously processed as a batch. We formulate makespan minimization as a problem of minimizing the wasted space. Applying a candidate set strategy to narrow the search space, combined with a wasted-space-based heuristic to update the pheromone information, an improved max-min ant system algorithm is presented. A specific local search method is incorporated to gain better performance. Appropriate parameter settings in the proposed algorithm are determined by extensive experiments. The experimental results show that the proposed algorithm outperforms several previously studied algorithms.

Original languageEnglish (US)
Pages (from-to)49-58
Number of pages10
JournalComputers and Operations Research
Volume46
DOIs
StatePublished - Jun 2014

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Modeling and Simulation
  • Management Science and Operations Research

Keywords

  • Batch machines
  • Max-min ant system
  • Meta-heuristic
  • NP-hard

Fingerprint Dive into the research topics of 'An improved meta-heuristic for makespan minimization of a single batch machine with non-identical job sizes'. Together they form a unique fingerprint.

Cite this