Why Midas would be a terrible secretary

Using a greedy approach to enhance SAT for the Preemptive Resource-Constrained project scheduling problem with set up time

Bachelor thesis (2023)

Authors

G.F.L. Hellouin de Ménibus Electrical Engineering, Mathematics and Computer Science

Contributors

E. Demirović Algorithmics - EEMCS (supervisor 1)
M.L. Flippo Algorithmics - EEMCS (supervisor 1)
K. Sidorov Algorithmics - EEMCS (supervisor 1)
Jérémie Decouchant Data-Intensive Systems - EEMCS (supervisor 2)
Faculty
Electrical Engineering, Mathematics and Computer Science
Copyright: © 2023 George Hellouin de Ménibus
More Info
expand_more

Published Date

04-07-2023

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

This paper presents a new greedy heuristic to extend SAT Solvers when solving the Preemptive resource-constrained project scheduling problem (PRCPSP-ST). The heuristic uses domain-specific knowledge to generate a fixed order of variable selection. We also extend previous work into encoding PRCPSP-ST by providing an alternative upper bound. The heuristic was tested against VSDIS on the J12 dataset. These experiments show that it performed, on average, six times slower than VSDIS.

Files

Final_Paper_4.pdf
(.pdf | 0.189 Mb)