Minimizing makespan for arbitrary size jobs with release times on P-batch machines with arbitrary capacities

Zhaohong Jia, Xiaohao Li, Joseph Y.T. Leung

Research output: Contribution to journalArticlepeer-review

21 Scopus citations

Abstract

We consider the problem of scheduling a set of arbitrary size jobs with dynamic arrival times on a set of parallel batch machines with arbitrary capacities; our goal is to minimize the makespan. We first give a mathematical model of the problem, and provide a lower bound for the objective function value. Based on different rules of batching the jobs and scheduling the batches on the machines, two meta-heuristics based on Ant Colony Optimization (ACO) are proposed to solve the problem. The performance of the proposed algorithms is evaluated and compared with existing heuristics by computational experiments. Our results show that one of the ACO algorithms consistently finds better solutions than all the others in a reasonable amount of time.

Original languageEnglish (US)
Pages (from-to)22-34
Number of pages13
JournalFuture Generation Computer Systems
Volume67
DOIs
StatePublished - Feb 1 2017

All Science Journal Classification (ASJC) codes

  • Software
  • Hardware and Architecture
  • Computer Networks and Communications

Keywords

  • Ant colony optimization
  • Makespan
  • Parallel batch machines with arbitrary capacities
  • Release times
  • Scheduling

Fingerprint

Dive into the research topics of 'Minimizing makespan for arbitrary size jobs with release times on P-batch machines with arbitrary capacities'. Together they form a unique fingerprint.

Cite this