A heuristic approach for multi-stage sequence-dependent group scheduling problems

Abstract

We present several heuristic algorithms based on tabu search for solving the multi-stage sequence-dependent group scheduling (SDGS) problem by considering minimization of makespan as the criterion. As the problem is recognized to be strongly NP-hard, several meta (tabu) search-based solution algorithms are developed to efficiently solve industry-size problem instances. Also, two different initial solution generators are developed to aid in the application of the tabu search-based algorithms. A lower bounding technique based on relaxing the mathematical model for the original SDGS problem is applied to estimate the quality of the heuristic algorithms. To find the best heuristic algorithm, random test problems, ranging in size from small, medium, to large are created and solved by the heuristic algorithms. A detailed statistical experiment, based on nested split-plot design, is performed to find the best heuristic algorithm and the best initial solution gen-erator. The results of the experiment show that the tabu search-based algorithms can provide high quality so-lutions for the problems with an average percentage error of only 1.00%.