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

Chung Yee Lee; T. C.E. Cheng; Miao-Tsong Lin

doi:10.1287/mnsc.39.5.616

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

Chung Yee Lee^*, T. C.E. Cheng, Miao-Tsong Lin

^*Corresponding author for this work

Institute of Information Management

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

291 Scopus citations

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
State	Published - 1993

Access to Document

10.1287/mnsc.39.5.616

Cite this

@article{12dd90aedc0b4498bc4774e1e434d5d1,

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, {T. C.E.} and Miao-Tsong Lin",

year = "1993",

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, T. C.E.

AU - Lin, Miao-Tsong

PY - 1993

Y1 - 1993

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 - Article

AN - SCOPUS:0027590319

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

Access to Document

Other files and links

Fingerprint

Cite this