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

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.