The preemptive stochastic resource-constrained project scheduling problem: an efficient globally optimal solution procedure

Stefan Creemers

No 553966, Working Papers of Department of Decision Sciences and Information Management, Leuven from KU Leuven, Faculty of Economics and Business (FEB), Department of Decision Sciences and Information Management, Leuven

Abstract: We present a globally optimal solution procedure to tackle the preemptive stochastic resource-constrained project scheduling problem (PSRCPSP). A solution to the PSRCPSP is a policy that allows to construct a precedence- and resource-feasible schedule that minimizes the expected makespan of a project. The PSRCPSP is an extension of the stochastic resource-constrained project scheduling problem (SRCPSP) that allows activities to be interrupted. The SRCPSP and PSRCPSP both assume that activities have stochastic durations. Even though the deterministic preemptive resource-constrained project scheduling problem (PRCPSP) has received some attention in the literature, we are the first to study the PSRCPSP. We use phase-type distributions to model the stochastic activity durations, and define a new Continuous-Time Markov Chain (CTMC) that drastically reduces memory requirements when compared to the well-known CTMC of Kulkarni and Adlakha (1986). In addition, we also propose a new and efficient approach to structure the state space of the CTMC. These improvements allow us to easily outperform the current state-of-the-art in optimal project scheduling procedures, and to solve instances of the PSPLIB J90 and J120 data sets. Last but not least, if activity durations are exponentially distributed, we show that elementary policies are globally optimal for the SRCPSP and the PSRCPSP.

Keywords: Project management; Continuous-time Markov chain; PSRCPSP (search for similar items in EconPapers)
Date: 2016-10
New Economics Papers: this item is included in nep-cmp
References: Add references at CitEc
Citations:

Published in FEB Research Report KBI_1626

Downloads: (external link)
https://lirias.kuleuven.be/retrieve/408938 The preemptive stochastic resource-constrained project scheduling problem: an efficient globally optimal solution procedure (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:ete:kbiper:553966

Access Statistics for this paper

More papers in Working Papers of Department of Decision Sciences and Information Management, Leuven from KU Leuven, Faculty of Economics and Business (FEB), Department of Decision Sciences and Information Management, Leuven
Bibliographic data for series maintained by library EBIB ().