An efficient constructive heuristic to balance trade-offs between makespan and flowtime in permutation flow shop scheduling

Feidi Dang, Wei Li, Honghan Ye

Research output: Contribution to journalConference articlepeer-review

3 Scopus citations


Balancing trade-offs between production cost and holding cost is critical for production and operations management. Utilization of a production line affects production cost, which relates to makespan, and work-in-process (WIP) inventories in a production line affect holding cost, which relate to flowtime. There are trade-offs between two objectives, to minimize makespan and to minimize flowtime. Without addressing trade-off balancing issues in flow shop scheduling, WIP inventories are still high in manufacturing, generating unnecessary holding cost. However, utilization is coupled with WIP inventories. Low WIP inventory levels might lower utilization and generate high production cost. Most existing constructive heuristics focus only on single-objective optimization. In the current literature, the NEH heuristic proposed by Nawaz, Enscore, and Ham (1983) is the best constructive heuristic to minimize makespan, and the LR heuristic proposed by Liu and Reeves (2001) is the best to minimize flowtime. In this paper, we propose a current and future deviation (CFD) heuristic to balance trade-offs between makespan and flowtime minimizations. Based on 5400 randomly generated instances, 120 instances in Taillard's benchmarks, and one-year historical records of operating room scheduling from University of Kentucky HealthCare (UKHC), our CFD heuristic outperforms the NEH and LR heuristics on trade-off balancing, and achieves the most stable performances from the perspective of statistical process control (SPC).

Original languageEnglish
Pages (from-to)40-48
Number of pages9
JournalProcedia Manufacturing
StatePublished - 2018
Event46th SME North American Manufacturing Research Conference, NAMRC 2018 - College Station, United States
Duration: Jun 18 2018Jun 22 2018

Bibliographical note

Funding Information:
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 uQ ality. We also appreciate the support from UK HeathCare and Department of Mechanical Engineering at University of Kentucky.

Publisher Copyright:
© 2018 The Author(s). Published by Elsevier B.V.


  • Permutation flow shop
  • constructive heuristic
  • trade-off balancing

ASJC Scopus subject areas

  • Industrial and Manufacturing Engineering
  • Artificial Intelligence


Dive into the research topics of 'An efficient constructive heuristic to balance trade-offs between makespan and flowtime in permutation flow shop scheduling'. Together they form a unique fingerprint.

Cite this