A Multi-objective optimization model for project scheduling with time-varying resource requirements and capacities

Document Type : Research Paper

Authors

School of Industrial Engineering, Iran University of Science and Technology, Tehran, Iran

Abstract

Proper and realistic scheduling is an important factor of success for every project. In reality, project scheduling often involves several objectives that must be realized simultaneously, and faces numerous uncertainties that may undermine the integrity of the devised schedule. Thus, the manner of dealing with such uncertainties is of particular importance for effective planning. A realistic schedule must also take account of the time-based variations in the capacity of renewable resources and the amount of resources needed to undertake the activities and the overall effect of such variations on the schedule. In this study, we propose a multi-objective project scheduling optimization model with time-varying resource requirements and capacities.This model, with the objectives of minimizing the project makespan, maximizing the schedule robustness, and maximizing the net present value, considers the interests of both project owner and contractor simultaneously. Two multi-objective solution algorithms, NSGA-II and MOPSO, are modified and adjusted with Taguchi method to be used for determination of the set of Pareto optimal solutions for the proposed problem. The proposed solution methods are evaluated by the use of fifteen problems of different sizes derived from Project Scheduling Problem Library (PSPLIB). Finally, solutions of the algorithms are evaluated in terms of five evaluation criteria. The comparisons show that NSGA-II yields better results than MOPSO algorithm. Also, we show that ignoring the time-based variations in consumption and availability of resources may lead to underestimation of project makespan and significant deviation from the optimal activity sequence.

Keywords

Main Subjects


