An ACO algorithm for makespan minimization in parallel batch machines with non-identical job sizes and incompatible job families

Zhao Hong Jia, Chao Wang, Joseph Y.T. Leung

Research output: Contribution to journalArticlepeer-review

23 Scopus citations

Abstract

We study the problem of scheduling a set of N jobs with non-identical job sizes from F different families on a set of M parallel batch machines; the objective is to minimize the makespan. The problem is known to be NP-hard. A meta-heuristic based on Max-Min Ant System (MMAS) is presented. The performance of the algorithm is compared with several previously studied algorithms by computational experiments. According to our results, the average distance between the solutions found by our proposed algorithm and the lower bounds is about 4% less than that of the best of all the compared algorithms, demonstrating that our algorithm outperforms the previously studied algorithms.

Original languageEnglish (US)
Pages (from-to)395-404
Number of pages10
JournalApplied Soft Computing Journal
Volume38
DOIs
StatePublished - Jan 1 2016

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Incompatible job families
  • Makespan
  • Max-Min Ant System
  • NP-hard
  • Parallel batch machines

Fingerprint

Dive into the research topics of 'An ACO algorithm for makespan minimization in parallel batch machines with non-identical job sizes and incompatible job families'. Together they form a unique fingerprint.

Cite this