Constraint Model-based Planning and Scheduling with Multiple Resources and Complex Collaboration Schema

摘要

In many domains, planning and scheduling problems have been considered separately. This historical decomposition leads to sub-optimal solving methods as task scheduling and planning share important sub-problems. In fact, on practical examples, there is no reason to separate coordination of activities and synchronization tasks. Furthermore, resource usage is not only relevant for task scheduling problems, but is also strongly affected by planning decisions in real-world problems. This paper proposes a Constraint Model-Based approach to concurrently tackle planning and scheduling problems. We show how constraint-based formulations can take advantage of flow models widely investigated in the operation research community. Our approach extends this model classification in order to derive both timing constraint and resource consumption for each transition of the plan. Therefore, scheduling constraints involving precedences, exclusive disjunctions, and resource capacity limit can be stated over the set of timing and resource variables. On aeronautic and spatial examples, we demonstrate how this approach enables problem-dependent specialization and increases planning and scheduling efficiency. Lastly, by using real-world problem experimentations, we show how the approach supports local / global trade-offs while designing solving methods.