Improving RCPSP algorithms using machine learning methods

Improving RCPSP algorithms using machine learning methods

Verburg, Floris (TU Delft Electrical Engineering, Mathematics and Computer Science; TU Delft Algorithmics)

de Weerdt, Mathijs (mentor)
Yorke-Smith, Neil (graduation committee)
Verwer, Sicco (graduation committee)

Delft University of Technology

2018-06-21

For performing technical maintenance, it is important to keep a detailed schedule of resources and temporal constraints. The Resource Constrained Project Scheduling Problem (RCPSP) is a well de- fined scheduling model with both resources and temporal constraints. Precedence Constraint Posting (PCP) is a technique to solve the NP-hard RCPSP problem, that currently uses heuristics for making decisions for selecting and resolving conflicts. Our work focuses on improving the quality of the solutions for PCP by replacing these heuristics by a machine learning classifier. In this work, several datasets are generated that are used for training classifiers. The performance of the PCP solver when replacing the heuristics with these classifiers is comparable with the performance of the solver when using heuristics, but on average it is slightly worse than the best performing heuristics. After implement- ing Monte Carlo simulation, we concluded that there was a slight, but statistically significant decrease in average makespan when using the machine learning classifiers for simulating the behaviour of the solver compared to the average makespan when using random heuristics for simulating the behaviour of the solver. However, future research is needed to further improve the performance of the machine learning classifiers, for which we propose a list of improvements based on our observations.

Scheduling
Maintenance scheduling
Resource Constrained Project Scheduling Problem
Precedence Constraint Posting
Machine learning
Monte Carlo simulation

http://resolver.tudelft.nl/uuid:82c2c44b-c3d6-4d9a-9b2f-49a0f71eb1a3

Student theses

master thesis

© 2018 Floris Verburg