Geri Dön

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

PDF İndir

  1. Tez No: 112205
  2. Yazar: ORHAN ENGİN
  3. Danışmanlar: DOÇ.DR. ALPASLAN FIĞLALI
  4. Tez Türü: Doktora
  5. Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 2001
  8. Dil: Türkçe
  9. Üniversite: İstanbul Teknik Üniversitesi
  10. Enstitü: Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
  12. Bilim Dalı: Belirtilmemiş.
  13. Sayfa Sayısı: 233

Ö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

Özet (Çeviri)

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

Benzer Tezler

  1. Tez No

    127093

    Akış tipi çizelgeleme problemlerinin genetik algoritma (GA) ile çözüm performansının artırılmasında deney tasarımı uygulaması

    Experimental design in improving solution performance by using genetic algorithm (GA) of the problem of scheduling jobs in a flow-shop

    HAKAN EREN

    Yüksek Lisans

    Türkçe

    Türkçe

    2002

    Endüstri ve Endüstri Mühendisliğiİstanbul Teknik Üniversitesi

    Endüstri Mühendisliği Ana Bilim Dalı

    DOÇ. DR. ALPASLAN FIĞLALI

  2. Tez No

    670439

    Bütünleşik üretim ve dağıtım çizelgeleme problemleri için çözüm yaklaşımları

    Solution approaches for integrated production and distribution scheduling problems

    ECE ÇETİN YAĞMUR

    Doktora

    Türkçe

    Türkçe

    2021

    Endüstri ve Endüstri MühendisliğiKonya Teknik Üniversitesi

    Endüstri Mühendisliği Ana Bilim Dalı

    PROF. SAADETTİN ERHAN KESEN

  3. Tez No

    397804

    Melez akış tipi çizelgeleme problemi için tepkisel bir algoritma

    A reactive algorithm for the hybrid flow shop scheduling problem

    ABDULLAH AKTEL

    Doktora

    Türkçe

    Türkçe

    2015

    Endüstri ve Endüstri Mühendisliğiİstanbul Teknik Üniversitesi

    Endüstri Mühendisliği Ana Bilim Dalı

    PROF. DR. MEHMET MUTLU YENİSEY

  4. Tez No

    626036

    Akış tipi çizelgeleme problemlerinin hibrit genetik algoritma ile çözümü ve karar ağacı ile incelenmesi

    Solution of flow shop scheduling problems with hybrid genetic algorithm and analysis with decision tree

    ÖMER KAYA

    Yüksek Lisans

    Türkçe

    Türkçe

    2020

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolHarran Üniversitesi

    Elektrik-Elektronik Mühendisliği Ana Bilim Dalı

    DOÇ. DR. İBRAHİM BERKAN AYDİLEK

  5. Tez No

    198952

    Sıralı akış tipi çizelgeleme problemlerinde genetik algoritma uygulaması

    A genetic algorithm application on ordered flow-shop problems

    MEHMET TUFAN KÖREZ

    Yüksek Lisans

    Türkçe

    Türkçe

    2005

    Endüstri ve Endüstri MühendisliğiYıldız Teknik Üniversitesi

    Endüstri Mühendisliği Ana Bilim Dalı

    Y.DOÇ.DR. SEMİH ÖNÜT

Geri Dön