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

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.CSE3000 Research ProjectComputer Science and Engineerin