Article ID: | iaor20121528 |
Volume: | 39 |
Issue: | 10 |
Start Page Number: | 2346 |
End Page Number: | 2358 |
Publication Date: | Oct 2012 |
Journal: | Computers and Operations Research |
Authors: | Vanhoucke Mario, Sels Veronique |
Keywords: | heuristics: genetic algorithms, heuristics: local search |
We consider the problem of scheduling a number of jobs, each job having a release time, a processing time, a due date and a family setup time, on a single machine with the objective of minimizing the maximum lateness. We develop a hybrid genetic algorithm and validate its performance on a newly developed diverse data set. We perform an extensive study of local search algorithms, based on the trade‐off between intensification and diversification strategies, taking the characteristics of the problem into account. We combine different local search neighborhood structures in an intelligent manner to further improve the solution quality. We use the hybrid genetic algorithm to perform a comprehensive analysis of the influence of the different problem parameters on the average maximum lateness value and the performance of the algorithm(s).