مروری بر مساله زمانبندی پروژه های نرم افزاری
محورهای موضوعی : شبکه های کامپیوتری و امنیت
جواد پاشایی باربین
1
*
,
مهدی جلالی
2
1 - گروه کامپیوتر، واحد نقده، دانشگاه آزاد اسلامی، نقده، ایران
2 - گروه برق، واحد نقده، دانشگاه آزاد اسلامی، نقده، ایران
کلید واژه: مساله زمانبندی پروژه‌های نرم‌افزاری, مساله زمانبندی پروژه با منابع محدود, الگوریتم‌های فرااکتشافی,
چکیده مقاله :
مساله زمانبندی پروژه‌های نرم‌افزاری یکی از مهمترین فعالیت‌ها در توسعه پروژه‌های نرم‌افزاری به‌شمار می‌آید. یکی از اصلی‌ترین دلایل عدم اتمام موفقیت‌آمیز پروژه‌های نرم‌افزاری، مطابقت نداشتن هزینه و زمانبندی برنامه‌ریزی شده و استفاده نکردن از روشهای زمانبندی کارا است. عامل اصلی برای بهاتمام رساندن پروژه‌های نرم‌افزاری مطابق با هزینه و زمانبندی برنامه‌ریزی شده، بکارگیری زمانبندی دقیق و درست است. موضوع زمانبندی پروژه‌های نرم‌افزاری، مهمترین مبحثی است که در توسعه و مدیریت پروژه می‌بایست بیش از هر موضوع دیگری به آن توجه کرد. این مساله شامل برنامه‌ریزی منابع، برآورد هزینه‌ها، نیروی انسانی و کنترل هزینه است. بنابراین، لازم است برای زمانبندی پروژه‌های نرم‌افزاری الگوریتمی اتخاذ شود که با در نظر گرفتن هزینه و محدودیت‌های منابع، بهینه‌ترین زمان برای انجام پروژه‌ها پیشبینی گردد. کاهش همزمان هزینه و زمان در توسعه پروژه‌های نرم‌افزاری برای شرکت‌های تولید نرم‌افزار بسیار لازم و ضروری است. بنابراین، بهدلیل کاهش عدم تقارن دو عامل ذکر شده در پروژه‌ها لازم است که بین زمان پروژه و هزینه موازنه‌ای صورت پذیرد. در این مقاله به بررسی و مرور مساله زمانبندی پروژه‌های نرم‌افزاری با استفاده از مدلهای کلاسیک و الگوریتم‌های هوش مصنوعی پرداخته شده است. بررسیهای به دست آمده نشان میدهد که روشهای هوش مصنوعی کارایی بهتری در مقایسه با مدلهای کلاسیک دارند.
The software project scheduling problem (SPSP) is one of the most important activities in software project development. One of the main reasons for unsuccessful software project completion is non-compliance with cost and schedule plans, often due to inefficient scheduling methods. The key factor for delivering software projects within planned cost and schedule is employing accurate and correct scheduling. SPSP is the most critical issue in project development and management, requiring more attention than any other aspect. Software project development should be fundamentally based on it. SPSP encompasses resource planning, cost estimation, manpower allocation, and cost control. Therefore, adopting an algorithm for software project scheduling that optimizes project completion time while considering cost and resource constraints is essential. Simultaneously reducing both cost and time in software project development is crucial for software production companies. Achieving a balance between project time and cost is necessary to minimize the asymmetry between these two factors. In SPSP, the most important element is the Resource Constrained Project Scheduling Problem (RCPSP). RCPSP involves assigning multiple tasks to limited-capacity resources under time constraints to optimize task scheduling with minimal time while satisfying and optimizing resource limitations. This article reviews SPSP using classical models and artificial intelligence algorithms.
- طبقه‌بندی جامع و ساخت‌یافته از روشهای زمانبندی پروژه‌های نرم‌افزاری.
- تحلیل تطبیقی دقیق عملکرد الگوریتم‌ها در سناریوهای مختلف.
- شناسایی خلأهای تحقیقاتی و جهت‌گیری‌های آینده.
[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. 4, p. 1110, 2023, 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 and 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] H. F. Rahman, R. K. Chakrabortty, and M. 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. M. Fahmy, ‘Optimization Algorithms in Project Scheduling’, Optimization Algorithms - Methods and Applications. InTech, Sept. 21, 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, and 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 Innovative Systems for Intelligent Health Informatics. IRICT 2020. Lecture Notes on Data Engineering and Communications Technologies, pp. 293-303. Cham: Springer International Publishing, 2020, doi: 10.1007/978-3-030-70713-2_28.
[39] Sh.-Ch. Chu and 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, 2013, vol. 201, pp. 417-428, doi: 10.1007/978-81-322-1038-2_35.
[43] M. Dam and M. Zachariasen, “Tabu Search on the Geometric Traveling Salesman Problem,” Meta-Heuristics: Theory and Applications, pp. 571-587, 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, p. 106185, 2023, 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.1007/s00500-008-0337-5.
[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.ins.2009.11.044.
[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, no. 2, 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, no. 2, 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, pp. 148-157, doi: 10.1007/978-3-642-15597-0_17 .
[57] 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.
[58] T. seng and L.Y. Chen, “A hybrid metaheuristic for the resource-constrained project scheduling problem,” European Journal of Operational Research, vol. 175, no. 2, pp. 707–721, 2006, doi: 10.1016/j.ejor.2005.06.014.
[59] 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.
[60] 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, no. 6, pp. 688-698, 2008, doi: 10.1016/j.ijproman.2007.09.012.
[61] 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.