کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
376904 658333 2014 18 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Filtering AtMostNValue with difference constraints: Application to the shift minimisation personnel task scheduling problem
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر هوش مصنوعی
پیش نمایش صفحه اول مقاله
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 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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Artificial Intelligence - Volume 212, July 2014, Pages 116–133
نویسندگان
, ,