Software Project Scheduling Problem: A Review

Javad Pashaei Barbin ¹ ( Department of Computer Engineering- Naghadeh Branch, Islamic Azad University )
Mahdi Jalali ² ( Department of Electrical Engineering, Naghadeh Branch, Islamic Azad University, Naghadeh , Iran )

Submited date : 2024-04-23 Accepted date : 2024-06-26

Keywords: Software project scheduling problem, Software projects, Project scheduling problem with limited resources, Heuristic algorithms.,

Abstract :

The software project scheduling problem (SPSP) is one of the most important activities in the development of software projects. The main factor for completing software projects according to the planned cost and schedule is the use of accurate and correct scheduling. SPSP includes resource planning, cost estimation, manpower and cost control. Therefore, it is necessary to adopt an algorithm for the scheduling of software projects that considers the best time to complete the projects, taking into account the cost and resource limitations. The simultaneous reduction of cost and time in the development of software projects is very necessary and essential for software production companies. Therefore, due to the reduction of the asymmetry of the two factors mentioned in the projects, it is necessary to make a balance between the project time and the cost. In SPSP, the most important element is the Resource Constrained Project Scheduling Problem (RCPSP). RCPSP includes assigning a number of tasks to a resource or resources with limited capacity and time constraints to achieve the optimization of task scheduling with minimum time.

Highlights:

Investigating software project scheduling techniques and comparing the types of methods

Expression of methods, main idea of ​​the method, advantages and disadvantages of the methods

Introducing classical methods and artificial intelligence methods used in this field and comparing the methods

 Shows that artificial intelligence methods have better performance compared to classical models.

References:

