A hybrid genetic algorithm for the single machine scheduling problem with sequence-dependent setup times

• Published in: Computers & operations research 2012-10, Vol.39 (10), p.2415-2424
• Main Authors: Sioud, A., Gravel, M., Gagné, C.
• Format: Article
• Language: English
• Subjects: Applied sciences; Benchmarks; Decision theory. Utility theory; Exact sciences and technology; Genetic algorithm; Genetic algorithms; Hybrid metaheuristics; Job shops; Mathematical models; Operational research and scientific management; Operational research. Management science; Operations research; Optimization algorithms; Programming; Scheduling; Scheduling, sequencing; Sensitivity analysis; Sequence-dependent setup times; Sequential scheduling; Setup times; Studies; Total tardiness
• ISSN: 0305-0548; 1873-765X; 0305-0548
• DOI: 10.1016/j.cor.2011.12.017

This paper presents a hybrid approach based on the integration between a genetic algorithm (GA) and concepts from constraint programming, multi-objective evolutionary algorithms and ant colony optimization for solving a scheduling problem. The main contributions are the integration of these concepts in a GA crossover operator. The proposed methodology is applied to a single machine scheduling problem with sequence-dependent setup times for the objective of minimizing the total tardiness. A sensitivity analysis of the hybrid approach is carried out to compare the performance of the GA and the hybrid genetic algorithm (HGA) approaches on different benchmarks from the literature. The numerical experiments demonstrate the HGA efficiency and effectiveness which generates solutions that approach those of the known reference sets and improves several lower bounds.