Genetik algoritma ile proje çizelgeleme
A genetic algorithm for project scheduling
Yazar: SEMİN PAKSOY
Danışman: YRD. DOÇ. DR. ARZU UZUN
Çukurova Üniversitesi / Sosyal Bilimler Enstitüsü / İşletme Ana Bilim Dalı / Sayısal Yöntemler Bilim Dalı
Derece: Doktora, 2007
Konu: Genetik = Genetics ; İşletme = Business Administration
Dizin: Kaynak kısıtlı çizelgeleme = Resource constrained scheduling ; Proje çizelgeleme = Project scheduling

Özet:
Bu çalışmada Delphi 6 kullanılarak, kaynak kısıtlı proje çizelgelemeye yönelik olarak genetik algoritma hazırlanmıştır. Kaynak kısıtlı proje çizelgeleme problemleri, karmaşık yapısı gereği çözümü zor ( NP-hard ) problemler arasında yer almaktadır. Çözümü zor olan bu tür problemlerde, kesin çözüm veren bir algoritmanın hazırlanması oldukça zordur.Geliştirilen sezgisel algoritma ile parametrik olarak verilebilen toplum sayıları ve iterasyonlar sonucunda, minimum proje süresine sahip çizelge tespit edilebilmektedir. Algoritmada rastgele ve öncelik kuralına dayanan kromozom temsillerinden ikisi de kullanılmıştır. Proje çizelgeleme aşamasında, faaliyetler rastgele seçilen öncelik kuralına göre çizelgelenmektedir.Çizelgeleme problemlerinde, öncül/ardıl olarak farklı iki şekilde verilen faaliyet öncelikleri göz önünde bulundurularak, algoritmanın her iki problem tipi için çalışması sağlanmaktadır. Böylece, problem ne şekilde verilirse verilsin, kullanıcı tarafından hangi bir dönüşüm işlemi yapılmaksızın, algoritmada test edilebilecektir.Algoritma; literatürde bulunan dört veri kümesi üzerinde, toplam 2040 çizelgeleme problemleri ile test edilmiştir. 2040 problemin her biri, farklı iterasyonlarda olmak üzere ikişer kez test edilerek, iterasyon sayısının etkisi araştırılmaya çalışılmıştır.Algortimanın performansını ölçmek ve değerlendirmek amacıyla; her bir veri kümesinin ortalama standart sapması hesaplanarak, literatürde yayınlanmış olan diğer çalışmalarla karşılaştırılmaktadır.Test edilen problemler neticesinde; elde edilen proje bitirme sürelerinin tatmin edilebilir düzeyde olduğu gözlenmiştir. Geliştirilen algoritma, basit problemlerde evrensel(global) sonuçlar verirken, karmaşık problemlerde genellikle yerel sonuçlar üretebilmektedir.

Abstract:
This study presents a genetic algorithm for the resource constrained project scheduling problem using Delphi 6. Resource constrained project scheduling is one of the NP-hard classes because of the complexity of their combinatorial nature. Any exact algorithm are difficult to handle such a problem.The heuristic algorithm generates parameterized active schedules and selects the best one which has minimum project completion time among the generated schedules. The chromosome representation of the problem is based on the both random key and priority rule represantation. The schedule is constructed using randomly selected heuristic priority rule.Priorities of activities of scheduling problems are given by two types such as proccessors/successors of any activities. The algorithm works for two types of scheduling problems. So there is no need any conversion process for successors to proccessors ( or vice versa ) by human being.The algorithm was tested on the four sets of standard problems from the literature. Each set has many project scheduling problems. Total number of scheduling problems is 2040. Each of these scheduling problems are tested twice to observe the effects of different iteration number.To measure and evaluate the performance of the algorthm; the average deviation of each problem set is calculated to compare the algorithm with other approaches in the literature. The computational results are reported.Computational results relatively validate the effectiveness of the generated algortihm. Generally, the algorithm gives global results for simple problems and gives local results for complex problems.