Effective heuristic for makespan minimization in parallel batch machines with non-identical capacities

Zhao Hong Jia; Kai Li; Joseph Y.T. Leung

doi:10.1016/j.ijpe.2015.07.021

Effective heuristic for makespan minimization in parallel batch machines with non-identical capacities

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

Computer Science

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

43 Scopus citations

Abstract

We consider the problem of scheduling a set of n jobs with arbitrary job sizes on a set of m parallel batch machines with non-identical capacities; the objective is to minimize the makespan. The problem is known to be NP-hard. A heuristic based on the First-Fit-Decreasing (FFD) rule is presented as well as a meta-heuristic based on Max-Min Ant System (MMAS). The performances of the two heuristics are compared with a previously studied heuristic by computational experiments. The results show that both proposed algorithms outperform the previously studied heuristic. Moreover, the MMAS heuristic obtains better solutions compared with the FFD heuristic.

Original language	English (US)
Pages (from-to)	1-10
Number of pages	10
Journal	International Journal of Production Economics
Volume	169
DOIs	https://doi.org/10.1016/j.ijpe.2015.07.021
State	Published - Nov 1 2015

All Science Journal Classification (ASJC) codes

General Business, Management and Accounting
Economics and Econometrics
Management Science and Operations Research
Industrial and Manufacturing Engineering

Keywords

Heuristic
Makespan
Max-Min Ant System
NP-hard
Non-identical machine capacity
Parallel batch machines

Access to Document

10.1016/j.ijpe.2015.07.021

Cite this

@article{97103754b8fb4adabed711b0b8891319,

title = "Effective heuristic for makespan minimization in parallel batch machines with non-identical capacities",

abstract = "We consider the problem of scheduling a set of n jobs with arbitrary job sizes on a set of m parallel batch machines with non-identical capacities; the objective is to minimize the makespan. The problem is known to be NP-hard. A heuristic based on the First-Fit-Decreasing (FFD) rule is presented as well as a meta-heuristic based on Max-Min Ant System (MMAS). The performances of the two heuristics are compared with a previously studied heuristic by computational experiments. The results show that both proposed algorithms outperform the previously studied heuristic. Moreover, the MMAS heuristic obtains better solutions compared with the FFD heuristic.",

keywords = "Heuristic, Makespan, Max-Min Ant System, NP-hard, Non-identical machine capacity, Parallel batch machines",

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

year = "2015",

month = nov,

day = "1",

doi = "10.1016/j.ijpe.2015.07.021",

language = "English (US)",

volume = "169",

pages = "1--10",

journal = "International Journal of Production Economics",

issn = "0925-5273",

publisher = "Elsevier B.V.",

}

TY - JOUR

T1 - Effective heuristic for makespan minimization in parallel batch machines with non-identical capacities

AU - Jia, Zhao Hong

AU - Li, Kai

AU - Leung, Joseph Y.T.

PY - 2015/11/1

Y1 - 2015/11/1

N2 - We consider the problem of scheduling a set of n jobs with arbitrary job sizes on a set of m parallel batch machines with non-identical capacities; the objective is to minimize the makespan. The problem is known to be NP-hard. A heuristic based on the First-Fit-Decreasing (FFD) rule is presented as well as a meta-heuristic based on Max-Min Ant System (MMAS). The performances of the two heuristics are compared with a previously studied heuristic by computational experiments. The results show that both proposed algorithms outperform the previously studied heuristic. Moreover, the MMAS heuristic obtains better solutions compared with the FFD heuristic.

AB - We consider the problem of scheduling a set of n jobs with arbitrary job sizes on a set of m parallel batch machines with non-identical capacities; the objective is to minimize the makespan. The problem is known to be NP-hard. A heuristic based on the First-Fit-Decreasing (FFD) rule is presented as well as a meta-heuristic based on Max-Min Ant System (MMAS). The performances of the two heuristics are compared with a previously studied heuristic by computational experiments. The results show that both proposed algorithms outperform the previously studied heuristic. Moreover, the MMAS heuristic obtains better solutions compared with the FFD heuristic.

KW - Heuristic

KW - Makespan

KW - Max-Min Ant System

KW - NP-hard

KW - Non-identical machine capacity

KW - Parallel batch machines

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

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

U2 - 10.1016/j.ijpe.2015.07.021

DO - 10.1016/j.ijpe.2015.07.021

M3 - Article

AN - SCOPUS:84942788341

SN - 0925-5273

VL - 169

SP - 1

EP - 10

JO - International Journal of Production Economics

JF - International Journal of Production Economics

ER -

Effective heuristic for makespan minimization in parallel batch machines with non-identical capacities

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this