%0 Journal Article
%J Artificial Intelligence
%D 2014
%T CROSS cyclic resource-constrained scheduling solver
%A Alessio Bonfietti
%A Michele Lombardi
%A Luca Benini
%A Michela Milano
%K Constraint Programming
%K Cumulative constraint
%K Cyclic scheduling problem
%K Filtering algorithm
%P 25–52
%U http://www.sciencedirect.com/science/article/pii/S0004370213001057
%V 206
%X Cyclic scheduling problems consist in ordering a set of activities executed indefinitely over time in a periodic fashion, subject to precedence and resource constraints. This class of problems has many applications in manufacturing, embedded systems and compiler design, production and chemical systems. This paper proposes a Constraint Programming approach for cyclic scheduling problems, based on modular arithmetic: in particular, we introduce a modular precedence constraint and a global cumulative constraint along with their filtering algorithms. We discuss two possible formulations. The first one (referred to as CROSS) models a pure cyclic scheduling problem and makes use of both our novel constraints. The second formulation (referred to as CROSS⁎) introduces a restrictive assumption to enable the use of classical resources constraints, but may incur a loss of solution quality. Many traditional approaches to cyclic scheduling operate by fixing the period value and then solving a linear problem in a generate-and-test fashion. Conversely, our technique is based on a non-linear model and tackles the problem as a whole: the period value is inferred from the scheduling decisions. Our approach has been tested on a number of non-trivial synthetic instances and on a set of realistic industrial instances. The method proved to effective in finding high quality solutions in a very short amount of time.