Combining SAT solvers with heuristic ideas for solving RCPSP with logical constraints

An exploration of variable ordering heuristics impact on solving RCPSP-log

Bachelor thesis (2023)

Authors

I.M. Tudor Electrical Engineering, Mathematics and Computer Science

Contributors

E. Demirović Algorithmics - EEMCS (supervisor 1)
K. Sidorov Algorithmics - EEMCS (supervisor 1)
M.L. Flippo Algorithmics - EEMCS (supervisor 1)
Jérémie Decouchant Data-Intensive Systems - EEMCS (supervisor 2)
Faculty
Electrical Engineering, Mathematics and Computer Science
Copyright: © 2023 Iarina Tudor
Heuristics RCPSP-Log NP-Hard Algorithms SAT solver
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 provides a novel method of solving the resource-constrained project scheduling problem (RCPSP) with logical constraints (RCPSP-log) using satisfiability (SAT) solving and integrating variable selection heuristics. The extension provides two additional precedences: OR constraints and bidirectional (BI) relations, making it possible to express more complex dependencies between tasks. OR constraints enable a task to be dependent on multiple preceding tasks, while BI relations do not allow tasks to be executed at the same time. Both problems are known to be NP-hard.

The solution method consists of using a max satisfiability (MaxSAT) solver combined with variable selection heuristics. The paper investigates two heuristics, based on the greedy approach of scheduling each activity as early as possible and variable conflict analysis.

The results on well-known datasets from the literature show that most of the instances can be solved within the designated time limit. The proposed approaches contribute to reducing the makespan, especially when dealing with no logical constraints or only OR relations. For BI constraints, the algorithm is having difficulties in finding solutions, especially when increasing the number of activities, reporting fewer solutions than the baselines. Overall, the results provide insight into the integration of variable selection heuristics for SAT solving, with the potential for more investigation into problem-specific ideas.

Files

Final_Paper_RP.pdf
(.pdf | 0.376 Mb)