An effective and efficient heuristic for no-wait flow shop production to minimize total completion time

Honghan Ye; Wei Li; Amin Abedini; Barrie Nault

doi:10.1016/j.cie.2017.04.002

An effective and efficient heuristic for no-wait flow shop production to minimize total completion time

Honghan Ye
, Wei Li
, Amin Abedini
, Barrie Nault

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

24 Scopus citations

Abstract

No-wait flow shop production has been widely applied in manufacturing. However, minimization of total completion time for no-wait flow shop production is NP-complete. Consequently, achieving good effectiveness and efficiency is a challenge in no-wait flow shop scheduling, where effectiveness means the deviation from optimal solutions and efficiency means the computational complexity or computation time. We propose a current and future idle time (CFI) constructive heuristic for no-wait flow shop scheduling to minimize total completion time. To improve effectiveness, we take current idle times and future idle times into consideration and use the insertion and neighborhood exchanging techniques. To improve efficiency, we introduce an objective increment method and determine the number of iterations to reduce the computation time. Compared with three recently developed heuristics, our CFI heuristic can achieve greater effectiveness in less computation time based on Taillard's benchmarks and 600 randomly generated instances. Moreover, using our CFI heuristic for operating room (OR) scheduling, we decrease the average patient flow times by 11.2% over historical ones in University of Kentucky Health Care (UKHC).

Original language	English
Pages (from-to)	57-69
Number of pages	13
Journal	Computers and Industrial Engineering
Volume	108
DOIs	https://doi.org/10.1016/j.cie.2017.04.002
State	Published - Jun 1 2017

Bibliographical note

Publisher Copyright:
© 2017 Elsevier Ltd

Funding

This project was supported by Grant No. R03HS024633 from the Agency for Healthcare Research and Quality. The content is solely the responsibility of the authors and does not necessarily represent the official views of the Agency for Healthcare Research and Quality. We also appreciate the support from UK HeathCare, Department of Mechanical Engineering at University of Kentucky and Haskayne School of Business at University of Calgary.

Funders
Agency for Healthcare Research and Quality

Keywords

Computational complexity
Heuristics
No-wait flow shop
Total completion time

ASJC Scopus subject areas

General Computer Science
General Engineering

Access to Document

10.1016/j.cie.2017.04.002

Cite this

@article{27a51b48fc7f4031adc63988f5a80a1d,

title = "An effective and efficient heuristic for no-wait flow shop production to minimize total completion time",

abstract = "No-wait flow shop production has been widely applied in manufacturing. However, minimization of total completion time for no-wait flow shop production is NP-complete. Consequently, achieving good effectiveness and efficiency is a challenge in no-wait flow shop scheduling, where effectiveness means the deviation from optimal solutions and efficiency means the computational complexity or computation time. We propose a current and future idle time (CFI) constructive heuristic for no-wait flow shop scheduling to minimize total completion time. To improve effectiveness, we take current idle times and future idle times into consideration and use the insertion and neighborhood exchanging techniques. To improve efficiency, we introduce an objective increment method and determine the number of iterations to reduce the computation time. Compared with three recently developed heuristics, our CFI heuristic can achieve greater effectiveness in less computation time based on Taillard's benchmarks and 600 randomly generated instances. Moreover, using our CFI heuristic for operating room (OR) scheduling, we decrease the average patient flow times by 11.2\% over historical ones in University of Kentucky Health Care (UKHC).",

keywords = "Computational complexity, Heuristics, No-wait flow shop, Total completion time",

author = "Honghan Ye and Wei Li and Amin Abedini and Barrie Nault",

note = "Publisher Copyright: {\textcopyright} 2017 Elsevier Ltd",

year = "2017",

month = jun,

day = "1",

doi = "10.1016/j.cie.2017.04.002",

language = "English",

volume = "108",

pages = "57--69",

}

TY - JOUR

T1 - An effective and efficient heuristic for no-wait flow shop production to minimize total completion time

AU - Ye, Honghan

AU - Li, Wei

AU - Abedini, Amin

AU - Nault, Barrie

PY - 2017/6/1

Y1 - 2017/6/1

N2 - No-wait flow shop production has been widely applied in manufacturing. However, minimization of total completion time for no-wait flow shop production is NP-complete. Consequently, achieving good effectiveness and efficiency is a challenge in no-wait flow shop scheduling, where effectiveness means the deviation from optimal solutions and efficiency means the computational complexity or computation time. We propose a current and future idle time (CFI) constructive heuristic for no-wait flow shop scheduling to minimize total completion time. To improve effectiveness, we take current idle times and future idle times into consideration and use the insertion and neighborhood exchanging techniques. To improve efficiency, we introduce an objective increment method and determine the number of iterations to reduce the computation time. Compared with three recently developed heuristics, our CFI heuristic can achieve greater effectiveness in less computation time based on Taillard's benchmarks and 600 randomly generated instances. Moreover, using our CFI heuristic for operating room (OR) scheduling, we decrease the average patient flow times by 11.2% over historical ones in University of Kentucky Health Care (UKHC).

AB - No-wait flow shop production has been widely applied in manufacturing. However, minimization of total completion time for no-wait flow shop production is NP-complete. Consequently, achieving good effectiveness and efficiency is a challenge in no-wait flow shop scheduling, where effectiveness means the deviation from optimal solutions and efficiency means the computational complexity or computation time. We propose a current and future idle time (CFI) constructive heuristic for no-wait flow shop scheduling to minimize total completion time. To improve effectiveness, we take current idle times and future idle times into consideration and use the insertion and neighborhood exchanging techniques. To improve efficiency, we introduce an objective increment method and determine the number of iterations to reduce the computation time. Compared with three recently developed heuristics, our CFI heuristic can achieve greater effectiveness in less computation time based on Taillard's benchmarks and 600 randomly generated instances. Moreover, using our CFI heuristic for operating room (OR) scheduling, we decrease the average patient flow times by 11.2% over historical ones in University of Kentucky Health Care (UKHC).

KW - Computational complexity

KW - Heuristics

KW - No-wait flow shop

KW - Total completion time

UR - https://www.scopus.com/pages/publications/85017426833

UR - https://www.scopus.com/pages/publications/85017426833#tab=citedBy

U2 - 10.1016/j.cie.2017.04.002

DO - 10.1016/j.cie.2017.04.002

M3 - Article

AN - SCOPUS:85017426833

SN - 0360-8352

VL - 108

SP - 57

EP - 69

JO - Computers and Industrial Engineering

JF - Computers and Industrial Engineering

ER -

An effective and efficient heuristic for no-wait flow shop production to minimize total completion time

Abstract

Bibliographical note

Funding

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this