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

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

doi:10.1287/mnsc.39.5.616

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 publication › Journal article › Academic research › peer-review

258 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 language	English
Pages (from-to)	616-625
Number of pages	10
Journal	Management Science
Volume	39
Issue number	5
DOIs	https://doi.org/10.1287/mnsc.39.5.616
Publication status	Published - 1 Jan 1993
Externally published	Yes

ASJC Scopus subject areas

Strategy and Management
Management Science and Operations Research

More information

10.1287/mnsc.39.5.616

Cite this

@article{05b1b2de713847269ad57ecedd864ab3,

title = "Minimizing the makespan in the 3-machine assembly-type flowshop scheduling problem",

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.",

author = "Lee, {Chung Yee} and Cheng, {Edwin Tai Chiu} and Lin, {B. M.T.}",

year = "1993",

month = jan,

day = "1",

doi = "10.1287/mnsc.39.5.616",

language = "English",

volume = "39",

pages = "616--625",

journal = "Management Science",

issn = "0025-1909",

publisher = "INFORMS Institute for Operations Research and the Management Sciences",

number = "5",

}

TY - JOUR

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

AU - Lee, Chung Yee

AU - Cheng, Edwin Tai Chiu

AU - Lin, B. M.T.

PY - 1993/1/1

Y1 - 1993/1/1

N2 - 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.

AB - 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.

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

U2 - 10.1287/mnsc.39.5.616

DO - 10.1287/mnsc.39.5.616

M3 - Journal article

SN - 0025-1909

VL - 39

SP - 616

EP - 625

JO - Management Science

JF - Management Science

IS - 5

ER -

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

Abstract

ASJC Scopus subject areas

More information

Other files and links

Fingerprint

Cite this