Integration of variable selection heuristics into a MaxSAT solver for solving the multi-mode resource-constrained project scheduling problem

Integration of variable selection heuristics into a MaxSAT solver for solving the multi-mode resource-constrained project scheduling problem

Tsvetkov, Denis (TU Delft Electrical Engineering, Mathematics and Computer Science; TU Delft Algorithmics)

Demirović, E. (mentor)
Sidorov, K. (mentor)
Flippo, M.L. (mentor)
Decouchant, Jérémie (graduation committee)

Delft University of Technology

Computer Science and Engineering

CSE3000 Research Project

2023-07-04

The multi-mode resource-constrained project scheduling problem (MRCPSP) is an extension of the resource-constrained project scheduling problem (RCPSP), which allows activities to be executed in multiple modes. The state-of-the-art solutions for solving this NP-Hard problem are dedicated algorithms and (meta-)heuristics. However, this paper considers a more flexible approach using a MaxSAT solver. The idea is to replace the existing variable selection strategy of the solver, Variable State Independent Decaying Sum (VSIDS), with two scheduling heuristics, Earliest Starting Time (EST) and Shortest Feasible Mode (SFM). We examine that combining the three heuristics results in a more efficient solver. In contrast, scheduling rules alone lead to a solver that performs significantly worse on any of the chosen metrics and benchmarks.

Algorithm
Scheduling
Heuristic
RCPSP
MRCPSP
MaxSAT

http://resolver.tudelft.nl/uuid:0c85f1d6-5471-42e7-9794-091ff7b40c40

Student theses

bachelor thesis

© 2023 Denis Tsvetkov