Skip to main content

Global Cyclic Cumulative Constraint

Posted in
TitleGlobal Cyclic Cumulative Constraint
Publication TypeConference Paper
Year of Publication2012
AuthorsBonfietti, A., M. Lombardi, L. Benini, and M. Milano
Conference NameProceedings of CPAIOR
Abstract

This paper proposes a global cumulative constraint for cyclic scheduling problems. In cyclic scheduling a project graph is periodically re-executed on a set of limited capacity resources. The objective is to find an assignment of start times to activities such that the feasible repetition period λ is minimized. Cyclic scheduling is an effective method to maximally exploit available resources by partially overlapping sched- ule repetitions. In our previous work, we have proposed a modular precedence constraint along with its filtering algorithm. The approach was based on the hypothesis that the end times of all activities should be assigned within the period: this allows the use of traditional resource constraints, but may introduce resource inefficiency. The adverse effects are particularly relevant for long activity durations and high resource availability. By relaxing this restriction, the problem becomes much more complicated and specific resource constrained filtering algorithms should be devised. Here, we introduce a global cumulative constraint based on modular arithmetic, that does not require the end times to be within the period. We show the advantages obtained for specific scenarios in terms of solution quality with respect to our previous approach, that was already superior with respect to state of the art techniques.

Resources
Publicly Accessible Resources: