Result: Inter-distance constraint : An extension of the all-different constraint for scheduling equal length jobs

Title:
Inter-distance constraint : An extension of the all-different constraint for scheduling equal length jobs
Authors:
ARTIOUCHINE, Konstantin, BAPTISTE, Philippe
Source:
Principles and practice of constraint programming - CP 2005 (11th international conference, CP 2005, Sitges, Spain, October 1-5, 2005, proceedings)Lecture notes in computer science. :62-76
Publisher Information:
New York, NY: Springer, 2005.
Publication Year:
2005
Physical Description:
print, 24 ref 1
Original Material:
INIST-CNRS
Subject Terms:
Computer science, Informatique, Sciences exactes et technologie, Exact sciences and technology, Sciences appliquees, Applied sciences, Informatique; automatique theorique; systemes, Computer science; control theory; systems, Intelligence artificielle, Artificial intelligence, Résolution de problèmes, jeux, Problem solving, game playing, Arithmétique intervalle, Interval arithmetic, Aritmética intervalo, Atelier multigamme, Job shop, Charge travail, Workload, Carga trabajo, Complexité algorithme, Algorithm complexity, Complejidad algoritmo, Gestion tâche, Task scheduling, Gestión labor, Optimisation sous contrainte, Constrained optimization, Optimización con restricción, Ordonnancement, Scheduling, Reglamento, Satisfaction contrainte, Constraint satisfaction, Satisfaccion restricción, Contrainte globale, Propagation contrainte
Document Type:
Conference Conference Paper
File Description:
text
Language:
English
Author Affiliations:
CNRS LIX, Ecole Polytechnique, 91128 Palaiseau, France
Thales TRT, Domaine de Corbeville, 91404 Orsay, France
ISSN:
0302-9743
Access URL:
http://pascal-francis.inist.fr/vibad/index.php?action=search&terms=17324901
Rights:
Copyright 2006 INIST-CNRS
CC BY 4.0
Sauf mention contraire ci-dessus, le contenu de cette notice bibliographique peut être utilisé dans le cadre d’une licence CC BY 4.0 Inist-CNRS / Unless otherwise stated above, the content of this bibliographic record may be used under a CC BY 4.0 licence by Inist-CNRS / A menos que se haya señalado antes, el contenido de este registro bibliográfico puede ser utilizado al amparo de una licencia CC BY 4.0 Inist-CNRS
Notes:
Computer science; theoretical automation; systems
Accession Number:
edscal.17324901
Database:
PASCAL Archive

Further Information

We study a global constraint, the inter-distance constraint that ensures that the distance between any pair of variables is at least equal to a given value. When this value is 1, the inter-distance constraint reduces to the all-different constraint. We introduce an algorithm to propagate this constraint and we show that, when domains of the variables are intervals, our algorithm achieves arc-B-consistency. It provides tighter bounds than generic scheduling constraint propagation algorithms (like edge-finding) that could be used to capture this constraint. The worst case complexity of the algorithm is cubic but it behaves well in practice and it drastically reduces the search space. Experiments on special Job-Shop problems and on an industrial problem are reported.