Heuristic local search for fuzzy open shop scheduling

Abstract

We consider the fuzzy open shop scheduling problem, where task durations are assumed to be ill-known and modelled as triangular fuzzy numbers. We propose a neighbourhood structure for local search procedures, based on reversing critical arcs in the associated disjunctive graph. We provide a thorough theoretical study of the structure and, in particular, prove that feasibility and asymptotic convergence hold. We further illustrate its good behaviour with experimental results obtained by incorporating the local search procedure to an existing genetic algorithm from the literature and provide a new benchmark of problem instances