A hybrid approach for solving resource-constrained software project scheduling problem

Yıl 2024, ERKEN GÖRÜNÜM, 1 - 1

Nurhan Gül , Nursal Arıcı

Öz

A software project schedule management tool is essential for monitoring the project duration and budget, two key factors that will directly affect project success. Assignment of personnel for tasks, initiation order of tasks, task completion time, possible delays in starting a task, and money already spent and the remaining budget are tracked via the software project tool. This study aims to provide software project managers with a powerful tool to solve the Resource-Constrained Software Project Scheduling Problem (RCSPSP) with minimum project duration, minimum project budget, and minimum waiting time of tasks. For this purpose, a hybrid approach is used in this study, in which the Genetic Algorithm (GA) is supported by Grey Wolf Optimization (GWO), Artificial Bee Colony Algorithm (ABC) and chaotic logistic map. The pack hierarchy model in GWO is used to contribute to the convergence success of GA, and scout bee methodology in ABC is adopted into the method to avoid being trapped at local minima. The chaotic logistic map technique is also used to improve randomness. The developed hybrid method has been tested with datasets in the Intelligent Multi-Objective Project Scheduling Environment (iMOPSE). The results are compared with in literature algorithms and statistically analyzed using non-parametrik tests. According to test results, an improvement of up to 7% in the one employee assignment model and up to 15% in the multiemployee assignment model has been observed. The results show that the method has good and competitive performance in terms of solution stability and closeness to optimal solutions.

Anahtar Kelimeler

Resource-constrained software project scheduling problem, genetic algorithm, grey wolf optimization, artificial bee colony, logistic map

Kaynak Kısıtlı Yazılım Proje Çizelgeleme Probleminin Hibrit Bir Yaklaşım ile Çözümü

Öz

Bir yazılım proje çizelgesi, proje başarısını doğrudan etkileyen iki temel faktör olan proje süresini ve bütçesini izlemek için gereklidir. Görevler için insan kaynağı ataması, göreve başlama sırası, görev tamamlama süresi, göreve başlamada olası gecikmeler, harcanan para ve kalan bütçe, yazılım proje çizelgesi ile takip edilir. Bu çalışma, yazılım proje yöneticilerine, kaynak kısıtlı yazılım proje çizelgeleme problemini minimum proje süresi, minimum proje bütçesi ve minimum görev bekleme süresi ile çözmek için güçlü bir araç sağlamayı amaçlamaktadır. Bu amaçla, bu çalışmada Genetik Algoritmanın(GA) Bozkurt Optimizasyonu(BO), Yapay Arı Kolonisi Algoritması(YAKA) ve kaotik lojistik harita ile desteklendiği hibrit bir yaklaşım kullanılmıştır. GA'nın yakınsama başarısına katkıda bulunmak için BO'daki hiyerarşi modeli, yerel minimuma takılma sorunundan kaçınmak için YAKA’daki kâşif arı metodolojisi kullanılmıştır. Daha iyi rastgelelik sağlamak adına kaotik lojistik harita kullanılmıştır. Geliştirilen hibrit yöntem Akıllı Çok Amaçlı Proje Çizelgeleme Ortamı (Intelligent Multi Objective Project Scheduling Environment - iMOPSE)’de bulunan veri setleriyle test edilmiştir. Yöntemin sonuçları, literatürdeki yöntemler ile karşılaştırılmış ve parametrik olmayan testler kullanılarak istatistiksel olarak analiz edilmiştir. Test sonuçlarına göre, tekli insan kaynağı atama modelinde %7, çoklu insan kaynağı atama modelinde ise %15 oranına varan iyileşme gözlenmiştir. Sonuçlar, yönteminin çözüm kararlılığı ve optimum çözümlere yakınsama açısından iyi ve rekabetçi bir performansa sahip olduğunu göstermiştir.

Anahtar Kelimeler

Kaynak kısıtlı yazılım proje çizelgeleme problemi, genetik algoritma, bozkurt optimizasyonu, yapay arı kolonisi algoritması, lojistik harita

Kaynakça

