TY - JOUR
T1 - Hybrid flow shop with parallel machines at the first stage and dedicated machines at the second stage
AU - Yang, Jaehwan
N1 - Publisher Copyright:
© 2015 KIIE.
PY - 2015/3/1
Y1 - 2015/3/1
N2 - In this paper, a two-stage hybrid flow shop problem is considered. Specifically, there exist identical parallel machines at stage 1 and two dedicated machines at stage 2, and the objective of the problem is to minimize makespan. After being processed by any machine at stage 1, a job must be processed by a specific machine at stage 2 depending on the job type, and one type of jobs can have different processing times on each machine. First, we introduce the problem and establish complexity of several variations of the problem. For some special cases, we develop optimal polynomial time solution procedures. Then, we establish some simple lower bounds for the problem. In order to solve this NP-hard problem, three heuristics based on simple rules such as the Johnson's rule and the LPT (Longest Processing Time first) rule are developed. For each of the heuristics, we provide some theoretical analysis and find some worst case bound on relative error. Finally, we empirically evaluate the heuristics.
AB - In this paper, a two-stage hybrid flow shop problem is considered. Specifically, there exist identical parallel machines at stage 1 and two dedicated machines at stage 2, and the objective of the problem is to minimize makespan. After being processed by any machine at stage 1, a job must be processed by a specific machine at stage 2 depending on the job type, and one type of jobs can have different processing times on each machine. First, we introduce the problem and establish complexity of several variations of the problem. For some special cases, we develop optimal polynomial time solution procedures. Then, we establish some simple lower bounds for the problem. In order to solve this NP-hard problem, three heuristics based on simple rules such as the Johnson's rule and the LPT (Longest Processing Time first) rule are developed. For each of the heuristics, we provide some theoretical analysis and find some worst case bound on relative error. Finally, we empirically evaluate the heuristics.
KW - Computational complexity
KW - Heuristic
KW - Two-stage hybrid flow shop
KW - Worst case bound on relative error
UR - http://www.scopus.com/inward/record.url?scp=84941194360&partnerID=8YFLogxK
U2 - 10.7232/iems.2015.14.1.022
DO - 10.7232/iems.2015.14.1.022
M3 - Article
AN - SCOPUS:84941194360
SN - 1598-7248
VL - 14
SP - 22
EP - 31
JO - Industrial Engineering and Management Systems
JF - Industrial Engineering and Management Systems
IS - 1
ER -