Improving PCP algorithms using flexibility metrics: Creating flexible schedules for Technical Maintenance

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.

Subject

scheduling
project scheduling
Precedence Constraint Posting
flexibility
Resource Constraint Project Scheduling Problem
RCPSP
NedTrain

To reference this document use:

http://resolver.tudelft.nl/uuid:8e4af95a-1c03-4c0d-80c7-64b82a7ef649

Embargo date

2014-03-26

Part of collection

Student theses

Document type

master thesis

Rights

Files

PDF

thesis1.0.2.pdf

1.63 MB

Close viewer