[1] M.C. Abeyasinghe, D.J. Greenwood and D.E. Johansen, “An Efficient Method for Scheduling Construction Projects with Resource Constraints”, International Journal of Project Management, vol. 19, no. 1, pp. 29-45, 2001, doi:10.1016/S0263-7863(00)00024-7.
[2] M. Lu and H. Li, “Resource Activity Critical Path Method for Construction Planning,” Journal of Construction Engineering and Management, vol. 129, no. 4, pp. 412-420, 2003, doi: 10.1061/(ASCE)0733-9364(2003)129:4(412).
[3] W. Herroelen, E. Demeulemeester and B.D. Reyck, “Resource Constrained Project Scheduling: A Survey of Recent Developments,” Computers & Operations Research, vol. 25, no. 4, pp. 279-302, 1998, doi:10.1016/S0305-0548(97)00055-5.
[4] E. Demeulemeester, “Minimizing Resource Availability Costs in Time-limited Project Networks,”Management Science, vol. 41, pp. 1590-1598, 1995, doi:10.1287/mnsc.41.10.1590.
[5] J. Zhang, X. Shen and C. Yao, "Evolutionary Algorithm for Software Project Scheduling Considering Team Relationships," in IEEE Access, vol. 11, pp. 43690-43706, 2023, doi: 10.1109/ACCESS.2023.3270163.
[6] S. Zhang, X. Song, L. Shen and L. Xu, "Complicated Time-Constrained Project Scheduling Problems in Water Conservancy Construction," Processes, vol. 11, no. 1110, doi:10.3390/pr11041110.
[7] D.G. Malcolm, J.H. Roseboom, C.E. Clark and W. Fazar, “Application of a Technique for Research and Development Program Evaluation,” Operate Res, vol. 7, no. 5, pp. 646-69, 1959, doi: 10.1287/opre.7.5.646.
[8] W. Fix, K. Neumann, “Project Scheduling by Special GERT Networks,” Computing, vol. 23, pp. 299-308, 1979, doi:10.1007/BF02252134.
[9] J.P. Pantouvakis and O.G. Manoliadis, “A Practical Approach to Resource Constrained Project Scheduling,” Operational Research an International Journal, vol. 6, no. 3, pp.299-309, 2006, doi: 10.1007/BF02941258.
[10] J. Holland, “Adaptation in Natural and Artificial Systems,” University of Michigan, Michigan, USA, April 29, 1992.
[11] J. Liu, Y. Liu, Y. Shi and J. Li, “Solving Resource-Constrained Project Scheduling Problem via Genetic Algorithm,” Journal of Computing in Civil Engineering, vol. 34, no. 2, 2020, doi: 10.1061/(ASCE)CP.1943-5487.0000874.
[12] C.K. Chang, Hsin-yi Jiang, Y. Di, D. Zhu and Y. Ge, “Time-line Based Model for Software Project Scheduling with Genetic Algorithms,” Information and Software Technology, vol. 50, pp. 1142-1154, 2008, doi:10.1016/j.infsof.2008.03.002.
[13] J. Lin, L. Zhu and K. Gao, “A genetic programming hyper-heuristic approach for the multi-skill resource constrained project scheduling problem,” Expert Systems with Applications, vol. 140, p. 112915, 2020, doi:10.1016/j.eswa.2019.112915.
[14] M. Pablo, “On Evolution, Search, Optimization, Genetic Algorithms and Martial Arts towards Memetic Algorithms Caltech Concurrent Computation Program,” C3P Report, 1989.
[15] L. Wang and J. Liu, “A Scale-Free Based Memetic Algorithm for Resource-Constrained Project Scheduling Problems,” LNCS, vol. 8206, pp. 202-209, 2013, doi:10.1007/978-3-642-41278-3_25.
[16] Humyun Fuad Rahman, Ripon K. Chakrabortty, Michael J. Ryan, “Memetic algorithm for solving resource constrained project scheduling problems,” Automation in Construction, vol. 111, p. 103052, 2020, doi:10.1016/j.autcon.2019.103052.
[17] M. Dorigo and L. M.Gambardella, “The Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem,” IEEE Transactions on Evolutionary Computation, vol. 1, no.1, April 1997, doi: 10.1109/4235.585892.
[18] J. Xiao, X. T. Ao and Y. Tang, “Solving Software Project Scheduling Problems with Ant Colony Optimization,” Computers & Operations Research, vol. 40, pp. 33-46, 2013, doi:10.1016/j.cor.2012.05.007.
[19] W. -N. Chen and J. Zhang, "Ant Colony Optimization for Software Project Scheduling and Staffing with an Event-Based Scheduler," in IEEE Transactions on Software Engineering, vol. 39, no. 1, pp. 1-17, Jan. 2013, doi: 10.1109/TSE.2012.17.
[20] W. Deng, J. Xu and H. Zhao, "An Improved Ant Colony Optimization Algorithm Based on Hybrid Strategies for Scheduling Problem," in IEEE Access, vol. 7, pp. 20281-20292, 2019, doi: 10.1109/ACCESS.2019.2897580.
[21] J. Kennedy and R. C. Eberhart, “Particle Swarm Optimization,” in Proceedings of the IEEE International Conference on Neural Networks, pp. 1942-1948, 1995, doi: 10.1109/ICNN.1995.488968.
[22] A. Fahmy, “Optimization Algorithms in Project Scheduling,” 2016, doi: 10.5772/63108.
[23] Q. Jia and Y. Seo, “An Improved Particle Swarm Optimization for the Resource-Constrained Project Scheduling Problem,” Int J Adv Manuf Technol, vol. 67, pp. 2627-2638, 2013, doi: 10.1007/s00170-012-4679-x.
[24] R.-M. Chen, Ch.-L. Wub, Ch.-M. Wang, Sh.-T. Lo, “Using Novel Particle Swarm Optimization Scheme to Solve Resource-Constrained Scheduling Problem in PSPLIB,” Expert Systems with Applications, vol. 37, no. 3, pp. 1899-1910, 2010, doi:10.1016/j.eswa.2009.07.024.
[25] H. Zhang, X. Li, Heng Li and F. Huang, “Particle Swarm Optimization-based Schemes for Resource-Constrained Project Scheduling,” Automation in Construction, vol. 14, pp. 393-404, 2005, doi:10.1016/j.autcon.2004.08.006.
[26] G. Koulinas, L. Kotsikas and K. Anagnostopoulos, “A particle swarm optimization based hyper-heuristic algorithm for the classic resource constrained project scheduling problem,” Information Sciences, vol. 277, 2014, pp. 680-693, doi:10.1016/j.ins.2014.02.155.
[27] Y. Zhang, X. Hu, X. Cao and Ch. Wu, “An efficient hybrid integer and categorical particle swarm optimization algorithm for the multi-mode multi-project inverse scheduling problem in turbine assembly workshop,” Computers & Industrial Engineering, vol. 169, 2022, doi:10.1016/j.cie.2022.108148.
[28] D. Karaboga, “An Idea Based on Honeybee Swarm for Numerical Optimization,” Technical Report TR06, Erciyes University, Engineering Faculty, Computer Engineering Department, 2005.
[29] B. Crawford, R. Soto, F. Johnson, M. Vargas, S. Misra and F. Paredes, “A Scheduling Problem for Software Project Solved with ABC Metaheuristic,” Computational Science and Its Applications. ICCSA 2015. Lecture Notes in Computer Science, vol. 9158, Springer, Cham, doi:10.1007/978-3-319-21410-8_48.
[30] N. Nouri, S. Krichen, T. Ladhari and P. Fatimah, "A discrete artificial bee colony algorithm for resource-constrained project scheduling problem," 5th International Conference on Modeling, Simulation and Applied Optimization (ICMSAO), Hammamet, Tunisia, 2013, pp. 1-6, doi: 10.1109/ICMSAO.2013.6552557.
[31] Y.J. Shi, F.Zh. Qu, W. Chen and B. Li, ”An Artificial Bee Colony with Random Key for Resource-Constrained Project Scheduling”, LNCS, Vol. 6329, pp. 148-157, Springer, 2010, doi: 10.1007/978-3-642-15597-0_17.
[32] H. Li, X. Li and L. Gao, ”A discrete artificial bee colony algorithm for the distributed heterogeneous no-wait flowshop scheduling problem,” Applied Soft Computing, vol. 100, p. 106946, 2021, doi:10.1016/j.asoc.2020.106946.
[33] J. Farmer, N. Packard and A. Perelson, “The Immune System, Adaptation and Machine Learning,” Physica D, vol. 2, pp. 187-204, 1986, doi:10.1016/0167-2789(86)90240-X.
[34] M. Mobini, Z. Mobini and M. Rabbani, “An Artificial Immune Algorithm for the Project Scheduling Problem under Resource Constraints,” Applied Soft Computing, vol. 11, pp. 1975-1982, 2011, doi:10.1016/j.asoc.2010.06.013.
[35] R. Agarwal, M. K. Tiwari and S. K. Mukherjee, “Artificial Immune System Based Approach for Solving Resource Constraint Project Scheduling Problem,” Int J Adv Manuf Technol , vol. 34, pp. 584-593, 2007, doi: 10.1007/s00170-006-0631-2.
[36] M. Eusuff, K. Lansey and F. Pasha, “Shuffled Frog-Leaping Algorithm: A Memetic Meta-heuristic for Discrete Optimization,” Engineering Optimization, vol. 38, no. 2, pp. 129-54, 2006, doi:10.1080/03052150500384759.
[37] C. Fang and L. Wang, “An Effective Shuffled Frog-Leaping Algorithm for Resource-Constrained Project Scheduling Problem,” Computers & Operations Research, vol. 39, pp. 890-901, 2012, doi:10.1016/j.cor.2011.07.010.
[38] O.A. Ameen et al.,"Application of shuffled frog-leaping algorithm for optimal software project scheduling and staffing," in International Conference of Reliable Information and Communication Technology, pp. 293-303. Cham: Springer International Publishing, 2020, doi: 10.1007/978-3-030-70713-2_28.
[39] Sh.-Ch. Chu, P.-W. Tsai “Computational Intelligence Based on the Behavior of Cats,” International Journal of Innovative Computing, Information and Control, vol. 3, no. 1, 2007.
[40] L. Xu and W. Hu, “Cat swarm Optimization-based Schemes for Resource-Constrained Project Scheduling,” Applied Mechanics and Materials Vols. 220-223, pp. 251-258, 2012, doi:10.4028/www.scientific.net/AMM.220-223.251.
[41] X.S. Yang, Nature-Inspired Meta-heuristic Algorithms. Luniver Press, 2008.
[42] P. Sanaei, R. Akbari, V. Zeighami and S. Shams, “Using Firefly Algorithm to Solve Resource Constrained Project Scheduling Problem,” Proceedings of Seventh International Conference on Bio-Inspired Computing: Theories and Applications, Advances in Intelligent Systems and Computing, vol. 201, pp. 417-428, 2013, doi: 10.1007/978-81-322-1038-2_35.
[43] M. Dam and M. Zachariasen, “Tabu Search on the Geometric Traveling Salesman Problem,” manuscript, 1995, doi:10.1007/978-1-4613-1361-8_34.
[44] O. Atli and C. Kahraman, “Fuzzy Resource-Constrained Project Scheduling Using Taboo Search Algorithm,” International Journal of Intelligent Systems, vol. 27, pp. 873-907, 2012, doi:10.1002/int.21552.
[45] Y. Ma, Zh. He, N. Wang and E. Demeulemeester “D. Erik. Tabu search for proactive project scheduling problem with flexible resources,” Computers & Operations Research, vol. 153, no. 2, 2023, p. 106185, doi: 10.1016/j.cor.2023.106185.
[46] F. Glover, “A Template for Scatter Search and Path Relinking,” Lecture Notes in Computer Science, vol. 1363, pp. 13-54. 1997, doi:10.1007/BFb0026589.
[47] T. Sari, V. Cakir, S. Kilic and E. Ece, "Evaluation of scatter search and genetic algorithm at resource constrained project scheduling problems," 15th IEEE International Conference on Intelligent Engineering Systems, Poprad, Slovakia, 2011, pp. 127-130, doi: 10.1109/INES.2011.5954732.
[48] M. D. Mahdi Mobini, M. Rabbani, M. S. Amalnik, J. Razmi and A. R. Rahimi-Vahed, “Using an enhanced scatter search algorithm for a resource-constrained project scheduling problem,” Soft Computing, vol. 13, pp. 597-610, 2009, doi:10.1016/j.ejor.2004.08.019.
[49] D. S. Yamashita, V.A. Armentano and M. Laguna, “Scatter Search for Project Scheduling with Resource Availability Cost,” European Journal of Operational Research, vol. 169, pp. 623-637, 2006, doi:10.1016/S1568-4946(02)00065-0.
[50] K.W. Kima, M. Genb and G. Yamazaki, “Hybrid Genetic Algorithm with Fuzzy Logic for Resource-Constrained Project Scheduling,” Applied Soft Computing, vol. 2/3F, pp. 174-188, 2003, doi:10.1016/j.ins.2009.11.044.
[51] W. Chen, Y.-J. Shi, H.-F Teng, X.P. Lan and L.-C. Hu, “An Efficient Hybrid Algorithm for Resource-Constrained Project Scheduling,” Information Sciences, vol. 180, pp. 1031-1039, 2010, doi:10.1016/j.ejor.2004.08.020.
[52] D. Debels, B.De Reyck, R. Leus and M. Vanhoucke, “A Hybrid Scatter Search/Electromagnetism Meta-Heuristic for Project Scheduling,” European Journal of Operational Research, vol. 169, pp. 638-653, 2006, doi:10.1016/j.ejor.2004.08.020.
[53] S. K. Shukla, Y. J. Son and M.K. Tiwari, “Fuzzy-based Adaptive Sample-Sort Simulated Annealing for Resource-Constrained Project Scheduling,” International Journal Advanced Manuf Technol, vol. 36, pp. 982-995, 2008, doi:10.1007/s00170-006-0907-6.
[54] S. Proon and M. Jin, “A Genetic Algorithm with Neighborhood Search for the Resource-Constrained Project Scheduling Problem,” Naval Research Logistics, vol. 58, pp. 74-82, 2011, doi:10.1002/nav.20439.
[55] V. Valls, F. Ballestín and S. Quintanilla, “Justification and RCPSP: A technique that pays”, European Journal of Operational Research, vol. 165, pp. 375–386, 2005, doi: 10.1016/j.ejor.2004.04.008.
[56] Y. j. Shi, F.Z. Qu, W. Chen and B. Li, “An Artificial Bee Colony with Random Key for Resource-Constrained Project Scheduling, ” Life System Modeling and Intelligent Computing. ICSEE LSMS 2010. Lecture Notes in Computer Science, vol 6329, 2010, doi:10.1007/978-3-642-15597-0_17.
[57] D. Debels, B. De Reyck, R. Leus, M. Vanhoucke, “A hybrid scatter search/electromagnetism meta-heuristic for project scheduling”, European Journal of Operational Research, vol. 169, pp. 638–653, 2006, doi:10.1016/j.ejor.2004.08.020.
[58] K. Nonobe and T. Ibaraki, “Formulation and tabu search algorithm for the resource constrained project scheduling problem,” Hansen, P. (ed.) Essays and Surveys in Metaheuristics, pp. 557–588, Kluwer Academic Publishers, Dordrecht, 2001, doi:10.1007/978-1-4615-1507-4_25.
[59] T. seng and L.Y. Chen, “A hybrid metaheuristic for the resource-constrained project scheduling problem,” European Journal of Operational Research, vol. 175, pp. 707–721, 2006, doi: 10.1016/j.ejor.2005.06.014.
[60] A. Agarwal, V.S. Jacob and H. Pirkul, “Augmented Neural Networks for Task Scheduling,” European Journal of Operational Research, vol. 151, no. 3, pp. 481-502, 2003, doi:10.1016/S0377-2217(02)00605-7.
[61] L.D. Long and A. Ohsato, “Fuzzy critical chain method for project scheduling under resource constraints and uncertainty,” International Journal of Project Management, vol. 26, pp. 688-698, 2008, doi:10.1016/j.ijproman.2007.09.012.
[62] W. Huang, L. Ding, B. Wen and B. Cao, “Project Scheduling Problem for Software Development with Random Fuzzy Activity Duration Times”, LNCS, vol. 5552, pp. 60-69, 2009, doi: 10.1007/978-3-642-01510-6_8.