Araştırma Makalesi
BibTex RIS Kaynak Göster

Tüm Arama Uzayını Tarayarak Küçük Ölçekli Kaynak Kısıtlı Proje Çizelgeleme Problemlerinin Çözümü

Yıl 2021, Cilt: 5 Sayı: 2, 92 - 112, 30.12.2021
https://doi.org/10.29002/asujse.878294

Öz

Kaynak kısıtlı proje çizelgeleme problemi özellikle imalat ve inşaat sektöründe yaygın olarak karşılaşılan bir problemdir. Proje tabanlı faaliyet gösteren inşaat sektöründe kaynak tahsisi her proje için baştan yapıldığı için planlamacılar kaynak kısıtlarının ihlalini düzenlerken en iyi çözümü bulmak için yeterli vakte sahip olmayabilirler. Ayrıca küçük ölçekli inşaat işlerini gerçekleştiren firmalarda optimizasyon alanında uzman inşaat mühendislerinin istihdam edilmesi düşük olasılıktır. Bunun sonucunda kaynak kısıtlarını ihlal etmeyen fakat optimum çözümden uzak bir çözüm elde edebilirler. Bu çalışmada karmaşık optimizasyon yöntemlerini kullanmadan tüm proje çizelgeleme olasılıklarını deneyerek kaynak kısıtlı proje çizelgeleme problemini çözen bir algoritma geliştirilmiştir. Algoritma hesap tablosu üzerinde programlanmış ve küçük ölçekli projelerde denenerek çalıştığı gösterilmiştir. Kaynak kısıtlı proje çizelgeleme problemleri NP-Zor türü problemler olduğu için arama uzayı aktivite sayısının artması ile üstel biçimde arttığı için büyük problemlerde hesaplama süresi çok artmaktadır. Bu nedenle bu çalışmada küçük ölçekli problemler çözülmüştür. Fakat ileri çalışma olarak yöntemin hızlandırılması, uygun olmayan çözümlerin elenmesi ve paralel hesaplama ile daha hızlı çözümün elde edilmesi amaçlanmaktadır. Böylece daha büyük problemlerin çözümü mümkün olacaktır. Gerçekleştirilen 6 vaka analizinin tam sonuçları 1 dakikadan daha kısa sürede elde edilmesi ve yöntemin uygulanabilmesi için karmaşık optimizasyon yöntemlerinin bilinmesine gerek duyulmaması inşaat sektöründe önerilen algoritmanın uygulanabileceği gösterilmiştir.

Destekleyen Kurum

Bulunmamaktadır.

