TY - GEN

T1 - Performance evaluation of scheduling policies for the DRCMPSP

AU - Satic, Ugur

AU - Jacko, Peter

AU - Kirkbride, Christopher

N1 - The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-030-62885-7_8

PY - 2020/11/7

Y1 - 2020/11/7

N2 - In this study, we consider the dynamic resource-constrained multi-project scheduling problem (DRCMPSP) where projects generate rewards at their completion, completions later than a due date cause tardiness costs and new projects arrive randomly during the ongoing project execution which disturbs the existing project scheduling plan. We model this problem as a discrete Markov decision process and explore the computational limitations of solving the problem by dynamic programming. We run and compare four different solution approaches on small size problems. These solution approaches are: a dynamic programming algorithm to determine a policy that maximises the average profit per unit time net of charges for late project completion, a genetic algorithm which generates a schedule to maximise the total reward of ongoing projects and updates the schedule with each new project arrival, a rule-based algorithm which prioritise processing of tasks with the highest processing durations, and a worst decision algorithm to seek a non-idling policy to minimise the average profit per unit time. Average profits per unit time of generated policies of the solution algorithms are evaluated and compared. The performance of the genetic algorithm is the closest to the optimal policies of the dynamic programming algorithm, but its results are notably suboptimal, up to 67.2\%. 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 resource-constrained multi-project scheduling problem (DRCMPSP) where projects generate rewards at their completion, completions later than a due date cause tardiness costs and new projects arrive randomly during the ongoing project execution which disturbs the existing project scheduling plan. We model this problem as a discrete Markov decision process and explore the computational limitations of solving the problem by dynamic programming. We run and compare four different solution approaches on small size problems. These solution approaches are: a dynamic programming algorithm to determine a policy that maximises the average profit per unit time net of charges for late project completion, a genetic algorithm which generates a schedule to maximise the total reward of ongoing projects and updates the schedule with each new project arrival, a rule-based algorithm which prioritise processing of tasks with the highest processing durations, and a worst decision algorithm to seek a non-idling policy to minimise the average profit per unit time. Average profits per unit time of generated policies of the solution algorithms are evaluated and compared. The performance of the genetic algorithm is the closest to the optimal policies of the dynamic programming algorithm, but its results are notably suboptimal, up to 67.2\%. Alternative scheduling algorithms are close to optimal with low project arrival probability but quickly deteriorate their performance as the probability increases.

KW - Dynamic programming

KW - Resource constraint

KW - Project scheduling

KW - DRCMPSP

U2 - 10.1007/978-3-030-62885-7_8

DO - 10.1007/978-3-030-62885-7_8

M3 - Conference contribution/Paper

SN - 9783030628840

T3 - Lecture Notes in Computer Science

SP - 100

EP - 114

BT - Analytical and Stochastic Modelling Techniques and Applications

PB - Springer

CY - Cham

T2 - The 25th International Conference on Analytical & Stochastic Modelling Techniques & Applications

Y2 - 21 October 2019 through 25 October 2019

ER -