Kaynak Dengeleme Probleminin Arama Uzayını Paralel Programlama ile Tarayarak Kesin Çözümü

Abstract

Kaynak dengeleme problemi (KDP) sezgisel, modern sezgisel ve matematiksel yöntemlerle çözülmektedir. Fakat belirtilen yöntemler özellikle büyük boyutlu problemler için kesin çözümü garanti edememektedir. Bu çalışmada KDP'nin aktiviteler arasındaki bağımlılık ilişkilerini ihlal etmeden ve proje süresinde uzamaya neden olmayacak şekilde bolluğu olan aktivitelerin ertelenmesi ile elde edilebilecek birbirinden farklı kaç iş programı oluşturulabileceği hesaplanmıştır. Arama uzayı olarak tanımlanan tüm uygulanabilir iş programlarının tamamının denenmesi ile garantili biçimde KDP'nin en iyi çözümü elde edilerek mevcut yöntemlerden farklı biçimde KDP'nin çözülmesi sağlanmıştır. Aktivite sayısı ile arama uzayı arasında seri bağlı aktiviteler için üstel bağıntı formülü türetilerek büyük projelerin tek işlemci ile çözümünün makul sürede gerçekleşemeyeceği belirlenmiştir. Problemin paralel programlama ile tüm işlemcilere eşit sayıda şebeke çözümü düşecek şekilde paylaştırılması sağlanmıştır. Bu çalışmada en büyüğü 36 aktiviteli olan 4 KDP arama uzayının tamamı taranıp makul sürede çözülerek geliştirilen yöntemin uygulanabilir olduğu kanıtlanmıştır. Bu yöntem ile daha küçük parçalara ayırmak sureti ile daha büyük kaynak dengeleme problemlerinin kesin çözümü elde edilebilecektir.

Keywords

• Kaynak Dengeleme Problemi
• Optimizasyon
• Kritik Yol Yöntemi

Exact Solution of Resource Leveling Problem by Exhaustive Enumeration with Parallel Programming

Abstract

Resource Leveling Problem (RLP) is solved by heuristic, meta-heuristic, and mathematical methods. However, the aforementioned methods cannot guarantee the exact solution for large size problems. In this study, number of feasible schedules which can be obtained by delaying the non-critical activities without violating the precedence relationships and elongating the project completion time are computed. All of the feasible schedules which can be defined as the search domain are enumerated and the guaranteed optimum solution for the RLP is obtained by a different method from the existing methods. Exponential equation between the search domain and the number of activities on serial path is derived and the insolvability of large RLP in a reasonable time by one central processing unit is verified. Partitioning of the problem into equal sizes is provided by parallel programming so that each particle contains the same number of enumeration. In this study, four RLP in which the largest problem has 36 activities are solved by exhaustive enumeration within reasonable solution time and it is proved that the proposed method is applicable. Exact solutions of larger problems can also be obtained by the proposed method if the problem is partitioned into smaller sizes.

Keywords

• Resource Leveling Problem
• Optimization
• Critical Path Method

References

1. [1] Ahbab, C., Daneshvar, S., ve Celik, T. (2019). Cost and Time Management Efficiency Assessment for Large Road Projects Using Data Envelopment Analysis. Teknik Dergi, 30(2), 8937-8959.
2. [2] Kolisch, R., ve Padman, R. (2001). "An integrated survey of deterministic project scheduling." Omega, 29(3), 249-272.
3. [3] Li, H., ve Demeulemeester, E. (2016). A genetic algorithm for the robust resource leveling problem. Journal of Scheduling, 19(1), 43-60.
4. [4] Tarasov, I., Haït, A., ve Battaïa, O. (2020). A Generalized MILP Formulation for the Period-Aggregated Resource Leveling Problem with Variable Job Duration. Algorithms, 13(1), 6.
5. [5] Li, H., ve Dong, X. (2018). Multi-mode resource leveling in projects with mode-dependent generalized precedence relations. Expert Systems with Applications, 97, 193-204.
6. [6] Abadi N.S., Bagheri N. ve Assadi M., (2018). Multiobjective model for solving resource‐leveling problem with discounted cash flows. International Transactions in Operational Research, 25(6), 2009-2030.
7. [7] Doulabi Hossein Hashemi, S., Seifi, A., ve Shariat, S. Y. (2011). "Efficient hybrid genetic algorithm for resource leveling via activity splitting". Journal of Construction Engineering and Management, 137(2), 137-146.
8. [8] Harris, R. B. (1990). Packing method for resource leveling (PACK). Journal of Construction Engineering and Management, 116(2), 331-350.

