Enhancing VSIDS with domain-specific information for the MRCPSP

Bachelor thesis (2024)

Authors

J. Berger Electrical Engineering, Mathematics and Computer Science

Contributors

E. Demirović Algorithmics - EEMCS (mentor)
M.L. Flippo Algorithmics - EEMCS (graduation committee member)
I.C.W.M. Marijnissen Algorithmics - EEMCS (graduation committee member)
Julia Olkhovskaya Sequential Decision Making - EEMCS (coach)
Faculty
Electrical Engineering, Mathematics and Computer Science, Electrical Engineering, Mathematics and Computer Science
More Info
expand_more

Published Date

25-06-2024

Language

English

Reuse Rights

Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.

Faculty

Electrical Engineering, Mathematics and Computer Science

Abstract

The Multi-Mode Resource Constraint Scheduling Problem is an NP-hard optimization problem. It arises in various industries such as construction engineering, transportation, and software development. This paper explores the integration of an adaptation of the Longest Processing Time heuristic to initialize the Variable State Independent Decaying Sum for the MRCPSP. This adaptation prioritizes tasks with a longer duration in all possible modes. Experimental evaluation demonstrates a 10% faster average computation time compared to default VSIDS, and the average deviation to the optimal solution is improved from 0.080% to 0.050%. These two findings combined show a minor improvement in using the LPT to initialize VSIDS values for the MRCPSP. Using the LPT also to initialize the default increment parameter, did not seem to yield any positive results.

Files

Final_Paper_Jarno_Berger.pdf
(pdf | 0.337 Mb)
Unknown license