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
G.F.L. Hellouin de Ménibus (TU Delft - Electrical Engineering, Mathematics and Computer Science)
E. Demirović – Mentor (TU Delft - Algorithmics)
M.L. Flippo – Mentor (TU Delft - Algorithmics)
K. Sidorov – Mentor (TU Delft - Algorithmics)
Jérémie Decouchant – Graduation committee member (TU Delft - Data-Intensive Systems)
More Info
expand_more
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.
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.