Kaynakça

  • [1] G. Ulusoy, L. Ozdamar, A constrained-based perspective in resource constrained project scheduling. International Journal of Production Research. 32 (1994) 693-705.
  • [2] H. Zhang, H. Li, C.M. Tam, Particle swarm optimization for resource-constrained project scheduling. International Journal of Project Management. 24(1) (2006) 83-92.
  • [3] R. Kanıt, U.N. Baykan, M. Erdal, Kısıtlı Kaynak Koşullarının Yapı Maliyetine Etkisinin İncelenmesi. Politeknik Dergisi. 8(2) (2005) 209-221.
  • [4] F.B. Talbot, An Integer Programming Algorithm for the Resource-Constrained Project Scheduling Problem. Ph.D. Dissertation, Pennsylvania State University, 1976.
  • [5] P. Stinson Joel, A Branch and Bound Algorithm for a General Class of Resource-Constrained Scheduling Problems. Ph.D. Dissertation, University of North Carolina at Chapel Hill, 1976.
  • [6] E.D. Davis, B.M. Khumawala, Multiple Resource-Constrained Scheduling Using Branch and Bound. AIIE Trans. 10(3) (1978) 252-259.
  • [7] R. Kolisch, Serial and parallel resource-constrained project scheduling methods revisited: Theory and computation. European Journal of Operational Research. 90(2) (1996) 320-333.
  • [8] D. Merkle, M. Middendorf, H. Schmeck, Ant colony optimization for resource-constrained project scheduling. IEEE transactions on evolutionary computation. 6(4) (2002) 333-346.
  • [9] S. Hartmann, A competitive genetic algorithm for resource constrained project scheduling. Naval Research Logistics (NRL). 45(7) (1998) 733-750.
  • [10] J.H. Patterson, Project scheduling: The effect of problem structure on heuristic performance. Naval Research Logistics Quarterly. 23 (1976) 95-124.
  • [11] L. Ozdamar, G. Ulusoy, A survey on the resource constrained project scheduling problem. IIE Transactions. 27 (1995) 574-586.
  • [12] N. Christofides, R. Alvarez-Valdes, J.M. Tamarit, Project scheduling with resource constraints: a branch and bound approach. European Journal of Operational Research. 29 (1987) 262-273.
  • [13] R.A.V. Olaguíbel, J.M.T. Goerlich, Heuristic algorithms for resource-constrained project scheduling: A review and an empirical analysis. Advances in project scheduling. (1989) 113-134.
  • [14] L. Özdamar, G. Ulusoy, A survey on the resource-constrained project scheduling problem. IIE transactions. 27(5) (1995) 574-586.
  • [15] V. Van Peteghem, M. Vanhoucke, An experimental investigation of metaheuristics for the multi-mode resource-constrained project scheduling problem on new dataset instances. European Journal of Operational Research. 235(1) (2014) 62-72.
  • [16] L. Bukata, P. Šůcha, Z. Hanzálek, Solving the resource constrained project scheduling problem using the parallel tabu search designed for the CUDA platform. Journal of Parallel and Distributed Computing. 77 (2015) 58-68.
  • [17] F. Glover, Future paths for integer programming and links to artificial intelligence. Comput. Oper. Res. 13(5) (1986) 533-549.
  • [18] T. Bhaskar, M.N. Pal, A.K. Pal, A heuristic method for RCPSP with fuzzy activity times. European Journal of Operational Research. 208(1) (2011) 57-66.
  • [19] U. Beşikci, Ü. Bilge, G. Ulusoy, Multi-mode resource constrained multi-project scheduling and resource portfolio problem. European Journal of Operational Research. 240(1) (2015) 22-31.
  • [20] U. Beşikci, Ü. Bilge, G. Ulusoy, Resource dedication problem in a multi-project environment. Flexible Services and Manufacturing Journal. 25(1) (2013) 206-229.
  • [21] J.A. Arauzo, J.M. Galan, J. Pajares, A. Lopez-Paredes, Efficient project portfolio management. An intelligent decision support system for engineering and consultancy firms. Dyna. 84(9) (2009) 761-772.
  • [22] X. Wang, Q. Chen, N. Mao, X. Chen, Z. Li, Proactive approach for stochastic RCMPSP based on multi-priority rule combinations. International Journal of Production Research. 53(4) (2015) 1098-1110.
  • [23] P. Brucker, S. Knust, A. Schoo, O. Thiele, A branch and bound algorithm for the resource-constrained project scheduling problem. European Journal of Operational Research. 107 (1998) 272-288.
  • [24] L. Zhu, J. Lin, Z.J. Wang, A discrete oppositional multi-verse optimization algorithm for multi-skill resource constrained project scheduling problem. Applied Soft Computing. 85 (2019) 105805.
  • [25] J. Lin, L. Zhu, K. Gao, A genetic programming hyper-heuristic approach for the multi-skill resource constrained project scheduling problem. Expert Systems with Applications. 140 (2020) 112915.
  • [26] R. Pellerin, N. Perrier, F. Berthaut, A survey of hybrid metaheuristics for the resource-constrained project scheduling problem. European Journal of Operational Research. 280(2) (2020) 395-416.
  • [27] A. Birjandi, S.M. Mousavi, Fuzzy resource-constrained project scheduling with multiple routes: A heuristic solution. Automation in Construction. 100 (2019) 84-102.
  • [28] M. Laszczyk, P.B. Myszkowski, Improved selection in evolutionary multi–objective optimization of multi–skill resource–constrained project scheduling problem. Information Sciences. 481 (2019) 412-431.
  • [29] R.K. Chakrabortty, A. Abbasi, M.J. Ryan, Multi-mode resource-constrained project scheduling using modified variable neighborhood search heuristic. International Transactions in Operational Research. 27(1) (2020) 138-167.
  • [30] E.B. Tirkolaee, A. Goli, M. Hematian, A.K. Sangaiah, T. Han, Multi-objective multi-mode resource constrained project scheduling problem using Pareto-based algorithms. Computing. 101(6) (2019) 547-570.
  • [31] S. Creemers, The preemptive stochastic resource-constrained project scheduling problem. European Journal of Operational Research. 277(1) (2019) 238-247.
  • [32] Ö.H. Bettemir, R. Sonmez, Hybrid genetic algorithm with simulated annealing for resource-constrained project scheduling. Journal of Management in Engineering. 31(5) (2015) 04014082.

