Analysis of a time–cost trade-off in a resource-constrained GERT project scheduling problem using the Markov decision process

Nowadays the advent of new types of projects such as startups, maintenance, and education make a revolution in project management, so that, classical project scheduling methods are incapable in analyzing of these stochastic projects. This study considers a time–cost trade-off project scheduling problem, where the structure of the project is uncertain. To deal with the uncertainties, we implemented Graphical Evaluation and Review Technique (GERT). The main aim of the study is to balance time and the amount of a non-renewable resource allocated to each activity considering the finite-time horizon and resource limitations. To preserve the generality of the model, we considered both discrete and continuous distribution functions for the activity’s duration. From a methodological standpoint, we proposed an analytical approach based on the Markov Decision Process (MDP) and Semi-Markov Decision Process (SMDP) to find the probability distribution of project makespan. These models are solved using the value iteration and a finite-horizon Linear Programming (LP) model. Two randomly generated examples explain the value iteration for models in detail. Furthermore, seven example groups each with five instances are adopted from a well-known data set, PSPLIB, to validate the efficiency of the proposed models in contrast to the two extensively-studied methods, Genetic algorithm (GA) and Monte-Carlo simulation. The convergence of the GA and simulation results to those of MDP and SMDP represent the efficiency of the proposed models. Besides, conducting a sensitivity analysis on the project completion probability with respect to the available resource, gives a good insight to managers to plan their resources.