A multi-objective resource-constrained project scheduling problem with time lags and fuzzy activity durations

Document Type : Research Paper

Authors

Department of Industrial Engineering, University of Kurdistan, Sanandaj, Iran

Abstract

The resource-constrained project scheduling problem is to find a schedule that minimizes the project duration subject to precedence relations and resource constraints. To further account for economic aspects of the project, one may add an objective of cash nature to the problem. In addition, dynamic nature and variations in real world are known to introduce uncertainties into data. Therefore, this study is aimed at proposing a multi-objective model for resource-constrained project scheduling problem, with the model objectives being to minimize makespan, and maximize net present value of the project cash flows; the proposed model has activity times expressed in fuzzy numbers where the corresponding uncertainties are taken into account. The project environment is considered to be a multi-resource environment where more than one resource is needed for the execution of any activity. Also, the proposed model comes with time lags in precedence relations between activities. The proposed model is validated by using epsilon-constraint method. The α-cut approach as well as the expression of acceptable risk level by the project manager is used to defuzzificate fuzzy activity durations. Since the problem is NP-hard, a NSGA-II meta-heuristic algorithm is proposed to solve the problem. The algorithm performance has been evaluated in terms of different criteria.

Keywords

Main Subjects


Abello, M. B., & Michalewicz, Z.(2014). Multiobjective resource-constrained project scheduling with a time-varying number of tasks, The scientific world journal, Volume 2014, Article ID 420101.
 Agarwal, R., Tiwari, M., & Mukherjee, S.(2007). Artificial immune system based approach for solving resource constraint project scheduling problem, The International Journal of Advanced Manufacturing Technology, 34, 584-593.
Artigues, C., Leus, R., Nobibon, F. , (2015). The stochastic time-constrained net present value problem, In: Schwindt, C., Zimmermann, J., editors. Handbook on Project Management and Scheduling Vol. 2. Springer, 875-908.
Atli, O. , & Kahraman, C.(2014). Resource-constrained project scheduling problem with multiple execution modes and fuzzy/crisp activity durations, Journal of Intelligent & Fuzzy Systems: Applications in Engineering and Technology, 26, 2001-2020.
 
Ballestín, F. (2007, April). A genetic algorithm for the resource renting problem with minimum and maximum time lags. In European Conference on Evolutionary Computation in Combinatorial Optimization (pp. 25-35). Springer Berlin Heidelberg.
 
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.
 
Čapek, R., Šůcha, P., & Hanzálek, Z. (2012). Production scheduling with alternative process plans. EuropeanJournal of Operational Research, 217(2), 300-311.
 
Chanas, S., & Zieliński, P.(2001).Critical path analysis in the network with fuzzy activity times, Fuzzy sets and systems, 122, 195-204.
 
Chassiakos, A. P., & Sakellaropoulos, S. P.(2005). Time-cost optimization of construction projects with generalized activity constraints, Journal of Construction Engineering and Management, 131, 1115-1124.
 
Davis, K. R., Stam, A., & Grzybowski, R. A.(1992). Resource constrained project scheduling with multiple objectives: A decision support approach, Computers & Operations Research, 19, 657-669.
 
De Reyck, B., & Herroelen, W.(1998). An optimal procedure for the resource-constrained project scheduling problem with discounted cash flows and generalized precedence relations, Computers & Operations Research, 25, 1-17.
 
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.
 
Demeulemeester, E. L., & Herroelen, W. S.(1996). Modelling setup times, process batches and transfer batches using activity network logic, European Journal of Operational Research, 89, 355-365.
 
Drexl, A., Nissen, R., Patterson, J. H., & Salewski, F. (2000). ProGen/πx–An instance generator for resource-constrained project scheduling problems with partially renewable resources and further extensions, European Journal of Operational Research, 125, 59-72.
 
Dubois, D. J.(1980). Fuzzy sets and systems: theory and applications vol. 144. Toulouse, France: Academic press.
 
Elloumi, S., Fortemps, P., & Loukil T.(2017). Multi-objective algorithms to multi-mode resource-constrained projects under mode change disruption. Computers & Industrial Engineeirg, 106, 161-173.
 
Ghamginzadeh, A., Najafi, A.A., & Azimi, P.(2014). Solving a multi-objective resource-constrained project scheduling problem using a cuckoo optimization algorithm, Scientia Iranica, 21(6), 2419-2428.
 
Gomes, H.C., Neves, F.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.

Habibi, F., Barzinpour, F., Sadjadi, S.J. (2017). A Multi-objective optimization model for project scheduling with time-varying resource requirements and capacities. Journal of Industrial and System Engineering, 10, 92-118.

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.
 
 
Hapke, M., & Slowinski, R.(1996). Fuzzy priority heuristics for project scheduling, Fuzzy sets and systems, 83, 291-299.
 
Hapke, M., Jaszkiewicz, A., & Slowinski, R.(1994). Fuzzy project scheduling system for software development, Fuzzy sets and systems, 67, 101-117.
 
