A Competitive Nature-Inspired Cuckoo Search Algorithm for Solving the Resource Constrained Project Scheduling Problem

Authors

  • Seyed Taha Hossein Mortaji * PhD., Iran University of Science and Technology, Industrial Engineering Department, Tehran, Iran.
  • Mohammadreza Hosseinzadeh PhD., Iran University of Science and Technology, Industrial Engineering Department, Tehran, Iran.

DOI:

https://doi.org/10.59615/ijie.1.3.48

DOR:

https://dorl.net/dor/20.1001.1.27831906.2021.1.3.5.1

Keywords:

Resource Constrained Project Scheduling, Meta-heuristics, Cuckoo Search, Levy Flights, Makespan Minimization

Abstract

Since its advent, the resource constrained project scheduling problem has been a favorite NP-Hard problem studied by many researchers. In this paper, we examine this problem with a focus on the total project time minimization, usually known as the makespan minimization. To this end, a nature-inspired Cuckoo Search Algorithm (CSA) has been introduced that works by simulating the brooding parasitism of some cuckoo birds in nature. In a nutshell, the proposed cuckoo search algorithm has two main capabilities including: a) a global random search using Levy flights, and b) a local random refinement strategy. In addition, a double justification method has been employed to improve the generated solutions. Simultaneous use of these features can maximize the efficiency of resource searches in uncertain environments. Experimental results on the standard J30, J60, and J120 test sets from the PSPLIB are also presented, showing that the CSA has satisfying results compared with the other well-reported algorithms.

Downloads

Download data is not yet available.

References

• Aliahmadi, A., Sadeghi, M. E., Nozari, H., Jafari-Eskandari, M., & Najafi, S. E. (2015). Studying key factors to creating competitive advantage in science Park. In Proceedings of the Ninth International Conference on Management Science and Engineering Management (pp. 977-987). Springer, Berlin, Heidelberg.Doi: https://doi.org/10.1007/978-3-662-47241-5_82

• Alvarez-Valdes, R. & Tamarit, M., 1989. Heuristic algorithms for resource-constrained project scheduling: A review and an empirical analysis. Advances in project scheduling, Volume 134.

• Aristide, M., Maniezzo, V., Ricciardelli, S. & Bianco, L., 1998. An exact algorithm for the resource-constrained project scheduling problem based on a new mathematical formulation. Management Science, 44(5), pp. 714-729.

• Artigues, C., Huguet, M.-J. & Lopez, P., 2011. Generalized disjunctive constraint propagation for solving the job shop problem with time lags. Engineering Applications of Artificial Intelligence, 24(2), pp. 220-231.Doi: https://doi.org/10.1016/j.engappai.2010.07.008

• Ben Issa, S. & Tu, Y., 2020. A survey in the resource-constrained project and multi-project scheduling problems. Journal of Project Management, 5(2), pp. 117-138.Doi: http://dx.doi.org/10.5267/j.jpm.2019.11.001

• Bettemir, Ö. H. & Sonmez, R., 2014. Hybrid Genetic Algorithm with Simulated Annealing for Resource-Constrained Project Scheduling. Journal of Management in Engineering.Doi: https://doi.org/10.1061/(ASCE)ME.1943-5479.0000323

• Bianco, L. & Caramia, M., 2012. An exact algorithm to minimize the makespan in project scheduling with scarce resources and generalized precedence relations. European Journal of Operational Research, 219(1), pp. 73-85.Doi: https://doi.org/10.1016/j.ejor.2011.12.019

• Blazewicz, J., Lenstra, J. K. & Kan, A., 1983. Scheduling subject to resource constraints: classification and complexity. Discrete Applied Mathematics, 5(1), pp. 11-24.Doi: https://doi.org/10.1016/0166-218X(83)90012-4

• Boctor, F. F., 1990. Some efficient multi-heuristic procedures for resource-constrained project scheduling. European Journal of Operational Research, 49(1), pp. 3-13.Doi: https://doi.org/10.1016/0377-2217(90)90116-S

• Brucker, P., 2002. Scheduling and constraint propagation. Discrete Applied Mathematics, 123(1), pp. 227-256.Doi: https://doi.org/10.1016/S0166-218X(01)00342-0

• Brucker, P. & Knust, S., 2003. Lower bounds for resource-constrained project scheduling problems. European Journal of Operational Research, 149(2), pp. 302-313.Doi: https://doi.org/10.1016/S0377-2217(02)00762-2

• Brucker, P. & Knust, S., 2012. Complex scheduling. s.l.:Springer.

