SAT-based optimisation for the resource-constrained project scheduling problem with time-dependent resource capacities and requests
J.G. Pleunes (TU Delft - Electrical Engineering, Mathematics and Computer Science)
E. Demirović – Mentor (TU Delft - Algorithmics)
S.S. Chakraborty – Graduation committee member (TU Delft - Programming Languages)
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
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.