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

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.