Solution of Resource Constrained Project Scheduling Problem by Scanning the Whole Search Domain

Yıl 2021, Cilt: 5 Sayı: 2, 92 - 112, 30.12.2021
https://doi.org/10.29002/asujse.878294

Öz

Resource constrained project scheduling problem is a prevalent problem for manufacturing and construction sectors. Resource allocation is redone from the beginning in the construction sector for each construction project; therefore project planners may not have adequate time to obtain optimum solution. Moreover, employment of civil engineers who are talented in the optimization task is less probable in small-scale construction firms. As a result of this, resource overrun problems are solved without converging optimum solution. In this study, a complete enumeration based algorithm which can solve resource constrained project scheduling problems without implementing complex optimization methods is implemented. The algorithm is programmed on spreadsheet and small-scale problems are solved in order to represent the proposed algorithm can obtain the optimum solution. Search domain expands exponentially and solution time excessively prolongs when the number of activities in the project increases because the resource constrained project scheduling problem is NP-Hard. Therefore in this study small-scale problems are solved. However, elimination of infeasible solutions and parallel computing can be inserted as further study to decrease the computing time. Thence solution of larger scale problems would be possible. It is considered that the construction sector may implement the proposed algorithm since the executed six case studies are solved within one minute and the implementation of the proposed method does not require complex optimization algorithms.

