Effective heuristics for makespan minimization in parallel batch machines with non-identical capacities and job release times

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

Research output: Contribution to journalArticlepeer-review

7 Scopus citations

Abstract

We consider the problem of scheduling a set of n jobs with arbitrary job sizes, processing times and release times on a set of m parallel batch machines with non-identical capacities; the objective is to minimize the makespan. We first present an algorithm to compute a lower bound for the optimal makespan. Based on different rules of batching the jobs and assigning the batches to the machines, several heuristics are proposed to solve the problem. The performance of the proposed heuristics is evaluated by computational experiments. The proposed heuristics are compared against the lower bound and against each other. Our results show that the one of the proposed algorithms outperforms all the other heuristics.

Original languageEnglish (US)
Pages (from-to)977-993
Number of pages17
JournalJournal of Industrial and Management Optimization
Volume13
Issue number2
DOIs
StatePublished - Apr 1 2017

All Science Journal Classification (ASJC) codes

  • Business and International Management
  • Strategy and Management
  • Control and Optimization
  • Applied Mathematics

Keywords

  • Heuristics
  • Makespan
  • Non-identical job sizes
  • Non-identical machine capacities
  • Parallel batch machines
  • Release times

Fingerprint

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

Cite this