A meta-heuristic to minimize makespan for parallel batch machines with arbitrary job sizes

Zhao Hong Jia; Joseph Y.T. Leung

doi:10.1016/j.ejor.2014.07.039

A meta-heuristic to minimize makespan for parallel batch machines with arbitrary job sizes

Zhao Hong Jia, Joseph Y.T. Leung

Computer Science

Research output: Contribution to journal › Article › peer-review

59 Scopus citations

Abstract

We consider the problem of scheduling a set of n jobs with arbitrary job sizes on a set of m identical and parallel batch machines so as to minimize the makespan. Motivated by the computational complexity of the problem, we propose a meta-heuristic based on the max-min ant system method. Computational experiments are performed with randomly generated test data. The results show that our algorithm outperforms several of the previously studied algorithms.

Original language	English (US)
Pages (from-to)	649-665
Number of pages	17
Journal	European Journal of Operational Research
Volume	240
Issue number	3
DOIs	https://doi.org/10.1016/j.ejor.2014.07.039
State	Published - 2015

All Science Journal Classification (ASJC) codes

General Computer Science
Modeling and Simulation
Management Science and Operations Research
Information Systems and Management

Keywords

Max-min ant system
Meta-heuristic
NP-hard
Parallel batch machines

Access to Document

10.1016/j.ejor.2014.07.039

Cite this

@article{880ce7928f0c4d60a4346fb85916febc,

title = "A meta-heuristic to minimize makespan for parallel batch machines with arbitrary job sizes",

abstract = "We consider the problem of scheduling a set of n jobs with arbitrary job sizes on a set of m identical and parallel batch machines so as to minimize the makespan. Motivated by the computational complexity of the problem, we propose a meta-heuristic based on the max-min ant system method. Computational experiments are performed with randomly generated test data. The results show that our algorithm outperforms several of the previously studied algorithms.",

keywords = "Max-min ant system, Meta-heuristic, NP-hard, Parallel batch machines",

author = "Jia, {Zhao Hong} and Leung, {Joseph Y.T.}",

year = "2015",

doi = "10.1016/j.ejor.2014.07.039",

language = "English (US)",

volume = "240",

pages = "649--665",

journal = "European Journal of Operational Research",

issn = "0377-2217",

publisher = "Elsevier B.V.",

number = "3",

}

TY - JOUR

T1 - A meta-heuristic to minimize makespan for parallel batch machines with arbitrary job sizes

AU - Jia, Zhao Hong

AU - Leung, Joseph Y.T.

PY - 2015

Y1 - 2015

N2 - We consider the problem of scheduling a set of n jobs with arbitrary job sizes on a set of m identical and parallel batch machines so as to minimize the makespan. Motivated by the computational complexity of the problem, we propose a meta-heuristic based on the max-min ant system method. Computational experiments are performed with randomly generated test data. The results show that our algorithm outperforms several of the previously studied algorithms.

AB - We consider the problem of scheduling a set of n jobs with arbitrary job sizes on a set of m identical and parallel batch machines so as to minimize the makespan. Motivated by the computational complexity of the problem, we propose a meta-heuristic based on the max-min ant system method. Computational experiments are performed with randomly generated test data. The results show that our algorithm outperforms several of the previously studied algorithms.

KW - Max-min ant system

KW - Meta-heuristic

KW - NP-hard

KW - Parallel batch machines

UR - http://www.scopus.com/inward/record.url?scp=85027936789&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85027936789&partnerID=8YFLogxK

U2 - 10.1016/j.ejor.2014.07.039

DO - 10.1016/j.ejor.2014.07.039

M3 - Article

AN - SCOPUS:85027936789

SN - 0377-2217

VL - 240

SP - 649

EP - 665

JO - European Journal of Operational Research

JF - European Journal of Operational Research

IS - 3

ER -

A meta-heuristic to minimize makespan for parallel batch machines with arbitrary job sizes

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this