New competitive results for the stochastic resource-constrained project scheduling problem: exploring the benefits of pre-processing

Journal of Scheduling - Tập 14 - Trang 157-171 - 2009
Behzad Ashtiani1, Roel Leus2, Mir-Bahador Aryanezhad1
1Department of Industrial Engineering, Iran University of Science and Technology, Tehran, Iran
2Department of Decision Sciences and Information Management, Katholieke Universiteit Leuven, Leuven, Belgium

Tóm tắt

We study the resource-constrained project scheduling problem with stochastic activity durations. We introduce a new class of scheduling policies for solving this problem, which make a number of a-priori sequencing decisions in a pre-processing phase while the remaining decisions are made dynamically during project execution. The pre-processing decisions entail the addition of extra precedence constraints to the scheduling instance, hereby resolving some potential resource conflicts. We obtain new competitive results for expected-makespan minimization on representative datasets, which are significantly better than those obtained by the existing algorithms when the variability in the activity durations is medium to high.

Tài liệu tham khảo

Al-Bahar, J., & Crandall, K. (1990). Systematic risk management approach for construction projects. Journal of Construction Engineering and Management, 116, 533–546.

Al Fawzan, M., & Haouari, M. (2005). A bi-objective model for robust resource-constrained project scheduling. International Journal of Production Economics, 96, 175–187.

Baker, K., & Trietsch, D. (2009). Principles of sequencing and scheduling. New York: Wiley.

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

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

Blazewicz, J., Lenstra, J., & Rinnooy Kan, A. (1983). Scheduling subject to resource constraints: classification and complexity. Discrete Applied Mathematics, 5, 11–24.

Brucker, P., Knust, S., Schoo, A., & Thiele, O. (1998). A branch-and-bound algorithm for the resource-constrained project scheduling problem. European Journal of Operational Research, 107, 272–288.

Chapman, C., & Ward, S. (2000). Estimation and evaluation of uncertainty: a minimalist first pass approach. International Journal of Project Management, 18, 369–383.

Chtourou, H., & Haouari, M. (2008). A two-stage-priority-rule-based algorithm for robust resource-constrained project scheduling. Computers & Industrial Engineering, 55, 183–194.

Dawood, N. (1998). Estimating project and activity duration: a risk management approach using network analysis. Construction Management and Economics, 16, 41–48.

Demeulemeester, E., & Herroelen, W. (1997). New benchmark results for the resource-constrained project scheduling problem. Management Science, 43, 1485–1492.

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

Drexl, A. (1991). Scheduling of project networks by job assignment. Management Science, 37, 1590–1602.

Elmaghraby, S. (1977). Activity networks. New York: Wiley-Interscience.

Fernandez, A. A., Armacost, R. L., & Pet-Edwards, J. (1996). The role of the non-anticipativity constraint in commercial software for stochastic project scheduling. Computers and Industrial Engineering, 31, 233–236.

Fernandez, A. A., Armacost, R. L., & Pet-Edwards, J. (1998). Understanding simulation solutions to resource constrained project scheduling problems with stochastic task durations. Engineering Management Journal, 10, 5–13.

Goldberg, D. (1989). Genetic algorithms in search, optimization, and machine learning. Reading: Addison-Wesley.

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

Graham, R. (1966). Bounds on multiprocessing timing anomalies. Bell System Technical Journal, 45, 1563–1581.

Hartmann, S. (1998). A competitive genetic algorithm for resource-constrained project scheduling. Naval Research Logistics, 45, 733–750.

Hartmann, S., & Kolisch, R. (2000). Experimental evaluation of state-of-the-art heuristics for the resource-constrained project scheduling problem. European Journal of Operational Research, 127, 394–407.

Herroelen, W., & Leus, R. (2004). Robust and reactive project scheduling: A review and classification of procedures. International Journal of Production Research, 42(8), 1599–1620.

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

Holland, H. (1975). Adaptation in natural and artificial systems. Ann Arbor: University of Michigan Press.

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

Kolisch, R. (1996a). Efficient priority rules for the resource-constrained project scheduling problem. Journal of Operations Management, 14, 172–192.

