Iterative Flattening Search for the Flexible Job Shop Scheduling Problem

This paper presents a meta-heuristic algorithm for solving the Flexible Job Shop Scheduling Problem (FJSSP). This strategy, known as Iterative Flattening Search (IFS), iteratively applies a relaxation-step, in which a subset of scheduling decisions are randomly retracted from the current solution; and a solving-step, in which a new solution is incrementally recomputed from this partial schedule. This work contributes two separate results: (1) it proposes a constraint-based procedure extending an existing approach previously used for classical Job Shop Scheduling Problem; (2) it proposes an original relaxation strategy on feasible FJSSP solutions based on the idea of randomly breaking the execution orders of the activities on the machines and opening the resource options for some activities selected at random. The efficacy of the overall heuristic optimization algorithm is demonstrated on a set of well-known benchmarks.

Publication type: 
Contributo in atti di convegno
Author or Creator: 
Oddi, Angelo
Rasconi, Riccardo
Cesta, Amedeo
Smith, Stephen F.
AAAI Press, Arlington [VA], USA
22nd International Joint Conference on Artificial Intelligence, 2011. Proceedings, pp. 1991–1996, Barcelona, Spain, 16-22 July 2011
Resource Identifier:
ISTC Author: 
Angelo Oddi's picture
Real name: 
Riccardo Rasconi's picture
Real name: 
Amedeo Cesta's picture
Real name: