SODA

Designing Global Scheduling Constraints for Local Search: A Generic Approach

Bohlin, Markus and Kocjan, Waldemar and Kreuger, Per (2002) Designing Global Scheduling Constraints for Local Search: A Generic Approach. [SICS Report]

[img]
Preview
PDF
375Kb
[img]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