Iterative Flattening Search for the Flexible Job Shop Scheduling Problem
Angelo Oddi, Riccardo Rasconi, Amedeo Cesta and Stephen Smith
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 two steps: (1) a relaxation-step, in which a subset of scheduling decisions are randomly retracted from the current solution; and (2) a solving-step, in which a new solution is incrementally recomputed from this partial schedule. The work proposes a twofold contribution. First, we propose an original extension of a constraint-based procedure for solving the classical Job Shop Scheduling Problem. This procedure incrementally creates a solution by assigning resources to activities, and generates consistent orderings of activities that require the same resource by imposing precedence constraints on a temporally feasible solution. Key to the effectiveness of the search procedure are variable and value ordering heuristics using temporal flexibility measures. Second, we propose 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 empirically on a set of well-known FJSSP benchmarks.