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/m1 (ml is the machine number of the first stage) times (bound) that of an optimal schedule and that this bound is tight.
展开▼
