Exploring Heuristic Methods for the Resource-Constrained Project Scheduling Problem with Logical Constraints
M. Schoenmaker (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
A repository containing the code of the heuristic solver, SAT encoder, and results
https://github.com/MelleSch/RP_Code_Results_RCPSP-LogOther 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
This paper presents the use of a heuristic solution method to improve the process of creating a conjunctive normal form (CNF) encoding of and finding optimal solutions to instances of the resource-constrained project scheduling problem with logical constraints (RCPSP-Log).
The RCPSP is an optimisation problem consisting of a set of resources with constant availability per time period, a set of activities with a duration and resource consumption rate, and a set of AND precedence relation pairs (i, j); activity j can start only if activity i has finished. The goal is to construct a schedule that minimises the total duration (makespan) of the project while satisfying all resource and precedence constraints. RCPSP-Log extends RCPSP by introducing two types of precedence relations OR and BI. OR relations allow a successor to be scheduled when at least one of its predecessors has finished. The BI relation prevents two jobs from running in parallel. The RCPSP is known to be NP-hard, thus the same holds for this extension.
To find solutions to the RCPSP-Log, activities can be assigned a priority value based on a heuristic function. The heuristic function makes use of the critical path method to calculate the latest finishing time (LFT) of an activity. By using the heuristic greedily a feasible sub-optimal solution is generated for a problem instance, which is then used to reduce the size of the instance's CNF encoding.
A maximum satisfiability (MaxSAT) solving algorithm is used to search for a variable assignment for the CNF encoded problem and to prove whether it has an optimal makespan while satisfying all precedence and resource constraints.
The computational results of encoding and solving RCPSP instances from a well-known dataset with both the standard and the reduced encoding show that there is a clear advantage to using a heuristic algorithm, in terms of the time needed to find optimal solutions, to provide a starting point to the SAT solver.