Hapke, M., Jaszkiewicz, A., & Słowiński, R.(1998). Interactive analysis of multiple-criteria project scheduling problems, European Journal of Operational Research, 107, 315-324.
 
Herroelen, W., & Leus, R. (2005). Project scheduling under uncertainty: Survey and research potentials. European journal of operational research , 165 (2), 289-306.
 
Kazemi, F., & Tavakkoli-Moghaddam, R.(2011a). Solving a multi-objective multi-mode resource-constrained project scheduling problem with particle swarm optimization, International Journal of Academic Research, 3, 103-110.
 
Kazemi, F. , & Tavakkoli-Moghaddam, R.(2011b).Solving a multi-objective multimode resource-constrained project scheduling problem with discounted cash flows, 6th International Project Management Conference, vol. 3.
 
Khalili, S., Najafi, A. A., & Niaki, S. T. A.(2013). Bi-objective resource constrained project scheduling problem with makespan and net present value criteria: two meta-heuristic algorithms, The International Journal of Advanced Manufacturing Technology, 69, 617-626.
 
Kolisch, R., & Hartmann, S. (2006). Experimental investigation of heuristics for resource-constrained project scheduling: an update. European Journal of Operational Research, 174, 23–37.
 
Leyman, P. & Vanhoucke, M. (2016). Payment models and net present value optimization for resource- constrained project scheduling. Computers & Industrial Engineering, 91,139-153.
 
Maghsoudlou, H., Afshar-Nadjafi, B., & Akhavan Niaki, S.T. (2016). A multi-objective invasive weeds optimization algorithm for solving multi-skill resource constrained project scheduling problem. Computers & Chemical Engineering, 88, 157-169.
 
Mogale, D. G., Kumar, S. K., & Tiwari, M. K. (2016). Two-stage Indian food grain supply chain network transportation-allocation model. IFAC-PapersOnLine, 49(12), 1767-1772.
 
Mogale, D.G., Kumar, S.K., & Tiwari, M.K. (2018). An MINLP model to support the movement and storage decisions of the Indian food grain supply chain. Control Engineering Practice, 70, 98-113.
 
Mogale, D.G., Lahoti, G., Jha, S.B., Shukla, M., Kamath, N., & Tiwari, M.K. (2018). Dual market facility network design under bounded rationality. Algorithms, 11(54), 1-18.
 

Mogale, D.G., Kumar, M., Kumar, S.k., Tiwari, M.K. (2018). Grain silo location-allocation problem with dwell time for optimization of food grain supply chain network. Transportation Research Part E, 111, 40-69.

Moradi, M., Hafezalkotob, A., Ghezavati, V.R. (2018). The resource-constraint project scheduling problem of the project subcontractors in a cooperative environment: Highway construction case study. Journal of Industrial and System Engineering, 11(3). Published Online.

Nahmias, S.(1978). Fuzzy variables, Fuzzy sets and systems, 1, 97-110.
 
Nudtasomboon, N., & Randhawa, S. U.(1997). Resource-constrained project scheduling with renewable and non-renewable resources and time-resource tradeoffs, Computers & Industrial Engineering, 32, 227-242.
 
Palacio, J. D. & Larrea, O. L. (2017). A lexicographic approach to the robust resource-constrained project scheduling problem. International Transactions in Operational esearch, 24,143-157.
 
Tao, S. & Dong, Z.S. (2018). Multi-mode resource-constrained project scheduling problem with alternative project structures. Computers & Industrial Engineering, 125, 333-347.
 
Tritschler, M., Naber, A., Kolisch, R. (2017). A hybrid metaheuristic for resource-constrained project scheduling with flexible resource profiles. European Journal of Operational Research, 262(1), 262-273.
 
Vanucci, S. C., Bicalho, R., Carrano, E. G., & Takahashi, R. H.(2012). A modified NSGA-II for the Multiobjective Multi-mode Resource-Constrained Project Scheduling Problem, IEEE Congress on Evolutionary Computation (CEC), pp. 1-7.

Wang, L., Zheng, X.-L. (2018). A knowledge-guided multi-objective fruit fly optimization algorithm for the multi-skill resource constrained project scheduling problem. Swarm and Evolutionary Computation, 38, 54-63.

Wieseman, W., Kuhn, D., (2015). The stochastic time-constrained net present value problem, In: Schwindt, C., Zimmermann, J., editors. Handbook on Project Management and Scheduling Vol. 2. Springer, 753-780.
 
Wiest, J. D. (1962). The scheduling of large projects with limited resources, Ph.D. dissertation, DTIC Document.
 
Xiao, J., Wu, Z., Hong, X. X., Tang, J. C., & Tang , Y. (2016). Integration of electromagnetism with multi-objective evolutionary algorithms for RCPSP. European Journal of Operational Research, 251(1), 22-35.
 
Zhao, Z. Y., You, W. Y., & Lv, Q. L.(2008). Applications of fuzzy critical chain method in project scheduling, in Natural ComputationI, Fourth International Conference on CNC'08., 473-477.