Robust Solutions for the Resource-Constrained Project Scheduling Problem: Understanding and Improving Robustness in Partial Order Schedules produced by the Chaining algorithm

Robust Solutions for the Resource-Constrained Project Scheduling Problem: Understanding and Improving Robustness in Partial Order Schedules produced by the Chaining algorithm

Wilmer, D.

Klos, T.B. (mentor)
Witteveen, C. (mentor)

Electrical Engineering, Mathematics and Computer Science

Software Technology

2015-01-20

Robustness is essential for schedules if they are being executed under uncertain conditions. In this thesis we research robustness in Partial Order Schedules, which represent sets of solutions for instances of the Resource-Constrained Project Scheduling Problem. They can be generated using a greedy procedure called Chaining, which can be easily adapted to use various heuristics. We use an empirical method to gain understanding of robustness and how the chaining procedure adds to this. Based on the findings of an exploratory study we develop three models, each capturing aspects of robustness on a different level. The first model describes how a single activity is affected by various disturbances. The second model predicts how structural properties of Partial Order Schedules can reduce the effect of these disturbances. The third model describes how heuristics for the chaining procedure can influence these properties. Using experimental evaluation, we found that the model is not complete. Experimental results did conform to the expectations set by the third model, but not of the second model. We therefore suspect that it is too simplistic for accurate predictions, but since it does match earlier observations we believe it is a good starting point for further understanding.

scheduling
RCPSP
robustness
Resource Constraint Project Scheduling Problem
project scheduling

http://resolver.tudelft.nl/uuid:f403f220-e233-4f9f-8602-584d928adfc8

Student theses

master thesis

(c) 2015 Wilmer, D.