Minimizing total completion time in a two-stage hybrid flow shop with dedicated machines at the first stage

作者：Yang Jaehwan^*

来源：Computers & Operations Research, 2015, 58: 1-8.

DOI：10.1016/j.cor.2014.11.012

• Two-stage hybrid flow shop
• Computational complexity
• Heuristic
• Worst case bound on relative error

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.

• 出版日期2015-6