Constraint model-based planning and scheduling with multiple resources and complex collaboration schema
Christophe Guettier, B. Allo, V. Legendre, J.-C. Poncet, N. Strady-Lécubin · 2002
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 practi-cal 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 ap-proach to concurrently tackle planning and scheduling prob-lems. We show how constraint-based formulations can take advantage of flow models widely investigated in the opera-tion research community. Our approach extends this model classification in order to derive both timing constraint and re-source consumption for each transition of the plan. There-fore, 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.