A hybrid genetic algorithm for the single machine scheduling problem

A hybrid genetic algorithm for the single machine scheduling problem

0.00 Avg rating0 Votes
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: , , ,
Keywords: genetic algorithms
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.