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

We present several heuristic algorithms based on tabu search for solving the multi-stage sequencedependentgroup scheduling (sdgs) problem by considering minimization of makespan as the criterion. asthe problem is recognized to be strongly np-hard, several meta (tabu) search-based solution algorithms aredeveloped to efficiently solve industry-size problem instances. also, two different initial solution generatorsare developed to aid in the application of the tabu search-based algorithms. a lower bounding technique basedon relaxing the mathematical model for the original sdgs problem is applied to estimate the quality of theheuristic 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, basedon nested split-plot design, is performed to find the best heuristic algorithm and the best initial solution generator.the results of the experiment show that the tabu search-based algorithms can provide high quality solutionsfor the problems with an average percentage error of only 1.00%.