Genetik Algoritma ile Kaynak Kısıtlı Proje Çizelgeleme

Yıl 2008, Cilt: 17 Sayı: 2, 345 - 362, 01.06.2008

Öğr. Gör. Dr. Semin Paksoy Yrd. Doç. Dr. Arzu Uzun

Öz

In this paper we consider genetic algorithm approach for the resource constrained project scheduling problems Starting with the summarizing the basic components of genetic algorithm approaches we describe the generating project schemes and its necessities Subsequently we present the results of our computational study which is depend on the standart set of test instances These instances have only four reources and thirty activities The results are obtained from a computer program that is developed by Delphi 6 0 Moreover the behaviour of the developed genetic algorithm is analyzed with respect to its main components such as iteration number crossover rate and priority rules Finally the influence of the problem characteristics like that simplicity complexity and size is examined on the performance of the genetic algorithm At the end of the study the results show that the solutions produced from the developed genetic algorithm is generally near the optimum solution Keywords: Genetic algorithm Project scheduling Schedule generation schemes Priority rules

Anahtar Kelimeler

-

Genetik Algoritma ile Kaynak Kısıtlı Proje Çizelgeleme

Öz

Bu çalışmada kaynak kısıtlı proje çizelgeleme problemlerinin genetik algoritma yaklaşımı ile çözümü ele alınmıştır Başlangıçta genetik algoritmanın temel kavramlarına yer verilerek proje çizelgeleme şemaları ve çizelgelemede göz önünde bulundurulması gereken unsurlar özetlenmiştir Daha sonra Delphi 6 0 da geliştirilen genetik algoritmanın otuz faaliyetli ve dört kaynak kullanan standart test problemlerindeki sonuçlarına yer verilmiştir Geliştirilen algoritmanın iterasyon sayısı çaprazlama oranı ve öncelik kuralları açısından davranışları test edilmeye çalışılmıştır Son olarak çizelgeleme problemlerinin faaliyet sayıları basit ya da karmaşık olma özelliklerinin algoritma üzerinde etkileri araştırılmaya çalışılmıştır Çalışma sonucunda geliştirilen genetik algoritma ile elde edilen çözümlerin genel olarak optimuma yakın çözümler olduğu görülmektedir Anahtar Kelimeler: Genetik algoritma Proje çizelgeleme Çizelge oluşturma şemaları Öncelik kuralları

Anahtar Kelimeler

Genetik algoritma, Proje çizelgeleme, Çizelge oluşturma şemaları, Öncelik kuralları

Kaynakça

