Robust optimization for the resource-constrained multi-project scheduling problem with uncertain activity durations

Document Type : Article


Faculty of Industrial Engineering, K.N. Toosi University of Technology, Tehran 1999143344, Iran


This paper studies the multi-project scheduling problem which involves multiple projects with different importance weight; with predefined assigned due dates; with activities that have uncertain durations; and with renewable resources that are constrained. The resource sharing policy is applied to share the resources among projects. Due to the environmental rapid changes and also the uniqueness of projects, the probability distribution function of uncertain durations cannot be estimated with confidence. Besides, the multi-project scheduling problem with its large scale investment dictates a conservative approach to deal with the existing uncertainty. Therefore, the Robust Resource-Constrained Multi-Project Scheduling Problem (RRCMPSp ) is studied in this paper while the maximum total weighted tardiness of the projects should be minimized. A scenario-relaxation algorithm is implemented which results in optimal solutions for the RRCMPSp . The aim is to find an optimal structure containing all the projects in such a way that it transfers the resources between the activities based on the resource sharing policy while the maximum weighted differences between the projects finish times and their assigned due dates will be minimum.


Main Subjects

1. Ma, W., Che, Y., Huang, H., and Ke, H. Resourceconstrained  project scheduling problem with uncertain  durations and renewable resources", International  Journal of Machine Learning and Cybernetics, 7(4),  pp. 613{621 (2016).  2. Hindelang, T.J. and Muth, J.F. A dynamic programming  algorithm for decision CPM networks",  Operations Research, 27(2), pp. 225{241 (1979).  3. Kruger, D. and Scholl, A. A heuristic solution  framework for the resource constrained (multi-)project  scheduling problem with sequence-dependent transfer  times", European Journal of Operational Research,  197, pp. 492{508 (2009).  4. Besikci, U., Bilge, U., and Ulusoy, G. Resource  dedication problem in a multi-project environment",  Flexible Services and Manufacturing Journal, 25, pp.  206{229 (2013).  5. Payne, J.H. Management of multiple simultaneous  projects: A state-of-the-art review", International  Journal of Project Management, 13(3), pp. 163{168  (1995).  6. Aritua, B., Smith, N.J., and Bower, D. Construction  client multi-projects - A complex adaptive systems  perspective", International Journal of Project Management,  27, pp. 72{79 (2009).  7. Bruni, M.E., Puglia Pugliese, L., Di Beraldi, P.,  and Guerriero, F. An adjustable robust optimization  model for the resource-constrained project scheduling  problem with uncertain activity durations", Omega,  71, pp. 66{84 (2017).  8. Bertsimas, D. and Sim, M. The price of robustness",  Operations Research, 52(1), pp. 35{53 (2004).  9. Herroelen, W. and Leus, R. Project scheduling under  uncertainty: Survey and research potentials", European  Journal of Operational Research, 165, pp. 289{  306 (2005).  10. Li, Z. and Floudas, C.A. Robust counterpart optimization:  Uncertainty sets, formulations and probabilistic  guarantees", Paper presented at the proceedings  of the 6th conference on foundations of  computer-aided process operations, Savannah (Georgia)  (2012). proceedings/  data/papers/030.pdf  11. Yamashita, D.S., Armentano, V.A., and Laguna, M.  Robust optimization models for project scheduling  with resource availability cost", Journal of Scheduling,  10, pp. 67{76 (2007).  12. Zheng, Z., Shumin, L., Ze, G., and Yueni, Z. Resource  constraint multi project scheduling with priority and  uncertain activity durations", International Journal of  Computational Intelligence Systems, 6(3), pp. 530{547  (2013).  13. Kerzner, H., Project Management: A Systems Approach  to Planning, Scheduling, and Controlling, Ed.  11th. pp. 1, 7, 42, 66, Hoboken: Wiley (2013).  14. Blismass, N., Sher, W.D., Thorpe, A., and Baldwin,  A.N. Factors inuencing delivery within construction  clients' multi-project environments", Engineering,  Construction and Architectural Management, 11(2),  pp. 113{125 (2004a).  15. Wei-xin, W., Xu, W., Xian-long, G., and Lei, D.  Multi-objective optimization model for multi-project  scheduling on critical chain", Advances in Engineering  Software, 68, pp. 33{39 (2014).  16. Wauters, T., Kinable, J., Smet, P., Vancroonenburg,  W., Berghe, G., and Verstichel, J. The multimode  resource-constrained multi-project scheduling  problem", Journal of Scheduling, 19(3), pp. 271{283  (2016).  17. Besikci, U., Bilge, U., and Ulusoy, G. Multi-mode  resource constrained multi-project scheduling and resource  portfolio problem", European Journal of Operational  Research, 240, pp. 22{31 (2015).  18. Zheng, Z., Shumin, L., Ze, G., Yueni, Z., and Zhang,  X. A critical chains-based distributed multi-project  scheduling approach", Neurocomputing, 143, pp. 282{  293 (2014).  19. Singh, A. Resource constrained multi-project scheduling  with priority rules & analytic hierarchy process",  Procedia Engineering, 69, pp. 725{734 (2014).  20. V_azquez, E.P., Calvo, M.P., and Ord_o~nez, P.M.  Learning process on priority rules to solve the  RCMPSP", Journal of Intelligent Manufacturing,  26(1), pp. 123{138 (2015).  21. Wang, Y., He, Z., Kerkhove, L., and Vanhoucke, M.  On the performance of priority rules for the stochastic  resource constrained multi-project scheduling problem",  Computers & Industrial Engineering, 114, pp.  223{234 (2017).  22. Uysal, F. Hybrid mate-heuristic algorithms for the resource  constrained multi-project scheduling problem",  PhD Thesis, Graduate School of Natural and Applied  Sciences of Middle East Technical University (2014).  376 E. Nabipoor Afruzi et al./Scientia Iranica, Transactions E: Industrial Engineering 27 (2020) 361{376  23. Nabipoor Afruzi, E., Roghanian, E., Naja_, A.A.,  and Mazinani, M. A multi-mode resource-constrained  discrete time-cost tradeo_ problem solving using an  adjusted fuzzy dominance genetic algorithm", Scientia  Iranica, 20(3), pp. 931{944 (2014).  24. Hazir, O., Erel, E., and Gnalay, Y. Robust optimization  models for the discrete time/cost trade-o_ problem",  International Journal of Production Economics,  130(1), pp. 87{95 (2011).  25. Moghani Ghahremanlouie, S. and Fathi Hafashjani,  K. A novel robust model for discrete time-cost trade  o_ problem", International Journal of Industrial Engineering  & Production Management, 25(1), pp. 1{14  (2014).  26. Rostami, S., Creemers, S., and Leus, R. A new  policy class for the stochastic RCPSP", International  Conference on Project Management and Scheduling  (PMS), At Valencia, Spain, p. 15 (2016).  27. Tao, S., Wu, C., Sheng, Z., and Wang, X. Stochastic  project scheduling with hierarchical alternatives", Applied  Mathematical Modelling, 58, pp. 181{202 (2018).  28. Chiang, A.J. and Jeang, A. Stochastic project management  via computer simulation and optimisation  method", International Journal of Systems Science:  Operations & Logistics, 2(4), pp. 211{230 (2015).  29. Ning, M., He, Z., Jia, T., and Wang, N. Metaheuristics  for multi-mode cash ow balanced project scheduling  with stochastic duration of activities", Automation  in Construction, 81, pp. 224{233 (2017).  30. Chtourou, H. and Haouari, M. A two-stage-priorityrule-  based algorithm for robust resource-constrained  project scheduling", Computers and Industrial Engineering,  55(1), pp. 183{194 (2008).  31. Khalilzadeh, M., Shakeri, H., Gholami, H., and Amini,  L. A heuristic algorithm for project scheduling with  fuzzy parameters", Procedia Computer Science, 121,  pp. 63{71 (2017).  32. Knyazeva, M., Bozhenyuk, B., and Rozenberg, I.  Resource-constrained project scheduling approach  under fuzzy conditions", Procedia Computer Science,  77, pp. 56{64 (2015).  33. Dixit, V., Srivastava, R.K., and Chaudhuri, A. Procurement  scheduling for complex projects with fuzzy  activity durations and lead times", Computers &  Industrial Engineering, 76, pp. 401{414 (2014).  34. Huang, M., Yuan, J., and Xiao, J. An adapted _rey  algorithm for product development project scheduling  with fuzzy activity duration", Mathematical Problems  in Engineering, 2015, Article ID 973291, 11 pages  (2015).  35. Chakrabortty, R.K., Sarker, R.A., and Essam, D.L.  Resource constrained project scheduling with uncertain  activity durations", Computers & Industrial  Engineering, 112, pp. 537{550 (2017).  36. Artigues, C., Leus, R., and Nobibon, F.T. Robust optimization  for resource-constrained project scheduling  with uncertain activity durations", Flexible Services  and Manufacturing Journal, 25, pp. 175{205 (2013).  37. Balas E. Project scheduling with resource constraints",  In E.M.L. Beale, Ed., Applications of Mathematical  Programming Techniques, pp. 187{200, The  English Universities Press Ltd (1971).  38. Assavapokee, T., Real_, M.J., Ammons, J.C., and  Hong, I-H. Scenario relaxation algorithm for _nite  scenario-based min-max regret and min-max relative  regret robust optimization", Computers & Operations  Research, 35, pp. 2093{2102 (2008).  39. Demeulemeester, E., Vanhoucke, M., and Herroelen,  W. A random network generator for activity-on-thenode  networks", Journal of Scheduling, 6, pp. 13{34  (2003).  40. Patterson, J.H. Project scheduling: the e_ects of  problem structure on heuristic performance", Naval  Research Logistic, 23(1), pp. 95{123 (1976).