Comparing and extending satisfiability solution methods for the resource-constrained project scheduling problem
Coelho, José
Coelho, José
Publication Type
Journal article with impact factor
Editor
Supervisor
Publication Year
2026
Journal
Computers & Operations Research
Book
Publication Volume
186
Publication Issue
Publication Begin page
Publication End page
Publication Number of pages
Collections
Abstract
This paper solves the resource-constrained project scheduling problem (RCPSP) with a satisfiability problem (SAT) solver. This paper builds further on various existing SAT models for this well-known project scheduling problem and extends them with two methods to satisfy the resource constraints. Specifically, we use the well-known minimal forbidden sets and compare them with the so-called covers that are traditionally used in SAT implementations. Moreover, we also implement an existing binary decision trees approach under various settings and extend the model with networks with adders, so far never used for solving the RCPSP, to guarantee that resource constraints are satisfied. The algorithms are tested under different settings on a set of 13,413 project instances with diverse network and resource structures, and the experiments demonstrate that a combination of these approaches help in finding better solutions within a reasonable time. Moreover, 393 new lower bounds, 62 new upper bounds, and 290 optimally solved instances (including 18 from the PSPLIB) have been discovered, which, to the best of our knowledge, had not been found before. The strong performance of the new algorithm motivated additional experiments, and the preliminary results suggest several promising directions for future research.
Research Projects
Organizational Units
Journal Issue
Keywords
Project Scheduling, Resource Constraints, Satisfiability Problem