Combined heuristics for bi-level group scheduling problems

In this paper the comparative performance of several combined heuristics for solving bi-level group scheduling problems is investigated. At the first level, the sequence of parts within a part family/group is determined. 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 levels in order to minimize the makespan. Two different research questions are addressed. The first determines which of the combinations, each consisting of a single- (Petrov (PT)) and a multiple-pass heuristic (Logendran and Nudtasomboon (LN); Campbell, Dudek and Smith (CDS)) is a better performer. The second determines which of the two multiple-pass heuristics (LN or CDS) is a better performer, if used at both levels. The experiments have been setup as factorial designs with split-plots across the heuristics. Several test problems are solved for addressing the key issues raised in both questions. Results obtained 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 preferred arrangement. For research question 2, a combination represented by LN-LN outperforms CDS-CDS.