TY - JOUR

T1 - Performance evaluation of scheduling policies for the Dynamic and Stochastic Resource-Constrained Multi-Project Scheduling Problem

AU - Satic, Ugur

AU - Jacko, Peter

AU - Kirkbride, Christopher

N1 - This is an Accepted Manuscript of an article published by Taylor & Francis in International Journal of Production Research on 26 Dec 2020, available online: https://www.tandfonline.com/doi/abs/10.1080/00207543.2020.1857450

PY - 2022/2/28

Y1 - 2022/2/28

N2 - In this study, we consider the dynamic and stochastic resource-constrained multi-project scheduling problem where projects generate rewards at their completion, completions later than a due date cause tardiness costs, task duration is uncertain, and new projects arrive randomly during the ongoing project execution both of which disturb the existing project scheduling plan. We model this problem as a discrete-time Markov decision process and explore the performance and computational limitations of solving the problem by dynamic programming. We run and compare five different solution approaches, which are: a dynamic programming algorithm to determine a policy that maximises the time-average profit, a genetic algorithm and an optimal reactive baseline algorithm, both generate a schedule to maximise the total profit of ongoing projects, a rule-based algorithm which prioritises processing of tasks with the highest processing durations, and a worst decision algorithm to seek a non-idling policy that minimises the time-average profit. The performance of the optimal reactive baseline algorithm is the closest to the optimal policies of the dynamic programming algorithm, but its results are suboptimal, up to 37.6%. Alternative scheduling algorithms are close to optimal with low project arrival probability but quickly deteriorate their performance as the probability increases.

AB - In this study, we consider the dynamic and stochastic resource-constrained multi-project scheduling problem where projects generate rewards at their completion, completions later than a due date cause tardiness costs, task duration is uncertain, and new projects arrive randomly during the ongoing project execution both of which disturb the existing project scheduling plan. We model this problem as a discrete-time Markov decision process and explore the performance and computational limitations of solving the problem by dynamic programming. We run and compare five different solution approaches, which are: a dynamic programming algorithm to determine a policy that maximises the time-average profit, a genetic algorithm and an optimal reactive baseline algorithm, both generate a schedule to maximise the total profit of ongoing projects, a rule-based algorithm which prioritises processing of tasks with the highest processing durations, and a worst decision algorithm to seek a non-idling policy that minimises the time-average profit. The performance of the optimal reactive baseline algorithm is the closest to the optimal policies of the dynamic programming algorithm, but its results are suboptimal, up to 37.6%. Alternative scheduling algorithms are close to optimal with low project arrival probability but quickly deteriorate their performance as the probability increases.

KW - dynamic

KW - stochastic

KW - resource constrained project scheduling problem

KW - dynamic programming

KW - reactive scheduling

KW - genetic algorithm

KW - scheduling policies

KW - DSRCMPSP

U2 - 10.1080/00207543.2020.1857450

DO - 10.1080/00207543.2020.1857450

M3 - Journal article

VL - 60

SP - 1411

EP - 1423

JO - International Journal of Production Research

JF - International Journal of Production Research

SN - 0020-7543

IS - 4

ER -