Improving PCP algorithms using flexibility metrics

Abstract

In this work we improve on existing scheduling techniques suitable for scheduling problems at the train maintenance provider, NedTrain. Scheduling problems that require flexible solutions can be modeled using variations of the Resource Constraint Project Scheduling Problem (RCPSP), which can be solved using Precedence Constraint Posting (PCP). Earlier work already showed that PCP is able to create fixed-time schedules for NetTrain. In this work we investigate two variations of PCP for creating flexible schedules. The envelope approach, where the problem instance is directly reduced to a flexible solution and the `solve and robustify' approach, where a fixed inflexible schedule is created and then relaxed to create a flexible schedule. Using state of the art flexibility metrics and Interval Schedules we show that the envelope approach, which has been considered the weaker approach in recent literature, can be greatly improved. By using Interval Schedules to remove temporal interaction between tasks we were able to estimate resource violations much more accurately, improving the flexibility of the resulting schedules.