Improving RCPSP algorithms using machine learning methods

Abstract

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.