9. [9] Hiyassat, M. A. S. (2001). Applying modified minimum moment method to multiple resource leveling. Journal of Construction Engineering and Management, 127(3), 192-198.
10. [10] Rieck, J., Zimmermann, J., ve Gather, T. (2012). "Mixed-integer linear programming for resource leveling problems." European Journal of Operational Research, 221(1), 27-37.
11. [11] Neumann, K., Schwindt, C., ve Zimmermann, J. (2012). "Project scheduling with time windows and scarce resources: temporal and resource-constrained project scheduling with regular and nonregular objective functions." Springer Science & Business Media.
12. [12] Hegazy, T. (1999). Optimization of resource allocation and leveling using genetic algorithms. Journal of construction engineering and management,125(3), 167-175.
13. [13] Son, J., ve Skibniewski, M. J. (1999). "Multiheuristic approach for resource leveling problem in construction engineering: Hybrid approach." J. Constr. Eng. Manage., 125(1), 23-31.
14. [14] Leu, S. S., Yang, C. H., ve Huang, J. C. (2000). "Resource leveling in construction by genetic algorithm-based optimization and its decision support system application." Autom. Constr., 10(1), 27-41.
15. [15] Zheng, D. X., Ng, S. T., ve Kumaraswamy, M. M. (2003). "GA-based multiobjective technique for multi-resource leveling." Bridges, 10(40671), 29.
16. [16] El-Rayes, K., ve Jun, D. H. (2009). "Optimizing resource leveling in construction projects." J. Constr. Eng. Manage., 135(11), 1172-1180.
17. [17] Christodoulou, S. E., Ellinas, G., ve Michaelidou-Kamenou, A. (2009). "Minimum moment method for resource leveling using entropy maximization." J. Constr. Eng. Manage., 136(5), 518-527.
18. [18] Ponz-Tienda, J. L., Yepes, V., Pellicer, E., ve Moreno-Flores, J. (2013). "The resource leveling problem with multiple resources using an adaptive genetic algorithm." Automation in Construction, 29, 161-172.
19. [19] Li, H., Xiong, L., Liu, Y., ve Li, H. (2017). "An effective genetic algorithm for the resource levelling problem with generalised precedence relations." International Journal of Production Research, 1-22.
20. [20] Qi, J. X., Wang, Q., and Guo, X. Z. (2007). "Improved particle swarm optimization for resource leveling problem." In IEEE International Conference on Machine Learning and Cybernetics, 2, 896-901.
21. [21] Li, Z., Wuliang, P., and Zhongliang, Z. (2010). "An ant colony system for solving resource leveling problem." In IEEE Int. Conf. Intell. Comp. Tech. and Autom. (ICICTA), 1, 489-492.
22. [22] Geng, J. Q., Weng, L. P., and Liu, S. H. (2011). "An improved ant colony optimization algorithm for nonlinear resource-leveling problems." Comput. Math. Appl., 61(8), 2300-2305.
23. [23] Tran, H. H., and Hoang, N. D. (2014). "A novel resource-leveling approach for construction project based on differential evolution." J. Constr. Eng., http://dx.doi.org/10.1155/2014/648938.
24. [24] Xu, X., Hao, J., ve Zheng, Y. (2020). Multi-objective artificial bee colony algorithm for multi-stage resource leveling problem in sharing logistics network. Computers & Industrial Engineering, 142, 106338.
25. [25] Prayogo, D., ve Kusuma, C.T. (2019). Optimization of resource leveling problem under multiple objective criteria using a symbiotic organisms search. Civil Engineering Dimension, 21(1), 43-49.
26. [26] Prayogo, D., Cheng, M. Y., Wong, F. T., Tjandra, D., ve Tran, D. H. (2018). Optimization model for construction project resource leveling using a novel modified symbiotic organisms search. Asian Journal of Civil Engineering, 19(5), 625-638.
27. [27] Erzurum, T. ve Bettemir, Ö.H. "Kaynak Dengeleme Problemlerinin Arama Uzayının Belirlenmesi Determination of Search Domain of Resource Leveling Problem", Uluslararası Katılımlı 7. İnşaat Yönetimi Kongresi, pp. 437-453, 6-7 Ekim 2017 Samsun Türkiye.
28. [28] Toğan, V., ve Eirgash, M. A. (2018). Time-Cost Trade-Off Optimization with a New Initial Population Approach. Teknik Dergi, 30(6).
29. [29] Karaa, F. A., ve Nasr, A. Y. (1986). Resource management in construction. Journal of construction engineering and management, 112(3), 346-357.
30. [30] Takamoto, M., Yamada, N., Kobayashi, Y., Nonaka, H., and Okoshi, S. (1995). "Zero‐one quadratic programming algorithm for resource leveling of manufacturing process schedules." Systems and Computers in Japan, 26(10), 68-76.
31. [31] Easa, S. M. (1989). "Resource leveling in construction by optimization." J. Constr. Eng. Manage., 115(2), 302-316.
32. [32] Hariga, M., and El-Sayegh, S. M. (2010). Cost optimization model for the multiresource leveling problem with allowed activity splitting. Journal of Construction Engineering and Management, 137(1), 56-64.
33. [33] Gather, T., Zimmermann, J., and Bartels, J. H. (2011). "Exact methods for the resource levelling problem." Journal of Scheduling, 14(6), 557-569.
34. [34] Rieck, J., ve Zimmermann, J. (2015). "Exact methods for resource leveling problems." In Handbook on Project Management and Scheduling Vol. 1 (pp. 361-387). Springer International Publishing.
35. [35] Mattila, K. G. ve Abraham, D. M. (1998). Resource leveling of linear schedules using integer linear programming. Journal of Construction Engineering and Management, 124(3), 232-244.
36. [36] Erzurum T., ve Bettemir Ö.H. (2018). Optimum or Near-Optimum Resolution of Resource Leveling Problems with Spreadsheet Application. 5th International Project and Construction Management Conference (IPCMC 2018), pp. 1285-1299.
37. [37] Bettemir, Ö.H., Erzurum T. (2019), "Comparison of resource distribution metrics on multi-resource projects", Journal of Construction Engineering, Management & Innovation, 2(2), pp. 93-102.
38. [38] Erzurum T. (2019), "Kaynak Dengeleme Probleminin Optimum veya Yakın Optimum Çözülmesi", İnönü Üniversitesi Fen Bilimleri Enstitüsü, Yüksek Lisans Tezi.
39. [39] El-Rayes, K. ve Kandil, A. (2004). Distributed Computing for the Optimization of Large-Scale Construction Projects.
40. [40] Kandil, A. ve El-Rayes, K. (2005). Parallel computing framework for optimizing construction planning in large-scale projects. Journal of computing in civil engineering, 19(3), 304-312.
41. [41] Kandil, A. ve El-Rayes, K. (2006). Parallel genetic algorithms for optimizing resource utilization in large-scale construction projects. Journal of Construction engineering and Management, 132(5), 491-498.
42. [42] Kandil, A., El-Rayes, K. ve El-Anwar, O. (2010). Optimization research: Enhancing the robustness of large-scale multiobjective optimization in construction. Journal of Construction Engineering and Management, 136(1), 17-25.
43. [43] Sayar, A., ve Ergün, U. (2014). Fonksiyonel Programlama Dilleri ile Paralel Programlama. Ömer Halisdemir Üniversitesi Mühendislik Bilimleri Dergisi, 3(2), 1-17.