Loading...
Resource-constrained project scheduling with activity splitting and setup times
Vanhoucke, Mario Coelho, José
Vanhoucke, Mario
Coelho, José
Citations
Altmetric:
Publication Type
Journal article with impact factor
Editor
Supervisor
Publication Year
2019
Journal
Computers and Operations Research
Book
Publication Volume
109
Publication Issue
September
Publication Begin page
230
Publication End page
249
Publication Number of pages
Collections
Abstract
This paper presents a new solution algorithm to solve the resource-constrained project scheduling problem with activity splitting and setup times. The option of splitting activities, known as activity preemption, has been studied in literature from various angles, and an overview of the main contributions will be given. The solution algorithm makes use of a meta-heuristic search for the resource-constrained project scheduling problem (RCPSP) using network transformations to split activities in subparts. More precisely, the project network is split up such that all possible preemptive parts are incorporated into an extended network as so-called activity segments, and setup times are incorporated between the different activity segments. Due to the inherent complexity to solve the problem for such huge project networks, a solution approach is proposed that selects the appropriate activity segments and ignores the remaining segments using a boolean satisfiability problem solver, and afterwards schedules these projects to near-optimality with the renewable resource constraints. The algorithm has been tested using a large computational experiment with five types of setup times. Moreover, an extension to the problem with overlaps between preemptive parts of activities has been proposed and it is shown that our algorithm can easily cope with this extension without changing it. Computational experiments show that activity preemption sometimes leads to makespan reductions without requiring a lot of splits in the activities. Moreover, is shown that the degree of these makespan reductions depends on the network and resource indicators of the project instance.
Research Projects
Organizational Units
Journal Issue
Keywords
Project Scheduling, RCPSP, Activity Preemption, Setup Times