Filtering AtMostNValue with difference constraints: Application to the shift minimisation personnel task scheduling problem

The problem of minimising the number of distinct values among a set of variables subject to difference constraints occurs in many real-life contexts. This is the case of the Shift Minimisation Personnel Task Scheduling Problem, introduced by Krishnamoorthy et al., which is used as a case study all a...

Full description

Saved in:
Bibliographic Details
Published in:Artificial intelligence 2014-07, Vol.212, p.116-133
Main Authors: Fages, Jean-Guillaume, Lapègue, Tanguy
Format: Article
Language:English
Subjects:
Applied sciences
AtMostNValue
Cognitive science
Computer science
Constraint-Programming
Exact sciences and technology
Firm modelling
Global constraints
Mathematical programming
Operational research and scientific management
Operational research. Management science
Scheduling, sequencing
Shift Minimisation Personnel Task Scheduling Problem
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The problem of minimising the number of distinct values among a set of variables subject to difference constraints occurs in many real-life contexts. This is the case of the Shift Minimisation Personnel Task Scheduling Problem, introduced by Krishnamoorthy et al., which is used as a case study all along this paper. Constraint-Programming enables to formulate this problem easily, through several AllDifferent constraints and a single AtMostNValue constraint. However, the independence of these constraints results in a poor lower bounding, hence a difficulty to prove optimality. This paper introduces a formalism to describe a family of propagators for AtMostNValue. In particular, we provide simple but significant improvement of the state-of-the-art AtMostNValue propagator of Bessière et al., to filter the conjunction of an AtMostNValue constraint and disequalities. In addition, we provide an original search strategy which relies on constraint reification. Extensive experiments show that our contribution significantly improves a straightforward model, so that it competes with the best known approaches from Operational Research.
ISSN:0004-3702
1872-7921
DOI:10.1016/j.artint.2014.04.001