Minimizing the makespan in the 3-machine assembly-type flowshop scheduling problem

Chung Yee Lee, Edwin Tai Chiu Cheng, B. M.T. Lin

Research output: Journal article publicationJournal articleAcademic researchpeer-review

219 Citations (Scopus)

Abstract

This paper considers minimizing the makespan in the 3-machine assembly-type flowshop scheduling problem. After problem formulation, we present a proof to show that the general version of this problem is strongly NP-complete. We then discuss a few polynomially solvable cases of the problem and present the solution algorithms. Next, a branch and bound solution scheme is suggested. Finally, three heuristics to find approximate solutions to the general problem are proposed and their error bounds are analyzed.
Original languageEnglish
Pages (from-to)616-625
Number of pages10
JournalManagement Science
Volume39
Issue number5
DOIs
Publication statusPublished - 1 Jan 1993
Externally publishedYes

ASJC Scopus subject areas

  • Strategy and Management
  • Management Science and Operations Research

Cite this