A new local search for the job shop problem with uncertain durations

Abstract

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