A two-stage hybrid flow shop with dedicated machines at the first stage

This paper considers the problem of minimizing the makespan in a two-stage hybrid flow shop with dedicated machines at stage 1. There exist multiple machines at stage 1 and one machine at stage 2. Each job must be processed on a specified machine at stage 1 depending on job type, and then the job is processed on the single machine at stage 2. First, we introduce this problem and establish the complexity of several variations of the problem. For a special case, we show that the decision version is unary NP-complete. For some other special cases, we develop optimal polynomial time solution procedures. Four heuristics based on simple rules such as Johnson's rule and the greedy-type scheduling rule are considered. For each heuristic, we provide some theoretical analysis and find a tight or asymptotically tight worst case bound on the relative error. Finally, the heuristics are empirically evaluated.