Kaynakça

  • [1] G. Ulusoy, L. Ozdamar, A constrained-based perspective in resource constrained project scheduling. International Journal of Production Research. 32 (1994) 693-705.
  • [2] H. Zhang, H. Li, C.M. Tam, Particle swarm optimization for resource-constrained project scheduling. International Journal of Project Management. 24(1) (2006) 83-92.
  • [3] R. Kanıt, U.N. Baykan, M. Erdal, Kısıtlı Kaynak Koşullarının Yapı Maliyetine Etkisinin İncelenmesi. Politeknik Dergisi. 8(2) (2005) 209-221.
  • [4] F.B. Talbot, An Integer Programming Algorithm for the Resource-Constrained Project Scheduling Problem. Ph.D. Dissertation, Pennsylvania State University, 1976.
  • [5] P. Stinson Joel, A Branch and Bound Algorithm for a General Class of Resource-Constrained Scheduling Problems. Ph.D. Dissertation, University of North Carolina at Chapel Hill, 1976.
  • [6] E.D. Davis, B.M. Khumawala, Multiple Resource-Constrained Scheduling Using Branch and Bound. AIIE Trans. 10(3) (1978) 252-259.
  • [7] R. Kolisch, Serial and parallel resource-constrained project scheduling methods revisited: Theory and computation. European Journal of Operational Research. 90(2) (1996) 320-333.
  • [8] D. Merkle, M. Middendorf, H. Schmeck, Ant colony optimization for resource-constrained project scheduling. IEEE transactions on evolutionary computation. 6(4) (2002) 333-346.
  • [9] S. Hartmann, A competitive genetic algorithm for resource constrained project scheduling. Naval Research Logistics (NRL). 45(7) (1998) 733-750.
  • [10] J.H. Patterson, Project scheduling: The effect of problem structure on heuristic performance. Naval Research Logistics Quarterly. 23 (1976) 95-124.
  • [11] L. Ozdamar, G. Ulusoy, A survey on the resource constrained project scheduling problem. IIE Transactions. 27 (1995) 574-586.
  • [12] N. Christofides, R. Alvarez-Valdes, J.M. Tamarit, Project scheduling with resource constraints: a branch and bound approach. European Journal of Operational Research. 29 (1987) 262-273.
  • [13] R.A.V. Olaguíbel, J.M.T. Goerlich, Heuristic algorithms for resource-constrained project scheduling: A review and an empirical analysis. Advances in project scheduling. (1989) 113-134.
  • [14] L. Özdamar, G. Ulusoy, A survey on the resource-constrained project scheduling problem. IIE transactions. 27(5) (1995) 574-586.
  • [15] V. Van Peteghem, M. Vanhoucke, An experimental investigation of metaheuristics for the multi-mode resource-constrained project scheduling problem on new dataset instances. European Journal of Operational Research. 235(1) (2014) 62-72.
  • [16] L. Bukata, P. Šůcha, Z. Hanzálek, Solving the resource constrained project scheduling problem using the parallel tabu search designed for the CUDA platform. Journal of Parallel and Distributed Computing. 77 (2015) 58-68.
  • [17] F. Glover, Future paths for integer programming and links to artificial intelligence. Comput. Oper. Res. 13(5) (1986) 533-549.
  • [18] T. Bhaskar, M.N. Pal, A.K. Pal, A heuristic method for RCPSP with fuzzy activity times. European Journal of Operational Research. 208(1) (2011) 57-66.
  • [19] U. Beşikci, Ü. Bilge, G. Ulusoy, Multi-mode resource constrained multi-project scheduling and resource portfolio problem. European Journal of Operational Research. 240(1) (2015) 22-31.
  • [20] U. Beşikci, Ü. Bilge, G. Ulusoy, Resource dedication problem in a multi-project environment. Flexible Services and Manufacturing Journal. 25(1) (2013) 206-229.
  • [21] J.A. Arauzo, J.M. Galan, J. Pajares, A. Lopez-Paredes, Efficient project portfolio management. An intelligent decision support system for engineering and consultancy firms. Dyna. 84(9) (2009) 761-772.
  • [22] X. Wang, Q. Chen, N. Mao, X. Chen, Z. Li, Proactive approach for stochastic RCMPSP based on multi-priority rule combinations. International Journal of Production Research. 53(4) (2015) 1098-1110.
  • [23] P. Brucker, S. Knust, A. Schoo, O. Thiele, A branch and bound algorithm for the resource-constrained project scheduling problem. European Journal of Operational Research. 107 (1998) 272-288.
  • [24] L. Zhu, J. Lin, Z.J. Wang, A discrete oppositional multi-verse optimization algorithm for multi-skill resource constrained project scheduling problem. Applied Soft Computing. 85 (2019) 105805.
  • [25] J. Lin, L. Zhu, K. Gao, A genetic programming hyper-heuristic approach for the multi-skill resource constrained project scheduling problem. Expert Systems with Applications. 140 (2020) 112915.
  • [26] R. Pellerin, N. Perrier, F. Berthaut, A survey of hybrid metaheuristics for the resource-constrained project scheduling problem. European Journal of Operational Research. 280(2) (2020) 395-416.
  • [27] A. Birjandi, S.M. Mousavi, Fuzzy resource-constrained project scheduling with multiple routes: A heuristic solution. Automation in Construction. 100 (2019) 84-102.
  • [28] M. Laszczyk, P.B. Myszkowski, Improved selection in evolutionary multi–objective optimization of multi–skill resource–constrained project scheduling problem. Information Sciences. 481 (2019) 412-431.
  • [29] R.K. Chakrabortty, A. Abbasi, M.J. Ryan, Multi-mode resource-constrained project scheduling using modified variable neighborhood search heuristic. International Transactions in Operational Research. 27(1) (2020) 138-167.
  • [30] E.B. Tirkolaee, A. Goli, M. Hematian, A.K. Sangaiah, T. Han, Multi-objective multi-mode resource constrained project scheduling problem using Pareto-based algorithms. Computing. 101(6) (2019) 547-570.
  • [31] S. Creemers, The preemptive stochastic resource-constrained project scheduling problem. European Journal of Operational Research. 277(1) (2019) 238-247.
  • [32] Ö.H. Bettemir, R. Sonmez, Hybrid genetic algorithm with simulated annealing for resource-constrained project scheduling. Journal of Management in Engineering. 31(5) (2015) 04014082.
Toplam 32 adet kaynakça vardır.

Ayrıntılar

Birincil Dil Türkçe
Konular Mühendislik
Bölüm Araştırma Makalesi
Yazarlar

Önder Halis Bettemir 0000-0002-5692-7708

Derya Çakmak 0000-0003-1271-5292

Yayımlanma Tarihi 30 Aralık 2021
Gönderilme Tarihi 11 Şubat 2021
Kabul Tarihi 28 Ekim 2021
Yayımlandığı Sayı Yıl 2021Cilt: 5 Sayı: 2

Kaynak Göster

APA Bettemir, Ö. H., & Çakmak, D. (2021). Tüm Arama Uzayını Tarayarak Küçük Ölçekli Kaynak Kısıtlı Proje Çizelgeleme Problemlerinin Çözümü. Aksaray University Journal of Science and Engineering, 5(2), 92-112. https://doi.org/10.29002/asujse.878294
Aksaray J. Sci. Eng. | e-ISSN: 2587-1277 | Period: Biannually | Founded: 2017 | Publisher: Aksaray University | https://asujse.aksaray.edu.tr