COMBINED HEURISTICS FOR BI-LEVEL GROUP SCHEDULING PROBLEMS

In this paper the comparative performance of several combined heuristi cs for solving bi-level group scheduling problems is investigated. At the first level, the sequence of parts within a part family/group is d etermined. While at the second, an appropriate sequence for groups of jobs is determined. Both single-pass and multiple-pass heuristics are selected for completely solving a group scheduling problem at both lev els in order to minimize the makespan. Two different research question s are addressed. The first determines which of the combinations, each consisting of a single-(Petrov, 1966 (PT)) and a multiple-pass heurist ic (Logendran and Nudtasomboon, 1991 (LN); Campbell, Dudek and Smith, 1970 (CDS)), is a better performer. The second determines which of the two multiple-pass heuristics (LN or CDS) is a better performer, if us ed at both levels. The experiments have been setup as factorial design s with split-plots across the heuristics. Several test problems are so lved for addressing the key issues raised in both questions. Results o btained show that, for research question 1, a combination given by LN at the first level, followed by PT at the second level is the most pre ferred arrangement. For research question 2, a combination represented by LN-LN outperforms CDS-CDS.