SAT-based optimisation for the resource-constrained project scheduling problem with time-dependent resource capacities and requests

SAT-based optimisation for the resource-constrained project scheduling problem with time-dependent resource capacities and requests

Pleunes, Jelle (TU Delft Electrical Engineering, Mathematics and Computer Science)

Demirović, E. (mentor)
Chakraborty, S.S. (graduation committee)

Delft University of Technology

Computer Science and Engineering

CSE3000 Research Project

2022-06-23

In this paper, a variant of the resource-constrained project scheduling problem is discussed. This variant introduces time-dependence for resource capacities and requests, making the problem a more realistic model for many practical applications such as production scheduling and medical research project planning. The main aim of this paper is to define a Boolean satisfiability (SAT) formulation for this variant, such that schedules with a minimal total duration can be found efficiently using a SAT solver. We introduce such a formulation which is then used to implement an exact solving approach, of which performance is compared to another approach based on satisfiability modulo theories (SMT). Our experiments show that the SAT-based approach is efficient, in that it outperforms the SMT-based approach for test instances with a larger amount of activities.

Resource-Constrained Project Scheduling Problem
SAT solver
NP-hard problems
Combinatorial Optimization
Algorithms
Heuristics
SMT solver

http://resolver.tudelft.nl/uuid:698692ab-3a12-4a66-ae6a-214d77d4a013

Student theses

bachelor thesis

© 2022 Jelle Pleunes