ABBASI, B., SHADROKH, S. & ARKAT, J. 2006. Bi-objective resource-constrained project scheduling with robustness and makespan criteria. Applied mathematics and computation, 180, 146-152.
AFSHAR-NADJAFI, B. 2016. A new proactive approach to construct a robust baseline schedule considering quality factor. International Journal of Industrial and Systems Engineering, 22, 63-72.
AKKAN, C., DREXL, A. & KIMMS, A. 2005. Network decomposition-based benchmark results for the discrete time–cost tradeoff problem. European Journal of Operational Research, 165, 339-358.
AL-FAWZAN, M. A. & HAOUARI, M. 2005. A bi-objective model for robust resource-constrained project scheduling. International Journal of production economics, 96, 175-187.
ARTIGUES, C., LEUS, R. & NOBIBON, F. T. 2013. Robust optimization for resource-constrained project scheduling with uncertain activity durations. Flexible Services and Manufacturing Journal, 25, 175-205.
BARTUSCH, M., MÖHRING, R. H. & RADERMACHER, F. J. 1988. Scheduling project networks with resource constraints and time windows. Annals of operations Research, 16, 199-240.
BERTHAUT, F., PELLERIN, R., PERRIER, N. & HAJJI, A. 2014. Time-cost trade-offs in resource-constraint project scheduling problems with overlapping modes. International Journal of Project Organisation and Management, 6, 215-236.
CHTOUROU, H. & HAOUARI, M. 2008. A two-stage-priority-rule-based algorithm for robust resource-constrained project scheduling. Computers & industrial engineering, 55, 183-194.
COELLO, C. A. C., PULIDO, G. T. & LECHUGA, M. S. 2004. Handling multiple objectives with particle swarm optimization. IEEE Transactions on evolutionary computation, 8, 256-279.
CREEMERS, S. 2015. Minimizing the expected makespan of a project with stochastic activity durations under resource constraints. Journal of Scheduling, 18, 263-273.
DE REYCK, B., DEMEULEMEESTER, E. & HERROELEN, W. 1999. Algorithms for scheduling projects with generalized precedence relations. Project Scheduling. Springer.
DEB, K., PRATAP, A., AGARWAL, S. & MEYARIVAN, T. 2002. A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE transactions on evolutionary computation, 6, 182-197.
DELGOSHAEI, A., ARIFFIN, M., BAHARUDIN, B. & LEMAN, Z. 2015. Minimizing makespan of a resource-constrained scheduling problem: A hybrid greedy and genetic algorithms. International Journal of Industrial Engineering Computations, 6, 503-520.
DEMEULEMEESTER, E., DE REYCK, B., FOUBERT, B., HERROELEN, W. & VANHOUCKE 1998. New computational results on the discrete time/cost trade-off problem in project networks. Journal of the Operational Research Society, 49, 1153-1163.
FALLAH, M., ARYANEZHAD, M. & ASHTIANI, B. Preemptive resource constrained project scheduling problem with uncertain resource availabilities: Investigate worth of proactive strategies.  Industrial Engineering and Engineering Management (IEEM), 2010 IEEE International Conference on, 2010. IEEE, 646-650.
GHASSEMI-TARI, F. & OLFAT, L. 2007. Development of a set of algorithms for the multi-project scheduling problems. Journal of Industrial and Systems Engineering, 1, 11-17.
GOLDRATT, E. M. 1997. Critical chain: A business novel, North River Press Great Barrington, MA.
GOMES, H. C., DAS NEVES, F. D. A. & SOUZA, M. J. F. 2014. Multi-objective metaheuristic algorithms for the resource-constrained project scheduling problem with precedence relations. Computers & Operations Research, 44, 92-104.
HAO, X., LIN, L. & GEN, M. 2014. An effective multi-objective EDA for robust resource constrained project scheduling with uncertain durations. Procedia Computer Science, 36, 571-578.
HAOUARI, M. & AL-FAWZAN, M. A. 2002. A bi-objective model for maximizing the quality in project scheduling. DIMACS technical report 2002.
HARTMANN, S. 2015. Time-Varying Resource Requirements and Capacities. Handbook on Project Management and Scheduling Vol. 1. Springer.
HARTMANN, S. & BRISKORN, D. 2010. A survey of variants and extensions of the resource-constrained project scheduling problem. European Journal of operational research, 207, 1-14.
HSU, C.-C. & KIM, D. S. 2005. A new heuristic for the multi-mode resource investment problem. Journal of the Operational Research Society, 56, 406-413.
KANG, C. & CHOI, B.-C. 2015. An adaptive crashing policy for stochastic time-cost tradeoff problems. Computers & Operations Research, 63, 1-6.
KUMAR, S. & ARUNAGIRI, A. 2010. Learning curve consideration in makespan computation using artificial neural network approach. Journal of Industrial and Systems Engineering, 4, 183-192.
LAMAS, P. & DEMEULEMEESTER, E. 2016. A purely proactive scheduling procedure for the resource-constrained project scheduling problem with stochastic activity durations. Journal of Scheduling, 19, 409-428.
LAMBRECHTS, O., DEMEULEMEESTER, E. & HERROELEN, W. 2008. Proactive and reactive strategies for resource-constrained project scheduling with uncertain resource availabilities. Journal of scheduling, 11, 121-136.
LAMBRECHTS, O., DEMEULEMEESTER, E. & HERROELEN, W. 2011. Time slack-based techniques for robust project scheduling subject to resource uncertainty. Annals of Operations Research, 186, 443-464.
LEYMAN, P. & VANHOUCKE, M. 2016. Payment models and net present value optimization for resource-constrained project scheduling. Computers & Industrial Engineering, 91, 139-153.
LIU, Z. & ZHENG, Y. Resource-constrained multiple projects scheduling with the objective of minimizing activities cost.  Control and Decision Conference, 2008. CCDC 2008. Chinese, 2008. IEEE, 1027-1032.
MOGAADI, H. & CHAAR, B. F. Scenario-Based Evolutionary Approach for Robust RCPSP.  Proceedings of the Second International Afro-European Conference for Industrial Advancement AECIA 2015, 2016. Springer, 45-55.
PALACIO, J. D. & LARREA, O. L. 2017. A lexicographic approach to the robust resource‐constrained project scheduling problem. International Transactions in Operational Research, 24, 143-157.
REZAEIAN, J., SOLEIMANI, F., MOHASELAFSHARY, S. & ARAB, A. 2015. Using a meta-heuristic algorithm for solving the multi-mode resource-constrained project scheduling problem. International Journal of Operational Research, 24, 1-16.
RUSSELL, A. 1970. Cash flows in networks. Management Science, 16, 357-373.
SHI, Y.-J., QU, F.-Z., CHEN, W. & LI, B. 2010. An artificial bee colony with random key for resource-constrained project scheduling. Life system modeling and intelligent computing. Springer.
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, 697-705.
SOLTANI, A. & HAJI, R. 2007. A project scheduling method based on fuzzy theory. Journal of Industrial and Systems Engineering, 1, 70-80.
SONG, Y., LIU, J., WIMMERS, M. O. & JIANG, Z. A differential evolution algorithm with local search for resource investment project scheduling problems.  Evolutionary Computation (CEC), 2015 IEEE Congress on, 2015. IEEE, 1725-1731.
SPRECHER, A. 2012. Resource-constrained project scheduling: Exact methods for the multi-mode case, Springer Science & Business Media.
ULUSOY, G., SIVRIKAYA-ŞERIFOĞLU, F. & ŞAHIN, Ş. 2001. Four payment models for the multi-mode resource constrained project scheduling problem with discounted cash flows. Annals of Operations research, 102, 237-261.
VANHOUCKE, M., DEMEULEMEESTER, E. & HERROELEN, W. 2002. Discrete time/cost trade-offs in project scheduling with time-switch constraints. Journal of the Operational Research Society, 741-751.
WANG, W.-X., WANG, X., GE, X.-L. & DENG, L. 2014. Multi-objective optimization model for multi-project scheduling on critical chain. Advances in Engineering Software, 68, 33-39.
WIESEMANN, W., KUHN, D. & RUSTEM, B. 2010. Maximizing the net present value of a project under uncertainty. European Journal of Operational Research, 202, 356-367.
WU, S., WAN, H.-D., SHUKLA, S. K. & LI, B. 2011. Chaos-based improved immune algorithm (CBIIA) for resource-constrained project scheduling problems. Expert Systems with Applications, 38, 3387-3395.
XIONG, J., CHEN, Y., LIU, J. & ABBASS, H. A. An evolutionary multi-objective scenario-based approach for stochastic resource investment project scheduling.  Evolutionary Computation (CEC), 2011 IEEE Congress on, 2011. IEEE, 2767-2774.
XIONG, J., LIU, J., CHEN, Y. & ABBASS, H. A. 2014. A knowledge-based evolutionary multiobjective approach for stochastic extended resource investment project scheduling problems. IEEE Transactions on Evolutionary Computation, 18, 742-763.
YUAN, X., LIU, J. & WIMMERS, M. O. A multi-agent genetic algorithm with variable neighborhood search for resource investment project scheduling problems.  Evolutionary Computation (CEC), 2015 IEEE Congress on, 2015. IEEE, 23-30.