Article ID: | iaor20002780 |
Country: | Netherlands |
Volume: | 5 |
Issue: | 4 |
Start Page Number: | 437 |
End Page Number: | 454 |
Publication Date: | Dec 1999 |
Journal: | Journal of Heuristics |
Authors: | Miller D.M., Chen H.C., Matson J., Liu Q. |
Keywords: | genetic algorithms |
A hybrid genetic algorithm (HGA) is proposed for the single machine, single stage, scheduling problem in a sequence dependent setup time environment within a fixed planning horizon (SSSDP). It incorporates the elitist ranking method, genetic operators, and a hill-climbing technique in each searching area. To improve the performance and efficiency, hill climbing is performed by uniting the Wagner–Whitin Algorithm with the problem-specific knowledge. The objective of the HGA is to minimize the sum of setup cost, inventory cost, and backlog cost. The HGA is able to obtain a superior solution, if it is not optimal, in a reasonable time. The computational results of this algorithm on real life SSSDP problems are promising. In out test cases, the HGA performed up to 50% better than the Just-In-Time heuristics and 30% better than the complete batching heuristics.