Kolisch, R. (1996b). Serial and parallel resource-constrained project scheduling methods revisited: Theory and computation. European Journal of Operational Research, 90, 320–333.

Kolisch, R., & Hartmann, S. (1999). Heuristic algorithms for the resource-constrained project scheduling problem: Classification and computational analysis. In J. Weglarz (Ed.), Project scheduling. Recent models, algorithms and applications (pp. 147–178). Dordrecht: Kluwer.

Kolisch, R., & Hartmann, S. (2006). Experimental investigation of heuristics for resource-constrained project scheduling: An update. European Journal of Operational Research, 174, 23–37.

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

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

Lambrechts, O. 2007. Robust project scheduling subject to resource breakdowns. Ph.D. thesis, Katholieke Universiteit Leuven, Belgium.

Leus, R., & Herroelen, W. (2004). Stability and resource allocation in project planning. IIE Transactions, 36(7), 667–682.

Li, K., & Willis, R. (1992). An iterative scheduling technique for resource-constrained project scheduling. European Journal of Operational Research, 56, 370–379.

Möhring, R. (2000). Scheduling under uncertainty: optimizing against a randomizing adversary. Lecture Notes in Computer Science, 1913/2000, 651–670.

Möhring, R., Radermacher, F., & Weiss, G. (1984). Stochastic scheduling problems I – general strategies. ZOR. Zeitschrift für Operations Research, 28, 193–260.

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

Özdamar, L., & Ulusoy, G. (1996). A note on an iterative forward/backward scheduling technique with reference to a procedure by Li and Willis. European Journal of Operational Research, 89, 400–407.

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

Pet-Edwards, J., Selim, B., Armacost, R. L., & Fernandez, A. (1998). Minimizing risk in stochastic resource-constrained project scheduling. In: Proceedings of INFORMS fall meeting, Seattle, USA.

Pinedo, M. (2008). Scheduling. Theory, algorithms, and systems. Berlin: Springer.

Saliby, E. (1990). Descriptive sampling: a better approach to Monte Carlo simulation. Journal of the Operational Research Society, 41, 1133–1142.

Schatteman, D., Herroelen, W., Van de Vonder, S., & Boone, A. (2008). A methodology for integrated risk management and proactive scheduling of construction projects. Journal of Construction Engineering and Management, 134, 885–893.

Shtub, A., Bard, J., & Globerson, S. (2005). Project management. Processes, methodologies, and Economics. New York: Pearson, Prentice Hall.

Sprecher, A. (2000). Scheduling resource-constrained projects competitively at modest memory requirements. Management Science, 46, 710–723.

Stork, F. 2001. Stochastic resource-constrained project scheduling. Ph.D. thesis, Technische Universität Berlin.

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

Valls, V., Ballestín, F., & Quintanilla, S. (2005). Justification and RCPSP: a technique that pays. European Journal of Operational Research, 165, 375–386.

Valls, V., Ballestín, F., & Quintanilla, S. (2008). Hybrid genetic algorithm for the resource-constrained project scheduling problem. European Journal of Operational Research, 185, 495–508.

Van de Vonder, S., Demeulemeester, E., Herroelen, W., & Leus, R. (2005). The use of buffers in project management: The trade-off between stability and makespan. International Journal of Production Economics, 97, 227–240.

Vepsalainen, A., & Morton, T. (1987). Priority rules for job shops with weighted tardines costs. Management Science, 33, 1035–1047.

Wang, J. (2004). A fuzzy robust scheduling approach for product development projects. European Journal of Operational Research, 152, 180–194.

Wu, S. D., Byeon, E. S., & Storer, R. H. (1999). A graph-theoretic decomposition of job shop scheduling to achieve scheduling robustness. Operations Research, 47(1), 113–124.

Xu, N., McKee, S. A., Nozick, L. K., & Ufomata, R. (2008). Augmenting priority rule heuristics with justification and rollout to solve the resource-constrained project scheduling problem. Computers & Operations Research, 35, 3284–3297.

Yu, G., & Qi, X. (2004). Disruption management—framework, models and applications. Singapore: World Scientific.

Thông tin
Thông tin xuất bản

Journal of Scheduling

Tập 14

157-171

Thông tin tác giả