Nothing Special   »   [go: up one dir, main page]

Skip to main content
Log in

Setting gates for activities in the stochastic project scheduling problem through the cross entropy methodology

  • Published:
Annals of Operations Research Aims and scope Submit manuscript

Abstract

This paper addresses the problem of scheduling activities in projects with stochastic activity durations. The aim is to determine for each activity a gate—a time before it the activity cannot begin. Setting these gates is analogous to setting inventory levels in the news vendor problem. The resources required for each activity are scheduled to arrive according to its gate. Since activities’ durations are stochastic, the start and finish time of each activity is uncertain. This fact may lead to one of two outcomes: (1) an activity is ready to start its processing as all its predecessors have finished, but it cannot start because the resources required for it were scheduled to arrive at a later time. (2) The resources required for the activity have arrived and are ready to be used but the activity is not ready to start because of precedence constraints. In the first case we will incur a “holding” cost while in the second case, we will incur a “shortage” cost. Our objective is to set gates so as to minimize the sum of the expected holding and shortage costs. We employ the Cross-Entropy method to solve the problem. The paper describes the implementation of the method, compares its results to various heuristic methods and provides some insights towards actual applications.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Similar content being viewed by others

References

  • Alon, G., Kroese, D. P., Raviv, T., & Rubinstein, R. Y. (2005). Application of the Cross-Entropy method to the buffer allocation problem in a simulation-based environment. Annals of Operations Research, 134, 137–151.

    Article  Google Scholar 

  • Botev, Z., & Kroese, D. P. (2004). Global likelihood optimization via the cross-entropy method with an application to mixture models. In R. G. Ingalls, M. D. Rossetti, J. S. Smith, & B. A. Peters (Eds.), Proceedings of the 2004 winter simulation conference (pp. 529–535). New York: IEEE Press.

    Google Scholar 

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

    Article  Google Scholar 

  • Cohen, I., Golany, B., & Shtub, A. (2005). Managing stochastic, finite capacity, multi-project systems through the Cross-Entropy methodology. Annals of Operations Research, 134, 189–199.

    Article  Google Scholar 

  • Demeulemeester, E. L., & Herroelen, W. S. (2002). Project scheduling—a research handbook. Dordrecht: Kluwer Academic.

    Google Scholar 

  • Denardo, E. V. (1982). Dynamic programming: models and applications. New York: Prentice-Hall.

    Google Scholar 

  • Elmaghraby, S. E. (1977). Activity networks: project planning and control by network models. New York: Wiley.

    Google Scholar 

  • Elmaghraby, S. E. (2001). On the optimal release time of jobs with random processing times, with extensions to other criteria. International Journal of Production Economics, 74, 103–113.

    Article  Google Scholar 

  • Elmaghraby, S. E., Ferreira, A. A., & Tavares, L. V. (2000). Optimal start times under stochastic activity durations. International Journal of Production Economics, 64, 153–164.

    Article  Google Scholar 

  • Fazar, W. (1959). Program evaluation and review technique. American Statistician, 13(2), 10.

    Google Scholar 

  • Golany, B., Dar-El, E. M., & Zeev, N. (1999). Controlling shop floor operations in a multi-family, multi-cell manufacturing environment through constant work-in-process. IIE Transactions, 31, 771–781.

    Google Scholar 

  • Goldratt, E. M. (1997). Critical chain. New York: North River Press.

    Google Scholar 

  • Heragu, S. (1997). Facilities design. Boston: PWS Publishing Company.

    Google Scholar 

  • Herroelen, W. S., & Leus, R. (2005). Project scheduling under uncertainty: survey and research potentials. European Journal of Operational Research, 165, 289–306.

    Article  Google Scholar 

  • Herroelen, W. S., Van Dommelen, P., & Demeulemeester, E. L. (1997). Project network models with discounted cash flows: a guided tour through recent developments. European Journal of Operational Research, 100, 97–121.

    Article  Google Scholar 

  • Herroelen, W. S., De-Reyck, B., & Demeulemeester, E. L. (1998). Resource-constrained project scheduling: a survey of recent developments. Computers and Operations Research, 25(4), 279–302.

    Article  Google Scholar 

  • Kimms, A. (2001). Mathematical programming and financial objectives for scheduling projects. Dordrecht: Kluwer Academic.

    Google Scholar 

  • Kolish, R., & Padman, R. (2001). An integrated survey of deterministic project scheduling. Omega, 29, 249–272.

    Article  Google Scholar 

  • Kolish, R., Sprecher, A., & Drexl, A. (1995). Characterization and generation of a general class of resource-constrained project scheduling problems. Management Science, 41(10), 1693–1703.

    Article  Google Scholar 

  • Krishnamoorthy, M. (1968). Critical path method: a review. Technical Report, Michigan Univ., Dept. of Industrial Engineering, Ann-Arbor, MI, USA.

  • Kroese, D. P., Rubinstein, R. Y., & Porotsky, S. (2006). The cross-entropy method for continuous multi-extremal optimization. Methodology and Computing in Applied Probability, 8, 383–407.

    Article  Google Scholar 

  • Malcom, D. G., Roseboom, J. H., Clark, C. E., & Fazar, W. (1959). Apllication of a technique for research and development of program evaluation. Operations Research, 7, 646–669.

    Article  Google Scholar 

  • Rand, G. K. (2000). Critical chain: the theory of constraints applied to project management. International Journal of Project Management, 18, 173–177.

    Article  Google Scholar 

  • Rubinstein, R. Y., & Kroese, D. P. (2004). The Cross-Entropy method—a unified approach to combinatorial optimization, Monte-Carlo simulation, and machine learning. New York: Springer.

    Google Scholar 

  • Shtub, A., Bard, J. F., & Globerson, S. (2005). Project management—processes, methodologies, and economics. New York: Pearson Prentice Hall.

    Google Scholar 

  • Sobel, M. J., Szmerekovsky, J. G., & Tilson, V. (2009). Scheduling projects with stochastic activity duration to maximize expected net present value. European Journal of Operational Research, 198(3), 697–705.

    Article  Google Scholar 

  • Trietsch, D. (2006a). Economically balanced criticalities for robust project scheduling and control. Working Paper, ISOM Department, University of Auckland, New Zealand.

  • Trietsch, D. (2006b). Optimal feeding buffers for projects or batch supply chains by an exact generalization of the newsvendor result. International Journal of Production Research, 44, 627–637.

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

Authors

Corresponding author

Correspondence to Illana Bendavid.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Bendavid, I., Golany, B. Setting gates for activities in the stochastic project scheduling problem through the cross entropy methodology. Ann Oper Res 172, 259–276 (2009). https://doi.org/10.1007/s10479-009-0579-3

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10479-009-0579-3

Keywords

Navigation