Change search
ReferencesLink to record
Permanent link

Direct link
Designing Global Scheduling Constraints for Local Search: A Generic Approach
Number of Authors: 3
2002 (English)Report (Refereed)
Abstract [en]

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.

Place, publisher, year, edition, pages
Swedish Institute of Computer Science , 2002, 1. , 29 p.
Series
SICS Technical Report, ISSN 1100-3154 ; 2002:20
Keyword [en]
Local Search, Global Constraints, Scheduling
National Category
Computer and Information Science
Identifiers
URN: urn:nbn:se:ri:diva-21994OAI: oai:DiVA.org:ri-21994DiVA: diva2:1041536
Available from: 2016-10-31 Created: 2016-10-31

Open Access in DiVA

fulltext(375 kB)3 downloads
File information
File name FULLTEXT01.pdfFile size 375 kBChecksum SHA-512
d57043d264f4fc435272c45993eb5046bc1b41832ca09ac29c9fe448055262749c7d7a6e53d4db5119adc90e0b6dd79268ffadb34c528beb640c0942c8c9f2eb
Type fulltextMimetype application/pdf

Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 3 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 3 hits
ReferencesLink to record
Permanent link

Direct link