Research Article
BibTex RIS Cite

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

Year 2021, Volume: 32 Issue: 3, 10767 - 10805, 01.05.2021

Önder Halis Bettemir Tuğba Erzurum

https://doi.org/10.18400/tekderg.595238
Cited By: 3

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

References

  • [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] Kolisch, R., ve Padman, R. (2001). "An integrated survey of deterministic project scheduling." Omega, 29(3), 249-272.
  • [3] Li, H., ve Demeulemeester, E. (2016). A genetic algorithm for the robust resource leveling problem. Journal of Scheduling, 19(1), 43-60.
  • [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] 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] 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] 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] Harris, R. B. (1990). Packing method for resource leveling (PACK). Journal of Construction Engineering and Management, 116(2), 331-350.
  • [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] 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] 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] Hegazy, T. (1999). Optimization of resource allocation and leveling using genetic algorithms. Journal of construction engineering and management,125(3), 167-175.
  • [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] 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] Zheng, D. X., Ng, S. T., ve Kumaraswamy, M. M. (2003). "GA-based multiobjective technique for multi-resource leveling." Bridges, 10(40671), 29.
  • [16] El-Rayes, K., ve Jun, D. H. (2009). "Optimizing resource leveling in construction projects." J. Constr. Eng. Manage., 135(11), 1172-1180.
  • [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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] Toğan, V., ve Eirgash, M. A. (2018). Time-Cost Trade-Off Optimization with a New Initial Population Approach. Teknik Dergi, 30(6).
  • [29] Karaa, F. A., ve Nasr, A. Y. (1986). Resource management in construction. Journal of construction engineering and management, 112(3), 346-357.
  • [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] Easa, S. M. (1989). "Resource leveling in construction by optimization." J. Constr. Eng. Manage., 115(2), 302-316.
  • [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] Gather, T., Zimmermann, J., and Bartels, J. H. (2011). "Exact methods for the resource levelling problem." Journal of Scheduling, 14(6), 557-569.
  • [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] 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] 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] 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] 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] El-Rayes, K. ve Kandil, A. (2004). Distributed Computing for the Optimization of Large-Scale Construction Projects.
  • [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] 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] 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] Sayar, A., ve Ergün, U. (2014). Fonksiyonel Programlama Dilleri ile Paralel Programlama. Ömer Halisdemir Üniversitesi Mühendislik Bilimleri Dergisi, 3(2), 1-17.

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

Year 2021, Volume: 32 Issue: 3, 10767 - 10805, 01.05.2021

Önder Halis Bettemir Tuğba Erzurum

https://doi.org/10.18400/tekderg.595238
Cited By: 3

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] 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] Kolisch, R., ve Padman, R. (2001). "An integrated survey of deterministic project scheduling." Omega, 29(3), 249-272.
  • [3] Li, H., ve Demeulemeester, E. (2016). A genetic algorithm for the robust resource leveling problem. Journal of Scheduling, 19(1), 43-60.
  • [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] 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] 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] 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] Harris, R. B. (1990). Packing method for resource leveling (PACK). Journal of Construction Engineering and Management, 116(2), 331-350.
  • [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] 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] 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] Hegazy, T. (1999). Optimization of resource allocation and leveling using genetic algorithms. Journal of construction engineering and management,125(3), 167-175.
  • [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] 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] Zheng, D. X., Ng, S. T., ve Kumaraswamy, M. M. (2003). "GA-based multiobjective technique for multi-resource leveling." Bridges, 10(40671), 29.
  • [16] El-Rayes, K., ve Jun, D. H. (2009). "Optimizing resource leveling in construction projects." J. Constr. Eng. Manage., 135(11), 1172-1180.
  • [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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] Toğan, V., ve Eirgash, M. A. (2018). Time-Cost Trade-Off Optimization with a New Initial Population Approach. Teknik Dergi, 30(6).
  • [29] Karaa, F. A., ve Nasr, A. Y. (1986). Resource management in construction. Journal of construction engineering and management, 112(3), 346-357.
  • [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] Easa, S. M. (1989). "Resource leveling in construction by optimization." J. Constr. Eng. Manage., 115(2), 302-316.
  • [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] Gather, T., Zimmermann, J., and Bartels, J. H. (2011). "Exact methods for the resource levelling problem." Journal of Scheduling, 14(6), 557-569.
  • [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] 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] 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] 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] 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] El-Rayes, K. ve Kandil, A. (2004). Distributed Computing for the Optimization of Large-Scale Construction Projects.
  • [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] 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] 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] Sayar, A., ve Ergün, U. (2014). Fonksiyonel Programlama Dilleri ile Paralel Programlama. Ömer Halisdemir Üniversitesi Mühendislik Bilimleri Dergisi, 3(2), 1-17.
