Research Article
BibTex RIS Cite

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

Year 2021, , 92 - 112, 30.12.2021

Önder Halis Bettemir , Derya Çakmak

https://doi.org/10.29002/asujse.878294

Abstract

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.

Keywords

Optimizasyon Kaynak kısıtlı proje çizelgeleme problemi proje yönetimi

Supporting Institution

Bulunmamaktadır.

References

  • [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

Year 2021, , 92 - 112, 30.12.2021

Önder Halis Bettemir , Derya Çakmak

https://doi.org/10.29002/asujse.878294

Abstract

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.

Keywords

Optimization resource-constrained project scheduling problem project management

References

  • [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.
There are 32 citations in total.

Details

Primary Language Turkish
Subjects Engineering
Journal Section Research Article
Authors

Önder Halis Bettemir 0000-0002-5692-7708

Derya Çakmak 0000-0003-1271-5292

Publication Date December 30, 2021
Submission Date February 11, 2021
Acceptance Date October 28, 2021
Published in Issue Year 2021

Cite

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