Exploring Heuristic Methods for the Resource-Constrained Project Scheduling Problem with Logical Constraints

Exploring Heuristic Methods for the Resource-Constrained Project Scheduling Problem with Logical Constraints

Schoenmaker, Melle (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

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.

RCPSP
RCPSP-Log
NP-Hard Algorithms
Heuristics
Encoding
SAT solver

http://resolver.tudelft.nl/uuid:f225ecc7-7360-4f7e-859e-12df9dd974b7

https://github.com/MelleSch/RP_Code_Results_RCPSP-Log A repository containing the code of the heuristic solver, SAT encoder, and results

Student theses

bachelor thesis

© 2022 Melle Schoenmaker