Constraint Programming Approach for Scheduling Jobs with Release Times, Non-Identical Sizes, and Incompatible Families on Parallel Batching Machines

Andy Ham; John Fowler; Eray Cakici

doi:10.1109/TSM.2017.2740340

Constraint Programming Approach for Scheduling Jobs with Release Times, Non-Identical Sizes, and Incompatible Families on Parallel Batching Machines

Andy Ham, John Fowler, Eray Cakici

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

25 Scopus citations

Abstract

We study a parallel batch-scheduling problem that involves the constraints of different job release times, non-identical job sizes, and incompatible job families, is addressed. Mixed integer programming and constraint programming (CP) models are proposed and tested on a set of common problem instances from a paper in the literature. Then, we compare the performance of the models with that of a variable neighborhood search (VNS) heuristic from the same paper. Computational results show that CP outperforms VNS with respect to solution quality and run time by 3.4%-6.8% and 47%-91%, respectively. When compared to optimal solutions, the results demonstrate CP is capable of generating a near optimal solution in a short amount of time.

Original language	English (US)
Article number	8010885
Pages (from-to)	500-507
Number of pages	8
Journal	IEEE Transactions on Semiconductor Manufacturing
Volume	30
Issue number	4
DOIs	https://doi.org/10.1109/TSM.2017.2740340
State	Published - Nov 2017

Keywords

CP
MIP
Parallel batching
VNS
incompatible

ASJC Scopus subject areas

Electronic, Optical and Magnetic Materials
Condensed Matter Physics
Industrial and Manufacturing Engineering
Electrical and Electronic Engineering

Access to Document

10.1109/TSM.2017.2740340

Cite this

@article{e1024b5292a744c9bca7f1717f4d76d5,

title = "Constraint Programming Approach for Scheduling Jobs with Release Times, Non-Identical Sizes, and Incompatible Families on Parallel Batching Machines",

abstract = "We study a parallel batch-scheduling problem that involves the constraints of different job release times, non-identical job sizes, and incompatible job families, is addressed. Mixed integer programming and constraint programming (CP) models are proposed and tested on a set of common problem instances from a paper in the literature. Then, we compare the performance of the models with that of a variable neighborhood search (VNS) heuristic from the same paper. Computational results show that CP outperforms VNS with respect to solution quality and run time by 3.4%-6.8% and 47%-91%, respectively. When compared to optimal solutions, the results demonstrate CP is capable of generating a near optimal solution in a short amount of time.",

keywords = "CP, MIP, Parallel batching, VNS, incompatible",

author = "Andy Ham and John Fowler and Eray Cakici",

note = "Publisher Copyright: {\textcopyright} 1988-2012 IEEE.",

year = "2017",

month = nov,

doi = "10.1109/TSM.2017.2740340",

language = "English (US)",

volume = "30",

pages = "500--507",

journal = "IEEE Transactions on Semiconductor Manufacturing",

issn = "0894-6507",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

number = "4",

}

TY - JOUR

T1 - Constraint Programming Approach for Scheduling Jobs with Release Times, Non-Identical Sizes, and Incompatible Families on Parallel Batching Machines

AU - Ham, Andy

AU - Fowler, John

AU - Cakici, Eray

PY - 2017/11

Y1 - 2017/11

N2 - We study a parallel batch-scheduling problem that involves the constraints of different job release times, non-identical job sizes, and incompatible job families, is addressed. Mixed integer programming and constraint programming (CP) models are proposed and tested on a set of common problem instances from a paper in the literature. Then, we compare the performance of the models with that of a variable neighborhood search (VNS) heuristic from the same paper. Computational results show that CP outperforms VNS with respect to solution quality and run time by 3.4%-6.8% and 47%-91%, respectively. When compared to optimal solutions, the results demonstrate CP is capable of generating a near optimal solution in a short amount of time.

AB - We study a parallel batch-scheduling problem that involves the constraints of different job release times, non-identical job sizes, and incompatible job families, is addressed. Mixed integer programming and constraint programming (CP) models are proposed and tested on a set of common problem instances from a paper in the literature. Then, we compare the performance of the models with that of a variable neighborhood search (VNS) heuristic from the same paper. Computational results show that CP outperforms VNS with respect to solution quality and run time by 3.4%-6.8% and 47%-91%, respectively. When compared to optimal solutions, the results demonstrate CP is capable of generating a near optimal solution in a short amount of time.

KW - CP

KW - MIP

KW - Parallel batching

KW - VNS

KW - incompatible

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

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

U2 - 10.1109/TSM.2017.2740340

DO - 10.1109/TSM.2017.2740340

M3 - Article

AN - SCOPUS:85028456966

SN - 0894-6507

VL - 30

SP - 500

EP - 507

JO - IEEE Transactions on Semiconductor Manufacturing

JF - IEEE Transactions on Semiconductor Manufacturing

IS - 4

M1 - 8010885

ER -

Constraint Programming Approach for Scheduling Jobs with Release Times, Non-Identical Sizes, and Incompatible Families on Parallel Batching Machines

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this