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: Genetik algoritmalar, Parametre optimizasyonu, Performans, Çizelgeleme, Genetic algorithms, Parameter optimization, Performance, Scheduling
  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ı: Belirtilmemiş.

Ö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

    212364

    Bulanık esnek akış tipi çok prosesli çizelgeleme problemlerinin genetik algoritma ve tavlama benzetimi ile çözümü

    Solving fuzzy flexible flow shop multi processing scheduling problems by genetic algorithm and simulated annealing

    ŞERİFE GÖZEN

    Yüksek Lisans

    Türkçe

    Türkçe

    2007

    Endüstri ve Endüstri MühendisliğiSelçuk Üniversitesi

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

    YRD. DOÇ. DR. ORHAN ENGİN

  3. Tez No

    178264

    Beklemesiz akış tipi çizelgeleme problemlerinin çözümünde yapay sinir ağları yaklaşımı

    An artifical neural networks approach for solving the no-wait flowshop scheduling problems

    CENGİZ GÜNAYDIN

    Yüksek Lisans

    Türkçe

    Türkçe

    2008

    Endüstri ve Endüstri MühendisliğiSelçuk Üniversitesi

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

    YRD. DOÇ. DR. M. ATİLLA ARICIOĞLU

  4. Tez No

    178538

    Bulanık çok işlemcili esnek akış tipi çizelgeleme problemlerinin çözümünde yeni bir yapay bağışıklık algoritması yaklaşımı

    A new approach for solving fuzzy multiprocessor flexible flow shop scheduling problems with artifical immunue system

    MUSTAFA KERİM YILMAZ

    Yüksek Lisans

    Türkçe

    Türkçe

    2008

    Endüstri ve Endüstri MühendisliğiSelçuk Üniversitesi

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

    YRD. DOÇ. DR. ORHAN ENGİN

  5. Tez No

    155842

    Bulanık iş ve teslim zamanlı akış tipi çizelgeleme problemi için çok amaçlı genetik algoritma

    Multiobjective genetic algorithm for flowshop scheduling problem with fuzzy processing time and fuzzy due date

    İZZETTİN TEMİZ

    Doktora

    Türkçe

    Türkçe

    2004

    Endüstri ve Endüstri MühendisliğiGazi Üniversitesi

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

    PROF.DR. SERPİL EROL

Geri Dön