TY - JOUR
T1 - Minimizing total completion time in a two-stage hybrid flow shop with dedicated machines at the first stage
AU - Yang, Jaehwan
N1 - Publisher Copyright:
© 2014 Elsevier Ltd. All rights reserved.
PY - 2015/6
Y1 - 2015/6
N2 - This paper considers a two-stage hybrid flow shop scheduling with dedicated machines at stage 1 with the objective of minimizing the total completion time. There exist two machines at stage 1 and one machine at stage 2. Each job must be processed on one of the two dedicated machines at stage 1 depending on the job type; subsequently, the job is processed on the single machine at stage 2. First, we introduce the problem and establish the complexity of the problem. For a special case in which the processing times on the machine at stage 2 are identical, an optimal solution is presented; for three special cases, we show that the decision version is unary NP-complete. For the general case, two simple and intuitive heuristics are introduced, and a worst case bound on the relative error is found for each of the heuristics. Finally, we empirically evaluate the heuristics, including an optimal algorithm for a special case.
AB - This paper considers a two-stage hybrid flow shop scheduling with dedicated machines at stage 1 with the objective of minimizing the total completion time. There exist two machines at stage 1 and one machine at stage 2. Each job must be processed on one of the two dedicated machines at stage 1 depending on the job type; subsequently, the job is processed on the single machine at stage 2. First, we introduce the problem and establish the complexity of the problem. For a special case in which the processing times on the machine at stage 2 are identical, an optimal solution is presented; for three special cases, we show that the decision version is unary NP-complete. For the general case, two simple and intuitive heuristics are introduced, and a worst case bound on the relative error is found for each of the heuristics. Finally, we empirically evaluate the heuristics, including an optimal algorithm for a special case.
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=84921367635&partnerID=8YFLogxK
U2 - 10.1016/j.cor.2014.11.012
DO - 10.1016/j.cor.2014.11.012
M3 - Article
AN - SCOPUS:84921367635
SN - 0305-0548
VL - 58
SP - 1
EP - 8
JO - Computers and Operations Research
JF - Computers and Operations Research
ER -