There are 43 citations in total.

Details

Primary Language Turkish
Subjects Engineering
Journal Section Articles
Authors

Önder Halis Bettemir 0000-0002-5692-7708

Tuğba Erzurum

Publication Date May 1, 2021
Submission Date July 22, 2019
Published in Issue Year 2021 Volume: 32 Issue: 3

Cite

APA Bettemir, Ö. H., & Erzurum, T. (2021). Kaynak Dengeleme Probleminin Arama Uzayını Paralel Programlama ile Tarayarak Kesin Çözümü. Teknik Dergi, 32(3), 10767-10805. https://doi.org/10.18400/tekderg.595238
AMA Bettemir ÖH, Erzurum T. Kaynak Dengeleme Probleminin Arama Uzayını Paralel Programlama ile Tarayarak Kesin Çözümü. Teknik Dergi. May 2021;32(3):10767-10805. doi:10.18400/tekderg.595238
Chicago Bettemir, Önder Halis, and Tuğba Erzurum. “Kaynak Dengeleme Probleminin Arama Uzayını Paralel Programlama Ile Tarayarak Kesin Çözümü”. Teknik Dergi 32, no. 3 (May 2021): 10767-805. https://doi.org/10.18400/tekderg.595238.
EndNote Bettemir ÖH, Erzurum T (May 1, 2021) Kaynak Dengeleme Probleminin Arama Uzayını Paralel Programlama ile Tarayarak Kesin Çözümü. Teknik Dergi 32 3 10767–10805.
IEEE Ö. H. Bettemir and T. Erzurum, “Kaynak Dengeleme Probleminin Arama Uzayını Paralel Programlama ile Tarayarak Kesin Çözümü”, Teknik Dergi, vol. 32, no. 3, pp. 10767–10805, 2021, doi: 10.18400/tekderg.595238.
ISNAD Bettemir, Önder Halis - Erzurum, Tuğba. “Kaynak Dengeleme Probleminin Arama Uzayını Paralel Programlama Ile Tarayarak Kesin Çözümü”. Teknik Dergi 32/3 (May 2021), 10767-10805. https://doi.org/10.18400/tekderg.595238.
JAMA Bettemir ÖH, Erzurum T. Kaynak Dengeleme Probleminin Arama Uzayını Paralel Programlama ile Tarayarak Kesin Çözümü. Teknik Dergi. 2021;32:10767–10805.
MLA Bettemir, Önder Halis and Tuğba Erzurum. “Kaynak Dengeleme Probleminin Arama Uzayını Paralel Programlama Ile Tarayarak Kesin Çözümü”. Teknik Dergi, vol. 32, no. 3, 2021, pp. 10767-05, doi:10.18400/tekderg.595238.
Vancouver Bettemir ÖH, Erzurum T. Kaynak Dengeleme Probleminin Arama Uzayını Paralel Programlama ile Tarayarak Kesin Çözümü. Teknik Dergi. 2021;32(3):10767-805.

Cited By

A Memetic Algorithm for the Solution of the Resource Leveling Problem
Buildings
https://doi.org/10.3390/buildings13112738
Scheduling, Management and Optimization of Construction Process
Teknik Dergi
https://doi.org/10.18400/tekderg.981601
Optimum Solution of Resource Leveling Problem by Evaluating the Whole Search Domain
Fırat Üniversitesi Mühendislik Bilimleri Dergisi
https://doi.org/10.35234/fumbd.1105174
 Download Cover Image