• Artigues, Christian, Philippe Michelon ve Stephane Reusser (2003), ”Insertion techniques for static and dynamic resource-constrained project scheduling”, European Journal of Operational Research, Volume 149, No. 2, 1 September, ss.249-267.
• Boctor, Fayez F.(1996), ”A new and efficient heuristic for scheduling projects with resource restrictions and multiple execution modes”, European Journal of Operational Research, Volume 90, No. 2, 19 April, ss.349-361.
• Bolat, Berna, K.Erol Osman ve Erdem C.İmsak (2004), “Mühendislik uygulamalarında genetik algoritma ve operatörlerin işlevleri”, Sigma 2004/4, Mühendislik ve Fen Bilimleri Dergisi, ss.264-271.
• Brochmann, Harold (2005), ” A genetıc algorithm”, http://www.salts Brucker Brucker pring.com/brochmann/math/GA/GA- 1.00.html [3.5.2005].
• Brucker, Peter, Andreas Drexl, Rolf Möhring, Klaus Neumann ve Erwin Pesch (1999), “Resource-constrained project scheduling: Notation, classification, models, and methods”, European Journal of Operational Research, Volume 112, No. 1, 1 January 1999, ss.3-41.
• Buckles, Bill P. ve Frederick E. Petry (Derl.) (1992), Genetic Algorithms, Washington: IEEE Computer Society Press, Technology Series.
• Chan, Felix T.S., S.H Chung ve Subhash Wadhwa (2005), “A hybrid genetic algorithm for production and distribution”, The International Journal of Management Sciense, Omega 33, ss.345-555.
• Cheng, Runwei. ve Mitsuo Gen (1994); “Evolution program for resource constrained project scheduling problem”,Evolutionary Computation, IEEE World Congress on Computational Intelligence, Proceedings of the First IEEE Conference ,27-29 June 1994, Vol.2, ss.736 – 741.
• Debels, Dieter ve Mario Vanhoucke (2005), ”A bi-population based genetic algorithm for the resource constrained project scheduling problem”, Vierick Leuven Gent Working Paper, (Seri No: 8).
• Goldberg, David E. (1992), ”Sizing populations for seral and paralel genetic algorithms”, Derl.: Bill P.Buckles and Frederick E. Petry, Washington: IEEE Computer Society Press, Technology Series, ss.20-29.
• Hartmann, Sönke ve Rainer Kolisch (2000),“Experimental evaluation of state-of-art heuristics for the resource constrained project scheduling problem”, European Journal of Operational Research,127, ss.394-407.
• Hindi, S.Khalil, Hongbo Yang ve Krzysztof Fleszar (2002), ” An evolutionary algorithm for resource constrained project scheduling”,IEEE Transactions on Evolutionary Computation,Vol.6, No.5, October.
• Kolisch, Rainer, Arno Sprecher ve Andreas Drexl (1995), “Characterization and generation of a general class of resource constrained project scheduling problems”, Management Science, Volume 41, No. 10, October, ss.1693- 1703.
• Kolisch, Rainer (1996), “Serial and parallel resource-constrained project scheduling methods revisited: Theory and computation”, European Journal of Operational Research, Volume 90, No. 2, 19 April, ss.320-333.
• Kolisch, Rainer ve Arno Sprecher (1997), ”PSPLIB - A project scheduling problem library : OR software - ORSEP operations research software exchange program”, European Journal of Operational Research, Volume 96, No. 1, 10 January, ss.205-216.
• Kolisch, Rainer ve Sönke Hartmann (1999), ”Heuristics algorithms for solving the resource-constrained project scheduling problem: classification and computational analysis”, Kluwer Academic Publishers In: Weglarz. J.(ed.).Project Scheduling-Recent Models, Algorithms and Applications, ss.147-178, Boston.
• Koza, John R. (1995), ”Two ways of discovering the size and shape of a computer program to solve a problem”, Proceedings of the Sixth International Conference on Genetic Algorithm, ss.287-294.
• Kurt, Mustafa ve Cumali Semetay (2001), “Genetik algoritma ve uygulama alanları”, http://www.mmo.org.tr/muhendismakina/arsiv/2001/ekim/Genetik_Algoritm a.htm, [12.4.2005].
• Mitchell, Melanie ve Charles E. Taylor (1999), “Evolutionary computations: an overview”, Annual Review of Ecology ad Systematics, 30: ss.593-616.
• Mitchell, Melanie (1999), An Introduction to Genetic Algorithms, USA: Massachusetts Institute of Technology.
• Mori, Masao ve Ching Chih Tseng (1997), ”A genetic algorithm for multi-mode resource constrained project scheduling problem”, European Journal of Operational Research, Volume 100, No. 1, 1 July, ss.134-141.
• Nakamura, Morikazu., N.Yamashiro, Y.Gong, T.Matsumura ve K.Onaga (2005), “Iterative parallel genetic algorithms based on biased inital population”, IEICE Trans. Fundamentals, (April),Vol.E88-A, No.4, ss.923-929.
• Özdamar, Linet (1999), ”A genetic algorithm approach to a general category project scheduling problem”, Systems, Man and Cybernetics, Part C, IEEE Transactions, Vol. 29, No 1, February, ss.44 – 59.
• Simpson, Wendell P.III, ve James H. Patterson (1996), ”A multiple-tree search procedure for the resource-constrained project scheduling problem”, European Journal of Operational Research, Volume 89, No. 3, 22 March, ss.525-542.
• Tormos, P. ve Antonio Lova (2003), ”An efficient multi-pass heuristic for project scheduling with constrainet resources”, International Journal of Production Research, Vol.41, No.5, ss.1071-1086.
• Ulusoy, Gündüz (2006), ”Proje planlamada kaynak kısıtlı çizelgeleme”, Sabancı Üniversitesi, Mühendislik ve Doğa Bilimleri Fakültesi, http://people.sabanciuniv.edu/gunduz/HalimDogrusoz .pdf , [8.7.2006].
• Wall, Mathew Bartschi (1996), ”A genetic algorithm for resource constrained scheduling”, Doktora Tezi, Massachusetts Institute of Technology, Cambridge.
• Wang, Peng-Yi ve Ming Lu (2002), “Genetic algorithm optimized resource activity critical path method”, Proceedings of the First Conference on Machine Learning and Cybernetics, Vol.. 4, 4-5 November, ss.1978-1982.
• Yeo, M. F. ve E. O. Agyei (1998), ”Optimising engineering problems using genetic algorithms”, Engineering Computations, Vol.15, No.2, ss.268-280.