Araştırma Makalesi
PDF Zotero Mendeley EndNote BibTex Kaynak Göster

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.

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.

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.

Ayrıntılar

Birincil Dil Türkçe
Konular Mühendislik
Bölüm Research Article
Yazarlar

Önder Halis BETTEMİR (Sorumlu Yazar)
INONU UNIVERSITY
0000-0002-5692-7708
Türkiye


Derya ÇAKMAK
İNÖNÜ ÜNİVERSİTESİ
0000-0003-1271-5292
Türkiye

Destekleyen Kurum Bulunmamaktadır.
Yayımlanma Tarihi 30 Aralık 2021
Başvuru Tarihi 11 Şubat 2021
Kabul Tarihi 28 Ekim 2021
Yayınlandığı Sayı Yıl 2021, Cilt 5, Sayı 2

Kaynak Göster

Bibtex @araştırma makalesi { asujse878294, journal = {Aksaray University Journal of Science and Engineering}, issn = {}, eissn = {2587-1277}, address = {Aksaray Üniversitesi, Fen Bilimleri Enstitüsü, Merkez Kampüs, 68100 Aksaray}, publisher = {Aksaray Üniversitesi}, year = {2021}, volume = {5}, pages = {92 - 112}, doi = {10.29002/asujse.878294}, title = {Tüm Arama Uzayını Tarayarak Küçük Ölçekli Kaynak Kısıtlı Proje Çizelgeleme Problemlerinin Çözümü}, key = {cite}, author = {Bettemir, Önder Halis and Çakmak, Derya} }
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 . DOI: 10.29002/asujse.878294
MLA Bettemir, Ö. H. , Çakmak, D. "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 (2021 ): 92-112 <http://asujse.aksaray.edu.tr/tr/pub/issue/63258/878294>
Chicago Bettemir, Ö. H. , Çakmak, D. "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 (2021 ): 92-112
RIS TY - JOUR T1 - Tüm Arama Uzayını Tarayarak Küçük Ölçekli Kaynak Kısıtlı Proje Çizelgeleme Problemlerinin Çözümü AU - Önder Halis Bettemir , Derya Çakmak Y1 - 2021 PY - 2021 N1 - doi: 10.29002/asujse.878294 DO - 10.29002/asujse.878294 T2 - Aksaray University Journal of Science and Engineering JF - Journal JO - JOR SP - 92 EP - 112 VL - 5 IS - 2 SN - -2587-1277 M3 - doi: 10.29002/asujse.878294 UR - https://doi.org/10.29002/asujse.878294 Y2 - 2021 ER -
EndNote %0 Aksaray University Journal of Science and Engineering Tüm Arama Uzayını Tarayarak Küçük Ölçekli Kaynak Kısıtlı Proje Çizelgeleme Problemlerinin Çözümü %A Önder Halis Bettemir , Derya Çakmak %T Tüm Arama Uzayını Tarayarak Küçük Ölçekli Kaynak Kısıtlı Proje Çizelgeleme Problemlerinin Çözümü %D 2021 %J Aksaray University Journal of Science and Engineering %P -2587-1277 %V 5 %N 2 %R doi: 10.29002/asujse.878294 %U 10.29002/asujse.878294
ISNAD Bettemir, Önder Halis , Çakmak, Derya . "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 (Aralık 2021): 92-112 . https://doi.org/10.29002/asujse.878294
AMA Bettemir Ö. H. , Çakmak D. Tüm Arama Uzayını Tarayarak Küçük Ölçekli Kaynak Kısıtlı Proje Çizelgeleme Problemlerinin Çözümü. Aksaray J. Sci. Eng.. 2021; 5(2): 92-112.
Vancouver Bettemir Ö. H. , Çakmak D. 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. 2021; 5(2): 92-112.
IEEE Ö. H. Bettemir ve D. Çakmak , "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, c. 5, sayı. 2, ss. 92-112, Ara. 2021, doi:10.29002/asujse.878294

Aksaray J. Sci. Eng. | e-ISSN: 2587-1277 | Period: Biannually | Founded: 2017 | Publisher: Aksaray University | https://asujse.aksaray.edu.tr


ASUJSE is indexing&Archiving in

crossref-logo-landscape-100.pngscilitLogo.png    scholar_logo_30dp.png   logo_wcmasthead_en.png   logo-large-explore.png    oaliblogo2.jpg   GettyImages_90309427_montage_255x130px.png search-result-logo-horizontal-TEST.jpgIndex Copernicus

Dimensions



Creative Commons License