• Chen, W. et al., 2010. An efficient hybrid algorithm for resource-constrained project scheduling. Information Sciences, 180(6), pp. 1031-1039.Doi: https://doi.org/10.1016/j.ins.2009.11.044

• Chiong, R. & Siarry, P., 2012. Local search for real-world scheduling and planning. Engineering Applications of Artificial Intelligence, 25(2), pp. 207-208.Doi: https://doi.org/10.1016/j.engappai.2011.07.008

• Coelho, J. & Vanhoucke, M., 2020. Going to the core of hard resource-constrained project scheduling instances. Computers & Operations Research, Volume 121, p. 104976.Doi: https://doi.org/10.1016/j.cor.2020.104976

• Debels, D., Reyck, B. D., Leus, R. & Vanhoucke, M., 2006. A hybrid scatter search/electromagnetism meta-heuristic for project scheduling. European Journal of Operational Research, 169(2), pp. 638-653.Doi: https://doi.org/10.1016/j.ejor.2004.08.020

• Demassey, S., Artigues, C. & Michelon, P., 2005. Constraint-propagation-based cutting planes: An application to the resource-constrained project scheduling problem. INFORMS Journal on computing, 14(1), pp. 52-65.Doi: https://doi.org/10.1287/ijoc.1030.0043

• Dhivya, M. & Sundarambal, M., 2011. Cuckoo search for data gathering in wireless sensor networks. International Journal of Mobile Communications, 9(6), pp. 642-656.Doi: https://doi.org/10.1504/IJMC.2011.042781

• Diana, F.-D. M. & De La Garza, J. M., 2020. Performance of resource-constrained scheduling heuristics. Journal of Construction Engineering and Management, 146(4), p. 04020026.Doi: https://orcid.org/0000-0001-8523-9309

• Eiben, A. E., Hinterding, R. & Michalewicz, Z., 1992. Parameter control in evolutionary algorithms. Evolutionary Computation, IEEE Transactions on, 3(2), pp. 124-141.Doi: https://doi.org/10.1109/4235.771166

• Ernst, B., Bloh, M., Seume, J. R. & Gómez González, A., 2012. Implementation of the cuckoo search algorithm to optimize the design of wind turbine rotor blades. Denmark, s.n.

• Gan, L. & Xu, J., 2013. Control Risk for Multimode Resource-Constrained Project Scheduling Problems under Hybrid Uncertainty. Journal of Management in Engineering.Doi: https://doi.org/10.1061/(ASCE)ME.1943-5479.0000243

• Hartmann, S., 2002. A self‐adapting genetic algorithm for project scheduling under resource constraints. Naval Research Logistics, 49(5), pp. 433-448.Doi: https://doi.org/10.1002/nav.10029

• 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), pp. 1-14.Doi: https://doi.org/10.1016/j.ejor.2009.11.005

• Humyun Fuad, R., Chakrabortty, R. K. & Ryan, M. J., 2020. Memetic algorithm for solving resource constrained project scheduling problems. Automation in Construction, Volume 111, p. 103052.Doi: https://doi.org/10.1016/j.autcon.2019.103052

• Jamshidi, R., & Sadeghi, M. E. (2021). Neural network based human reliability analysis method in production systems. Journal of applied research on industrial engineering, 8(3), 236-250.Doi: https://doi.org/ 10.22105/JARIE.2021.277071.1274

• Jati, G. K. & Manurung, H. M., 2012. Discrete cuckoo search for traveling salesman. Seol, s.n., pp. 993 - 997.

• Khan, K. & Sahai, A., 2013. Neural-Based Cuckoo Search of Employee Health and Safety (HS). International Journal of Intelligent Systems and Applications, 5(2), pp. 76-85.

• Kochetov, Y. & Stolyar, A., 2003. Evolutionary local search with variable neighborhood for the resource constrained project scheduling problem. s.l., s.n.

• Kolisch, R., 1996. Efficient priority rules for the resource-constrained project scheduling problem. Journal of Operations Management, 14(3), pp. 179-192.Doi: https://doi.org/10.1016/0272-6963(95)00032-1

• Kolisch, R., 1996. Serial and parallel resource-constrained project scheduling methods revisited: Theory and computation. European Journal of Operational Research, 90(2), pp. 320-333.Doi: https://doi.org/10.1016/0377-2217(95)00357-6

• Kolisch R., Hartmann S. (1999) Heuristic Algorithms for the Resource-Constrained Project Scheduling Problem: Classification and Computational Analysis. In: Węglarz J. (eds) Project Scheduling. International Series in Operations Research & Management Science, vol 14. Springer, Boston, MA. https://doi.org/10.1007/978-1-4615-5533-9_7

