Surveying the versatility of constraint-based large neighborhood search for scheduling problems

Constraint-based search techniques have gained increasing attention in recent years as a basis for scheduling procedures that are capable of accommodating a wide range of constraints. Among these, the Large Neighborhood Search (lns) has largely proven to be a very effective heuristic-based methodology. Its basic optimization cycle consists of a continuous iteration of two steps where the solution is first relaxed and then re-constructed. In Constraint Programming terms, relaxing entails the retraction of some previously imposed constraints, while re-constructing entails imposing new constraints, searching for a better solution. Each iteration of constraint removal and re-insertion can be considered as the examination of a large neighborhood move, hence the procedure's name. Over the years, LNS has been successfully employed over a wide range of different problems; this paper intends to provide an overview of some utilization examples that demonstrate both the versatility and the effectiveness of the procedure against significantly difficult scheduling benchmarks known in literature.

Publication type: 
Contributo in atti di convegno
Author or Creator: 
Rasconi, Riccardo
Oddi, Angelo
Cesta, Amedeo
Springer, Heidelberg ;, Germania
Beyond Databases, Architectures and Structures, pp. 33–43, Ustro?, Poland, May 26-29, 2015
Resource Identifier:
ISTC Author: 
Angelo Oddi's picture
Real name: 
Riccardo Rasconi's picture
Real name: 
Amedeo Cesta's picture
Real name: