article

Minimizing the expected makespan of a project with stochastic activity durations under resource constraints

Author:

Stefan CreemersAuthors Info & Claims

Journal of Scheduling, Volume 18, Issue 3

Pages 263 - 273

https://doi.org/10.1007/s10951-015-0421-5

Published: 01 June 2015 Publication History

Abstract

The resource-constrained project scheduling problem (RCPSP) has been widely studied. A fundamental assumption of the basic type of RCPSP is that activity durations are deterministic (i.e., they are known in advance). In reality, however, this is almost never the case. In this article, we illustrate why it is important to incorporate activity duration uncertainty, and develop an exact procedure to optimally solve the stochastic resource-constrained scheduling problem. A computational experiment shows that our approach works best when solving small- to medium-sized problem instances where activity durations have a moderate-to-high level of variability. For this setting, our model outperforms the existing state-of-the-art. In addition, we use our model to assess the optimality gap of existing heuristic approaches, and investigate the impact of making scheduling decisions also during the execution of an activity rather than only at the end of an activity.

References

[1]

Ashtiani, B., Leus, R., & Aryanezhad, M. B. (2011). New competitive results for the stochastic resource-constrained project scheduling problem: Exploring the benefits of pre-processing. Journal of Scheduling, 14(2), 157-171.

Digital Library

[2]

Ballestín, F. (2007). When it is worthwhile to work with the stochastic RCPSP? Journal of Scheduling, 10(3), 153-166.

Digital Library

[3]

Ballestín, F., & Leus, R. (2009). Resource-constrained project scheduling for timely project completion with stochastic activity durations. Production and Operations Management, 18(4), 459-474.

[4]

Bidot, J., Vidal, T., Laborie, P., & Beck, J. C. (2009). A theoretic and practical framework for scheduling in a stochastic environment. Journal of Scheduling, 12(3), 315-344.

Digital Library

[5]

Buss, A. H., & Rosenblatt, M. J. (1997). Activity delay in stochastic project networks. Operations Research, 45(1), 126-139.

Digital Library

[6]

Creemers, S., Leus, R., & Lambrecht, M. (2010). Scheduling Markovian PERT networks to maximize the net present value. Operations Research Letters, 38(1), 51-56.

Digital Library

[7]

Creemers, S., Demeulemeester, E., & Van de Vonder, S. (2014). A new approach for quantitative risk analysis. Annals of Operations Research, 213(1), 27-65.

[8]

Demeulemeester, E., & Herroelen, W. (2002). Project scheduling: A research handbook. AH Dordrecht: Kluwer Academic Publishers Group.

[9]

Fu, N., Lau, H. C., Varakantham, P., & Xiao, F. (2012). Robust local search for solving RCPSP/max with durational uncertainty. Journal of Artificial Intelligence Research, 43, 43-86.

Digital Library

[10]

Golenko-Ginzburg, D., & Gonik, A. (1997). Stochastic network project scheduling with non-consumable limited resources. International Journal of Production Economics, 48(1), 29-37.

[11]

Herroelen, W., & Leus, R. (2005). Project scheduling under uncertainty: Survey and research potentials. European Journal of Operational Research, 165(2), 289-306.

[12]

Igelmund, G., & Radermacher, F. J. (1983). Preselective strategies for the optimization of stochastic project networks under resource constraints. Networks, 13(1), 1-28.

[13]

Kolisch, R., & Sprecher, A. (1996). PSPLIB--A project scheduling problem library. European Journal of Operational Research, 96(1), 205-216.

[14]

Kulkarni, V., & Adlakha, V. (1986). Markov and Markov-regenerative PERT networks. Operations Research, 34(5), 769-781.

Digital Library

[15]

Latouche, G., & Ramaswami, V. (1999). Introduction to matrix analytic methods in stochastic modeling. Philadelphia: American Statistical Association and the Society for Industrial and Applied Mathematics.

[16]

Möhring, R. H. (2000). Scheduling under uncertainty: Optimizing against a randomizing adversary. Lecture Notes in Computer Science, 1913, 15-26.

[17]

Neumann, K., Schwindt, C., & Zimmermann, J. (2003). Project scheduling with time windows and scarce resources. Berlin: Springer.

[18]

Neuts, M. F. (1981). Matrix-geometric solutions in stochastic models. Baltimore: Johns Hopkins University Press.

[19]

Osogami, T. (2005). Analysis of multiserver systems via dimensionality reduction of Markov chains. PhD Thesis, Carnegie Mellon University.

[20]

Patterson, J. H. (1984). A comparison of exact approaches for solving the multiple constrained resource, project scheduling problem. Management Science, 30(7), 854-867.

Digital Library

[21]

Sobel, M. J., Szmerekovsky, J. G., & Tilson, V. (2009). Scheduling projectswith stochastic activity duration tomaximize expected net present value. European Journal of Operational Research, 198(1), 697-705.

[22]

Stork, F. (2001). Stochastic resource-constrained project scheduling. PhD Thesis, Technische Universität Berlin.

[23]

Tsai, Y.-W., & Gemmill, D. D. (1998). Using tabu search to schedule activities of stochastic resource-constrained projects. European Journal of Operational Research, 111(1), 129-141.

Cited By

Tian BZhang JDemeulemeester ELiu H(2024)A chance-constrained optimization approach integrating project scheduling and material ordering to manage the uncertain material supplyComputers and Operations Research10.1016/j.cor.2024.106624166:COnline publication date: 1-Jun-2024
https://dl.acm.org/doi/10.1016/j.cor.2024.106624
Patra SPathan MMahfouz MZehtabi POuaja WMagazzeni DVeloso M(2024)Capacity planning and scheduling for jobs with uncertainty in resource usage and durationThe Journal of Supercomputing10.1007/s11227-024-06282-880:15(22428-22461)Online publication date: 1-Oct-2024
https://dl.acm.org/doi/10.1007/s11227-024-06282-8
Rezaei FNajafi ARamezanian RDemeulemeester E(2022)Simulation-based priority rules for the stochastic resource-constrained net present value and risk problemComputers and Industrial Engineering10.1016/j.cie.2021.107607160:COnline publication date: 22-Apr-2022
https://dl.acm.org/doi/10.1016/j.cie.2021.107607
Show More Cited By

Index Terms

Minimizing the expected makespan of a project with stochastic activity durations under resource constraints
1. Computing methodologies
  1. Artificial intelligence
    1. Search methodologies
      1. Heuristic function construction
2. Theory of computation
  1. Design and analysis of algorithms
    1. Approximation algorithms analysis
      1. Scheduling algorithms
    2. Online algorithms
      1. Online learning algorithms
        Scheduling algorithms
  2. Theory and algorithms for application domains
    1. Machine learning theory
      1. Reinforcement learning
        Sequential decision making

Index terms have been assigned to the content through auto-classification.

Recommendations

Metaheuristics for minimizing the makespan of the dynamic shop scheduling problem

For the shop scheduling problems such as flow-shop, job-shop, open-shop, mixed-shop, and group-shop, most research focuses on optimizing the makespan under static conditions and does not take into consideration dynamic disturbances such as machine ...
New strategies for stochastic resource-constrained project scheduling

We study the stochastic resource-constrained project scheduling problem or SRCPSP, where project activities have stochastic durations. A solution is a scheduling policy, and we propose a new class of policies that is a generalization of most of the ...
An Artificial Immune Algorithm for the project scheduling problem under resource constraints

The Resource Constrained Project Scheduling Problem (RCPSP) is one of the most challenging problems in the field of scheduling and combinatorial optimization. This paper deals with the RCPSP considering the makespan minimization as the objective. Due to ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of Scheduling

Journal of Scheduling Volume 18, Issue 3

June 2015

100 pages

ISSN:1094-6136

Issue’s Table of Contents

Copyright © Copyright © 2015 Springer Science+Business Media New York.

Publisher

Kluwer Academic Publishers

United States

Publication History

Published: 01 June 2015

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

11
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 04 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

Tian BZhang JDemeulemeester ELiu H(2024)A chance-constrained optimization approach integrating project scheduling and material ordering to manage the uncertain material supplyComputers and Operations Research10.1016/j.cor.2024.106624166:COnline publication date: 1-Jun-2024
https://dl.acm.org/doi/10.1016/j.cor.2024.106624
Patra SPathan MMahfouz MZehtabi POuaja WMagazzeni DVeloso M(2024)Capacity planning and scheduling for jobs with uncertainty in resource usage and durationThe Journal of Supercomputing10.1007/s11227-024-06282-880:15(22428-22461)Online publication date: 1-Oct-2024
https://dl.acm.org/doi/10.1007/s11227-024-06282-8
Rezaei FNajafi ARamezanian RDemeulemeester E(2022)Simulation-based priority rules for the stochastic resource-constrained net present value and risk problemComputers and Industrial Engineering10.1016/j.cie.2021.107607160:COnline publication date: 22-Apr-2022
https://dl.acm.org/doi/10.1016/j.cie.2021.107607
Zhao SXu Z(2021)New closed-loop approximate dynamic programming for solving stochastic decentralized multi-project scheduling problem with resource transfersExpert Systems with Applications: An International Journal10.1016/j.eswa.2021.115593185:COnline publication date: 15-Dec-2021
https://dl.acm.org/doi/10.1016/j.eswa.2021.115593
Chen HDing GQin SZhang J(2021)A hyper-heuristic based ensemble genetic programming approach for stochastic resource constrained project scheduling problemExpert Systems with Applications: An International Journal10.1016/j.eswa.2020.114174167:COnline publication date: 30-Dec-2021
https://dl.acm.org/doi/10.1016/j.eswa.2020.114174
Song WKang DZhang JCao ZXi H(2019)A sampling approach for proactive project scheduling under generalized time-dependent workability uncertaintyJournal of Artificial Intelligence Research10.1613/jair.1.1136964:1(385-427)Online publication date: 1-Jan-2019
https://dl.acm.org/doi/10.1613/jair.1.11369
Kosztyán ZSzalkai I(2019)Multimode resource-constrained project scheduling in flexible projectsJournal of Global Optimization10.1007/s10898-019-00832-876:1(211-241)Online publication date: 4-Oct-2019
https://dl.acm.org/doi/10.1007/s10898-019-00832-8
Song WKang DZhang JXi HMcIlraith SWeinberger K(2018)Risk-aware proactive scheduling via conditional value-at-riskProceedings of the Thirty-Second AAAI Conference on Artificial Intelligence and Thirtieth Innovative Applications of Artificial Intelligence Conference and Eighth AAAI Symposium on Educational Advances in Artificial Intelligence10.5555/3504035.3504804(6278-6285)Online publication date: 2-Feb-2018
https://dl.acm.org/doi/10.5555/3504035.3504804
Li QTao SChong HDong Z(2018)Robust Optimization for Integrated Construction Scheduling and Multiscale Resource AllocationComplexity10.1155/2018/26979852018Online publication date: 24-Jul-2018
https://dl.acm.org/doi/10.1155/2018/2697985
Zaman FElsayed SSarker REssam D(2018)Scenario-Based Solution Approach for Uncertain Resource Constrained Scheduling Problems2018 IEEE Congress on Evolutionary Computation (CEC)10.1109/CEC.2018.8477756(1-8)Online publication date: 8-Jul-2018
https://dl.acm.org/doi/10.1109/CEC.2018.8477756
Show More Cited By

View Options

View options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents