AAAI Publications, Nineteenth International Conference on Automated Planning and Scheduling

Font Size: 
Improved Local Search for Job Shop Scheduling with uncertain Durations
Ines Gonzalez-Rodriguez, Camino Rodriguez Vela, Jorge Puente, Alejandro Hernandez-Arauzo

Last modified: 2009-10-16


This paper is concerned with local search methods to solve job shop scheduling problems with uncertain durations modelled as fuzzy numbers. Based on a neighbourhood structure from the literature, a reduced set of moves and the consequent structure are defined. Theoretical results show that the proposed neighbourhood contains all the improving solutions from the original neighbourhood and provide a sufficient condition for optimality. Additionally, a makespan lower bound is proposed which can be used to discard neighbours. Experimental results illustrate the good performance of both proposals, which considerably reduce the computational load of the local search, as well as a synergy effect when they are simultaneously used.


artificial intelligence; scheduling; job shop; uncertainty; fuzzy; local search

Full Text: PDF