Akış tipi çizelgeleme problemlerinin genetik algoritma ile çözüm performansının artırılmasında parametre optimizasyonu
To Increase the performance of flow-shop scheduling problems solving with genetic algorithms: A parameter optimization
Yazar: ORHAN ENGİN
Danışman: DOÇ.DR. ALPASLAN FIĞLALI
İstanbul Teknik Üniversitesi / Fen Bilimleri Enstitüsü / Bilgisayar Mühendisliği Ana Bilim Dalı
Derece: Doktora, 2001
Konu: Endüstri ve Endüstri Mühendisliği = Industrial and Industrial Engineering
Dizin: Genetik algoritmalar = Genetic algorithms ; Parametre optimizasyonu = Parameter optimization ; Performans = Performance ; Çizelgeleme = Scheduling

Özet:
AKIŞ TIPI ÇİZELGELEME PROBLEMLERİNİN GENETİK ALGORİTMA İLE ÇÖZÜM PERFORMANSININ ARTIRILMASINDA PARAMETRE OPTİMİZASYONU ÖZET Tez kapsamında, NP Problemleri grubunda olan akış tipi çizelgeleme problemlerinin Genetik Algoritma(GA) ile çözüm performansının artırılmasına yönelik bir çalışma yapılmıştır. Bu çalışmanın ilk bölümünde, akış tipi çizelgeleme problemlerinin yapısı ve çizelgeleme problemlerinde kullanılan rassal arama metotlarından olan; Tabu araştırmaları, Tavlama Benzetimi, Karınca Kolonileri ve Yapay Bağışıklık sistemlerinden bahsedilmiştir. Akış tipi çizelgeleme problemlerinde kullanılan GA modeli ve parametreleri ile uygulama alanları,ikinci ve üçüncü bölümlerde yer almaktadır. Genetik Algoritmalarda kullanılan parametrelerin optimizasyonu ile ilgili 10 farklı problem için 10250 deneme yapılmıştır. Öncelikli olarak, GA'da kullanılan ve GA'nın performansını etkileyen altı parametre; 2x5(iki iş, beş makine), 2x10, 2x15, 2x20 problemleri üzerinde test edilmiştir. İki makine problemlerinin tercih edilmesinin nedeni, bu problemlerin optimum çözümlerinin Johnson algoritması ile önceden belirlenebilmesidir. İki makine problemlerinde GA ile, Johnson algoritması gibi optimum çözüme ulaşılmıştır. GA, tek optimum iş sırası yerine alternatifli iş sırası oluşturduğundan, Johnson algoritmasından daha iyi performans göstermiştir. Çok makine problemi olarak, 3x10, 4x1 Q, 5x10, 7x15 problemleri rassal olarak üretilmiştir. Toplam 10 problem için, -Başlangıç popülasyonu, -Üreme Yöntemi, -Çaprazlama Yöntemi, -Mutasyon Yöntemi, -Çaprazlama Oranı, -Mutasyon Oranı parametreleri ile ilgili deneyler yapılmıştır. X111Akış tipi çizelgeleme problemlerinde; GA ile optimum veya optimuma yakın çözümlere daha düşük nesil sayılarında ulaşabilmek için, başlangıç popülasyonunun 40; iki makine için, "kısmı yapay seçim" üreme yönteminin, çok makine için, "akış zamanlı rulet çemberi" üreme yönteminin; çaprazlama yöntemi olarak, "sıralı çaprazlamanın"; çaprazlama oranının,%60-%100 ve mutasyon oranının, %40-%70 arasında seçilmesinin uygun olacağı belirlenmiştir. Belirlenen bu oranlara göre iki seviyeli deney tasarımı yapılmıştır. Akış tipi çizelgeleme problemlerinde GA'nın performansını etkileyen en önemli faktörlerin, üreme ile çaprazlama yönteminin olduğu belirlenmiştir. XIV

Abstract:
TO INCREASE THE PERFORMANCE OF FLOW-SHOP SCHEDULING PROBLEMS SOLVING WITH GENETIC ALGORITHMS: A PARAMETERS OPTIMIZATION SUMMARY In the thesis, the problem of scheduling jobs in a flow-shop which is an NP - complete problem is studied to optimize the parameters for improving the genetic algorithm performance. In the first chapter, the structure of flow-shop scheduling problems and some related random search methods such as Tabu Search, Simulated Annealing, Ant Colonies and Artificial Immune Systems are mentioned. Optimisation of the control parameters of genetic algorithms for flow-shop scheduling problems are discussed in the second and third chapters. In the thesis ten different problems were solved with 10250 runs. Firstly 2x5(2- machine, 5-jobs), 2x10, 2x15, 2x20 problems were tested for six parameters which influence the performance of genetic algorithms. Two machine problems were preferred because it is possible to find an optimal schedule with Johnson Algorithm. For two machine problems Johnson Algorithm gives only one optimal schedule but genetic algorithm gives alternative optimal schedules that's why GA is preferrable to Johnson Algorithm. As multiple machine problems 3xl0(3-machine, 10-jobs), 4x10, 5x10, 7x15, flow- shop problems were randomly generated for solving with GA. Six different control parameters of genetic algorithm for flow-shop scheduling problems that are defined in the following were tested for improving the genetic algorithm performance in ten different above-mentioned problems: -Number of initial population, -Reproduction operators, -Crossover operators, -Mutation operators, -Rate of crossover, -Rate of mutation. XVResults indicate that for the flow-shop scheduling problems 40 as initial population, partially artificial reproduction as reproduction operator for two machines and flow time rulet wheel reproduction as reproduction operator for multiple machines; order crossover as crossover operator, 60% - 100% as crossover rate and 40% - 70% as mutation rate give the best result in the genetic algorithms. For fine-tuning of these parameters a two-level experimental design is applied. It is determined that the most important factors affecting the GA performance for flow- shop scheduling problems are reproduction operator and crossover operator. XVI