Bohlin, Markus and Kocjan, Waldemar and Kreuger, Per (2002) Designing Global Scheduling Constraints for Local Search: A Generic Approach. [SICS Report]
![]()
| PDF 375Kb | |
![]() | Postscript 191Kb |
Abstract
In this work we present a novel method to automate the computation of global constraints cost for local search. The method is based on the representation of a global constraints as graph properties on a binary constraint network. This formulation simplifies the implementation of global constraints in local search, and provides a cost that can be readily compared to one obtained for subproblems using binary constraints exclusively. The cost obtained can be efficiently updated during the search using incremental methods. The representation of a global constraint as outlined above can also be used for generation of suitable neighborhoods for the constraint. This is done using simple repair functions applied on the elementary constraints in the global constraint graph. We show the usability of our approach by presenting formulations of global constraints in non-overlapping and cumulative scheduling.
Item Type: | SICS Report |
---|---|
Uncontrolled Keywords: | Local Search, Global Constraints, Scheduling |
ID Code: | 2269 |
Deposited By: | Vicki Carleson |
Deposited On: | 29 Oct 2007 |
Last Modified: | 18 Nov 2009 16:03 |
Repository Staff Only: item control page