Job Shop Scheduling with Routing Flexibility and Sequence-Dependent Setup Times

This paper presents a meta-heuristic algorithm for solving a job shop scheduling problem involving both sequence dependent setup-times and the possibility of selecting alternative routes among the available machines. The proposed strategy is a variant of the Iterative Flattening Search (IFS ) schema. This work provides three separate results: (1) a constraint-based solving procedure that extends an existing approach for classical Job Shop Scheduling; (2) a new variable and value ordering heuristic based on temporal flexibility that take into account both sequence dependent setup-times and flexibility in machine selection; (3) an original relaxation strategy based on the idea of randomly breaking the execution orders of the activities on the machines with a activity selection criteria based on their proximity to the solution's critical path. The efficacy of the overall heuristic optimization algorithm is demonstrated on a new benchmark set which is an extension of a well-known and difficult benchmark for the Flexible Job Shop Scheduling Problem.

Publication type: 
Contributo in atti di convegno
Author or Creator: 
Oddi, Angelo [1]
Rasconi, Riccardo [1]
Cesta, Amedeo [1]
Smith, Stephen F. [2]
18th RCRA International Workshop on "Experimental Evaluation of Algorithms for solving problems with combinatorial explosion" (RCRA 2011), pp. 96–110, Barcelona, Spain, 17-18 July 2011
Resource Identifier:
ISTC Author: 
Angelo Oddi's picture
Real name: 
Riccardo Rasconi's picture
Real name: 
Amedeo Cesta's picture
Real name: