A new Local Search for the Job Shop Problem with uncertain Durations

Ines Gonzalez-Rodriguez, Camino R. Vela, Jorge Puente, Ramiro Varela

In the sequel we consider the job shop scheduling problem with uncertain durations represented as triangular fuzzy numbers. We propose a new neighbourhood structure for local search, based on a new definition of critical path for fuzzy durations. A theoretical analysis of the proposed structure shows that it improves a previous one from the literature. It also shows that feasibility and connectivity hold, these being two highly desirable properties. Experimental results are reported which further illustrate the potential of the proposal.

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.