Analysis of a Heuristics for Scheduling Two-Stage Hybrid Flow Shop

This paper focuses on the scheduling problem of minimizing the makespan for a given set of jobs in a two-stage hybrid flowshop environment. In each stage, there are identical parallel machines. We present a heuristic algorithm which extends a few classes of the heuristics for solving the problem with only one machine on the second stage. Furthermore, we give a theoretical analysis of the worst-case performance of the proposed algorithm and prove that a schedule generated by the algorithm with length at most 3-2/m₁ (m1 is the machine number of the first stage) times (bound) that of an optimal schedule and that this bound is tight.