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.
Surveying the versatility of constraint-based large neighborhood search for scheduling problems
Contributo in atti di convegno
Springer, Heidelberg ;, Germania
Beyond Databases, Architectures and Structures, pp. 33–43, Ustro?, Poland, May 26-29, 2015