A New Hybrid Genetic Algorithm for the Job Shop Scheduling Problem with Setup Times

Miguel A. González, Camino R. Vela, Ramiro Varela

In this paper we face the Job Shop Scheduling Problem with Sequence Dependent Setup Times by means of a genetic algorithm hybridized with local search. We have built on a previous work and propose a new neighborhood structure for this problem which is based on reversing operations on a critical path. We have conducted an experimental study across the conventional benchmarks and some new ones of larger size. The results of these experiments show clearly that our approach outperforms the current state-of-the-art methods.

Subjects: 1.12 Scheduling; 1.9 Genetic Algorithms

Submitted: Jun 25, 2008

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.