• Kolisch, R. & Hartmann, S., 2006. Experimental investigation of heuristics for resource-constrained project scheduling: An update. European Journal of Operational Research, 174(1), pp. 23-37.Doi: https://doi.org/10.1016/j.ejor.2005.01.065

• Kolisch, R. & Padman, R., 2001. An integrated survey of deterministic project scheduling. Omega, 29(3), pp. 249-272.Doi: https://doi.org/10.1016/S0305-0483(00)00046-3

• Kolisch, R. & Sprecher, A., 1997. PSPLIB-a project scheduling problem library: OR software-ORSEP operations research software exchange program. European Journal of Operational Research, 96(1), pp. 205-216.

• Layeb, A., 2011. A novel quantum inspired cuckoo search for knapsack problems. International Journal of Bio-Inspired Computation, 3(5), pp. 297-305.Doi: https://doi.org/10.1504/IJBIC.2011.042260

• Li, K. Y. & Willis, R. J., 1992. An iterative scheduling technique for resource-constrained project scheduling. European Journal of Operational Research, 56(3), pp. 370-379.Doi: https://doi.org/10.1016/0377-2217(92)90320-9

• Lin, D., Lee, C. K. M. & Ho, W., 2013. Multi-level genetic algorithm for the resource-constrained re-entrant scheduling problem in the flow shop. Engineering Applications of Artificial Intelligence, 26(4), pp. 1282-1290.Doi: https://doi.org/10.1016/j.engappai.2012.10.006

• Mantegna, R. N., 1994. Fast, accurate algorithm for numerical simulation of Levy stable stochastic processes. Physical Review E, 49(5), pp. 4677-4683.

• Marichelvam, M. K., 2012. An improved hybrid Cuckoo Search (IHCS) metaheuristics algorithm for permutation flow shop scheduling problems. International Journal of Bio-Inspired Computation, 4(4), pp. 200-205.Doi: https://doi.org/10.1504/IJBIC.2012.048061

• Mendes, J. J. d. M., Gonçalves, J. F. & Resende, M. G., 2009. A random key based genetic algorithm for the resource constrained project scheduling problem. Computers & Operations Research, 36(1), pp. 92-109.

• Menesi, W. & Hegazy, T., 2014. Multimode Resource-Constrained Scheduling and Leveling for Practical-Size Projects. Journal of Management in Engineering.

• Mobini, M. M. et al., 2009. Using an enhanced scatter search algorithm for a resource-constrained project scheduling problem. Soft Computing, 13(6), pp. 597-610.Doi: https://doi.org/10.1007/s00500-008-0337-5

• Mohammadi, H., Ghazanfari, M., Nozari, H., & Shafiezad, O. (2015). Combining the theory of constraints with system dynamics: A general model (case study of the subsidized milk industry). International Journal of Management Science and Engineering Management, 10(2), 102-108.Doi: https://doi.org/10.1080/17509653.2014.920123

• Nozari, H., & Szmelter, A. (Eds.). (2018). Global supply chains in the pharmaceutical industry. IGI Global.Doi: http://doi:10.4018/978-1-5225-5921-4

• Nozari, H., Najafi, S. E., Jafari-Eskandari, M., & Aliahmadi, A. (2016). Providing a model for virtual project management with an emphasis on IT projects. In Project Management: Concepts, Methodologies, Tools, and Applications (pp. 476-496). IGI Global.Doi: http://doi:10.4018/978-1-5225-0196-1.ch023

• Ouaarab, A., Ahiod, B. & Yang, X.-S., 2013. Discrete cuckoo search algorithm for the travelling salesman problem. Neural Computing and Applications, pp. 1-11.Doi: https://doi.org/10.1007/s00521-013-1402-2

• Pan, N.-H., Hsaio, P.-W. & Chen, K.-Y., 2008. A study of project scheduling optimization using Tabu Search algorithm. Engineering Applications of Artificial Intelligence, 21(7), pp. 1101-1112.

• Pellerin, R., Perrier, N. & Berthaut, F., 2020. A survey of hybrid metaheuristics for the resource-constrained project scheduling problem. European Journal of Operational Research, 280(2), pp. 395-416.Doi: https://doi.org/10.1016/j.ejor.2019.01.063

• Prakash, M., Saranya, R., Jothi, R. & Vigneshwaran, A., 2012. An Optimal Job Scheduling in Grid Using Cuckoo Algorithm. International Journal of Computer Science and Telecommunications, 3(2), pp. 65-70.

• Shali, M., Irannejad, E., & Rahimi, M. (2021). Analysis of Spatial Inequalities in Tehran Metropolis. International Journal of Innovation in Management, Economics and Social Sciences, 1(2), 1–11. https://doi.org/10.52547/ijimes.1.2.1

