Resource-constraint project scheduling with task preemption and setup times by Boolean satisfiability encoding and satisfiability (SAT) solver
J. Vermeulen (TU Delft - Electrical Engineering, Mathematics and Computer Science)
E. Demirović – Mentor (TU Delft - Algorithmics)
Soham 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
Scheduling has been subject to much research. The resource-constrained project scheduling problem (RCPSP) is no exception. With the multiple different variations and additions to the standard definition that are possible, many exact, heuristic and meta-heuristic approaches have been proposed. One of those variations is allowing tasks in the project to be split up into smaller subsegments and scheduled at different times. The splitting of tasks is introduced to try and find project schedules that require less overall time to complete. This paper proposes a satisfiability (SAT) encoding for the RCPSP while also allowing tasks to be split. A SAT solver is used to solve the encoded problem instances and compared with the results of a heuristic algorithm. The comparison shows a lower rate of solved instances but found results are in almost all cases more optimal and proof of optimality can be provided. For applications where the sacrifice of completing tasks without splitting is only worthwhile if the absolute lowest schedule duration can be found this method provides a good alternative to other approaches.