• [1] J. P. Lewis, “Project Planning, Scheduling, and Control: A Hands-On Guide to Bringing Projects in on Time and on Budget”, 4th edition. McGraw-Hill, (2004).
• [2] Project Management Institute, “A guide to the project management body of knowledge (PMBOK guide)”, Fifth edition. Newtown Square, Pennsylvania: Project Management Institute, Inc, (2013).
• [3] A. Başar, “A novel scheduling methodology for resource constrained projects by a new mathematical model and a hybrid metaheuristic: A case study”, Journal of the Faculty of Engineering and Architecture of Gazi University, 37(3), (2022).
• [4] A. Reza, V. Zeighami, and K. Ziarati, “Artificial Bee colony for resource constrained project scheduling problem”, International Journal of Industrial Engineering Computations, 2, (2011).
• [5] V. Nayak, H. A. Suthar, and J. Gadit, “Implementation of Artificial Bee Colony Algorithm”, IJ-AI, 1(3),(2012).
• [6] N. F. B. M. Pauzi and salleh ahmad Bareduan, “Scheduling analysis for flowship using artifical bee colony (ABC) algorithm with varying onlooker approaches”, ARPN Journal of Engineering and Applied Sciences, 11: 6472–6477, (2016).
• [7] H. M. H. Saad, R. K. Chakrabortty, S. Elsayed, and M. J. Ryan, “Quantum-Inspired Genetic Algorithm for Resource-Constrained Project-Scheduling”, IEEE Access, 9: 38488–38502, (2021).
• [8] H. F. Rahman, R. K. Chakrabortty, and M. J. Ryan, “Memetic algorithm for solving resource constrained project scheduling problems”, Automation in Construction, 111:103052, ( 2020).
• [9] X. Shen, Y. Guo, and A. Li, “Cooperative coevolution with an improved resource allocation for large-scale multi-objective software project scheduling”, Applied Soft Computing, 88: 106059, ( 2020).
• [10] M. Laszczyk and P. B. Myszkowski, “Improved selection in evolutionary multi–objective optimization of multi–skill resource–constrained project scheduling problem”, Information Sciences, 481: pp. 412–431, (2019).
• [11] M. W. Guo, J. S. Wang, L. F. Zhu, S. S. Guo, and W. Xie, “An Improved Grey Wolf Optimizer Based on Tracking and Seeking Modes to Solve Function Optimization Problems”, IEEE Access, 8: 69861–69893, (2020).
• [12] W. Xiao, H. Deng, Y. Sheng, and L. Hu, “Factored grey wolf optimizer with application to resource-constrained project scheduling”, International Journal of Innovative Computing, Information and Control, 14: 881–897, (2018).
• [13] T. Jiang and C. Zhang, “Application of Grey Wolf Optimization for Solving Combinatorial Problems: Job Shop and Flexible Job Shop Scheduling Cases”, IEEE Access, 6: 26231–26240, (2018).
• [14] H. D. Quoc, L. Nguyen The, C. N. Doan, and T. Phan Thanh, “Solving Resource Constrained Project Scheduling Problem by a Discrete Version of Cuckoo Search Algorithm”, 2019 6th NAFOSTED Conference on Information and Computer Science (NICS), Hanoi, Vietnam, 2019: 73–76, (2019).
• [15] K. Bibiks, Y.-F. Hu, J.-P. Li, P. Pillai, and A. Smith, “Improved discrete cuckoo search for the resource-constrained project scheduling problem”, Applied Soft Computing, 69: 493–503, (2018).
• [16] B. Afshar-Nadjafi, “A solution procedure for preemptive multi-mode project scheduling problem with mode changeability to resumption”, Applied Computing and Informatics, 14(2), (2018).
• [17] M. Ali, S. Ullah, and M. Jahanzaib, “A Resource Optimisation Based Heuristic For Resource Constrained Project Scheduling Problem”, NEDJR, XVI(4),(2019).
• [18] M. Rauf, Z. Guan, L. Yue, Z. Guo, J. Mumtaz, and S. Ullah, “Integrated Planning and Scheduling of Multiple Manufacturing Projects Under Resource Constraints Using Raccoon Family Optimization Algorithm”, IEEE Access, 8: 151279–151295, (2020).
• [19] M. Á. Vega-Velázquez, A. García-Nájera, and H. Cervantes, “A survey on the Software Project Scheduling Problem”, International Journal of Production Economics, 202: 145–161, (2018).
• [20] J. Snauwaert and M. Vanhoucke, “A new algorithm for resource-constrained project scheduling with breadth and depth of skills”, European Journal of Operational Research, 292(1), (2021).
• [21] A. Ghamginzadeh, A. A. Najafi, and M. Khalilzadeh, “Multi-Objective Multi-Skill Resource-Constrained Project Scheduling Problem Under Time Uncertainty”, Int. J. Fuzzy Syst., 23(2), (2021).
• [22] H. Dai and W. Cheng, “A Memetic Algorithm for Multiskill Resource-Constrained Project Scheduling Problem under Linear Deterioration”, Mathematical Problems in Engineering, 2019: 1–16, (2019).
• [23] Y. Guo, J. Ji, J. Ji, D. Gong, J. Cheng, and X. Shen, “Firework-based software project scheduling method considering the learning and forgetting effect”, Soft Computing, 23(13): 5019–5034, (2019).
• [24] J. Blazewicz, J. K. Lenstra, and A. H. G. R. Kan, “Scheduling subject to resource constraints: classification and complexity”, Discrete Applied Mathematics, 5(1), (1983).
• [25] F. Uysal, “Hybrid meta-heuristic algorithms for the resource constrained multi-project scheduling problem”, Doctoral dissertation, Middle East Technical University, Ankara, (2014).
• [26] http://imopse.ii.pwr.wroc.pl, Wrocław University of Science and Technology, “Intelligent Multi Objective Project Scheduling Environment”, (2021).
• [27] P. B. Myszkowski, M. Laszczyk, I. Nikulin, and M. Skowroński, “iMOPSE: a library for bicriteria optimization in Multi-Skill Resource-Constrained Project Scheduling Problem”, Soft Computing, 23(10), (2019).
• [28] H. D. Quoc, L. N. The, C. N. Doan, and T. P. Thanh, “New Effective Differential Evolution Algorithm for the Project Scheduling Problem”, 2nd International Conference on Computer Communication and the Internet (ICCCI), Nagoya, Japan, 2020: 150–157, (2020).
• [29] P. B. Myszkowski, Ł. P. Olech, M. Laszczyk, and M. E. Skowroński, “Hybrid Differential Evolution and Greedy Algorithm (DEGR) for solving Multi-Skill Resource-Constrained Project Scheduling Problem”, Applied Soft Computing, 62: 1–14, (2018).
• [30] P. B. Myszkowski, M. Skowroński, and K. Sikora, “A new benchmark dataset for Multi-Skill Resource-Constrained Project Scheduling Problem”, Proceedings of the Federated Conference on Computer Science and Information Systems, 5: 129–138, (2015).
• [31] A. M. Fahmy, “Optimization Algorithms in Project Scheduling”, Optimization Algorithms - Methods and Applications, O. Baskan, Ed. InTech, (2016).
• [32] F. Meziane and S. Vadera, Eds., Artificial Intelligence Applications for Improved Software Engineering Development: New Prospects. IGI Global, (2010).
• [33] N. Yavuz, “Relible data transfer in chaotic systems”, M.S. Thesis, Karadeniz Technical University, Trabzon, Turkey, (2006).
• [34] A. R. Ozoren, “Random Number Generation Using Chaotic Dynamical Maps”, M.S. Thesis, Boğaziçi University, Istanbul, Turkey, (2011).
• [35] S. Wu, H.-D. Wan, S. K. Shukla, and B. Li, “Chaos-based improved immune algorithm (CBIIA) for resource-constrained project scheduling problems”, Expert Systems with Applications, 38(4), (2011).
• [36] D. Tian, “Particle Swarm Optimization with Chaotic Maps and Gaussian Mutation for Function Optimization”, IJGDC, 8(4), (2015).
• [37] G. Yan and C. Li, “An Effective Refinement Artificial Bee Colony Optimization Algorithm Based On Chaotic Search and Application for PID Control Tuning”, Journal of Computational Information Systems,7(9) , (2010).
• [38] F. Gargiulo and D. Quagliarella, “Genetic Algorithms for the Resource Constrained Project Scheduling Problem”, 2012 IEEE 13th International Symposium on Computational Intelligence and Informatics (CINTI), Budapest, Hungary, 2012: 39–47, (2012).
• [39] S. Mirjalili, S. M. Mirjalili, and A. Lewis, “Grey Wolf Optimizer”, Advances in Engineering Software, 69: 46–61, (2014).
• [40] S. Mirjalili, S. Saremi, S. M. Mirjalili, and L. dos S. Coelho, “Multi-objective grey wolf optimizer: A novel algorithm for multi-criterion optimization”, Expert Systems with Applications, 47: 106–119, (2016).
• [41] Q. Tu, X. Chen, and X. Liu, “Hierarchy Strengthened Grey Wolf Optimizer for Numerical Optimization and Feature Selection”, IEEE Access, 7: 78012–78028, (2019).
• [42] X. Zhou, F. Miao, and H. Ma, “Genetic Algorithm with an Improved Initial Population Technique for Automatic Clustering of Low-Dimensional Data”, Information, 9(4): 101, (2018).