• Shirazi, F. (2021). Managing portfolio’s risk for improving quality in a project oriented manufacture. International Journal of Innovation in Engineering, 1(1), 55–63. https://doi.org/10.52547/ijie.1.1.48

• Sprecher, A., 2000. Scheduling resource-constrained projects competitively at modest memory requirements. Management Science, 46(5), pp. 710-723.Doi: https://doi.org/10.1287/mnsc.46.5.710.12044

• Tormos, P. & Lova, A., 2001. A competitive heuristic solution technique for resource-constrained project scheduling. Annals of Operations Research, 102(1), pp. 65-81.Doi: https://doi.org/10.1023/A:1010997814183

• Valian, E., Tavakoli, S., Mohanna, S. & Haghi, A., 2013. Improved cuckoo search for reliability optimization problems. Computers & Industrial Engineering, 64(1), p. 459–468.Doi: https://doi.org/10.1016/j.cie.2012.07.011

• Valls, V., Ballestı́n, F. & Quintanilla, S., 2005. Justification and RCPSP: A technique that pays. European Journal of Operational Research, 165(2), pp. 375-386.Doi: https://doi.org/10.1016/j.ejor.2004.04.008

• Valls, V., Ballestin, F. & Quintanilla, S., 2008. A hybrid genetic algorithm for the resource-constrained project scheduling problem. European Journal of Operational Research, 185(2), pp. 495-508.Doi: https://doi.org/10.1016/j.ejor.2006.12.033

• Vanhoucke, M., 2012. Project Management with Dynamic Scheduling: Baseline Scheduling, Risk Analysis and Project Control. Berlin: Springer.

• Walton, S., Hassan, O., Morgan, K. & Brown, M. R., 2011. Modified cuckoo search: a new gradient free optimisation algorithm. Chaos, Solitons & Fractals, 44(9), pp. 710-718.Doi: https://doi.org/10.1016/j.chaos.2011.06.004

• Wang, F., He, X.-S., Wang, Y. & Yang, S.-M., 2012. Markov model and convergence analysis based on cuckoo search algorithm. Jisuanji Gongcheng/ Computer Engineering, 38(11).

• Watermeyer, K. & Zimmermann, J., 2020. A branch-and-bound procedure for the resource-constrained project scheduling problem with partially renewable resources and general temporal constraints. OR spectrum, 42(2), pp. 427-460.Doi: https://doi.org/10.1007/s00291-020-00583-z

• Yang, X.-S. & Deb, S., 2009. Cuckoo search via Lévy flights. s.l., NaBIC, pp. 210-214.Doi: https://doi.org/10.1109/NABIC.2009.5393690

• Yang, X.-S. & Deb, S., 2010. Engineering optimisation by cuckoo search. International Journal of Mathematical Modelling and Numerical Optimisation, 1(4), pp. 330-343.Doi: https://doi.org/10.1504/IJMMNO.2010.03543

• Yang, X.-S. & Deb, S., 2011. Multiobjective cuckoo search for design optimization. Computers & Operations Research, 40(6), p. 1616–1624.Doi: https://doi.org/10.1016/j.cor.2011.09.026

• Zaman, F. et al., 2021. An evolutionary approach for resource constrained project scheduling with uncertain changes. Computers & Operations Research, Volume 125, p. 105104.Doi: https://doi.org/10.1016/j.cor.2020.105104

• Zamani, R. M., 2001. A high-performance exact method for the resource-constrained project scheduling problem. Computers & Operations Research, 28(14), pp. 1387-1401.Doi: https://doi.org/10.1016/S0305-0548(00)00048-4

• Zhang, Y., Wang, L. & Wu, Q., 2012. Modified Adaptive Cuckoo Search (MACS) algorithm and formal description for global optimisation. International Journal of Computer Applications in Technology, 44(2), pp. 73-79. Doi: https://doi.org/10.1504/IJCAT.2012.048675

International Journal of Innovation in Engineering

Downloads

Published

2021-10-07

How to Cite

Mortaji, S. T. H., & Hosseinzadeh, M. . (2021). A Competitive Nature-Inspired Cuckoo Search Algorithm for Solving the Resource Constrained Project Scheduling Problem . International Journal of Innovation in Engineering, 1(3), 48–64. https://doi.org/10.59615/ijie.1.3.48

Issue

Vol. 1 No. 3 (2021): Summer

Section

Original Research

License

Copyright (c) 2021 Seyed Taha Hossein Mortaji, Mohammadreza Hosseinzadeh

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.