Polygon stacks and time reference conversions

Abstract

This paper describes how a time-based planning system, which supports resource constraints, may be extended such that a resource constraint interval does not have to refer to the start- or end-time of the underlying activity but to any linear combination thereof, such as the middle. This way, an activity with multiple resource constraints referring to different time intervals no longer has to be split into sub-activities, which may simplify the planning model and the algorithm. To be able to describe the necessary transformations, we introduce the concept of PolygonStacks and describe the operations which a typical planning engine requires to intersect the sets of consistent timeline entries of all constraints defined on an activity. We then introduce Sliders and Offsets, which allow specifying the constraint intervals in a more generic way as supported in current planning models. Based on this preparation, we can derive two lemmas, which provide the conversions required by Sliders and Offsets. We continue with several conversion examples and point out how to solve the issues which will occur during implementation. A short sketch of the complexity of our current implementation demonstrates that further work on performance should be considered, even though in practice we observe that the bottleneck of calculation remains within profile calculation rather than PolygonStack operations.