Geri Dön

Atölye tipi çizelgeleme problemlerine parçacık sürü optimizasyonu yaklaşımı ve genetik algoritma modeli ile karşılaştırılması

A particle swarm optimization approach for the job shop scheduling problems and comparing with the genetic algorithm model

  1. Tez No: 166630
  2. Yazar: MEHMET ŞEVKLİ
  3. Danışmanlar: Y.DOÇ.DR. MEHMET MUTLU YENİSEY
  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: 2005
  8. Dil: Türkçe
  9. Üniversite: İstanbul Teknik Üniversitesi
  10. Enstitü: Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
  12. Bilim Dalı: Belirtilmemiş.
  13. Sayfa Sayısı: 94

Özet

ATÖLYE TİPİ ÇIZELGELEME PROBLEMLERİNE PARÇACIK SÜRÜ OPTİMİZASYONU YAKLAŞIMI VE GENETİK ALGORİTMA MODELİ İLE KARŞILAŞTIRILMASI ÖZET Bu tezde, zor çizelgeleme problemleri arasında yer alan atölye tipi çizelgeleme problemlerinin çözümünde alternatif yeni bir yaklaşım ele alınmıştır. Çözüm yöntemi olarak, son yıllarda hızla gelişen popülasyon temelli yeni sezgisel yöntemlerden biri olan Parçacık Sürü Optimizasyonu (PSO) kullanılmıştır. Popülasyon temelli bir sezgisel yaklaşım olan PSO yöntemi, kuş ve balık sürülerinin sosyal davranışlarından esinlenerek geliştirilmiş ve optimizasyon problemlerinin çözümüne uyarlanmıştır. PSO'da aday çözüm, parçacık olarak nitelendirilir ve sürü içerisindeki kuş olarak düşünülebilir. Kuşlardan meydana gelen sürü (popülasyon) ise çözüm uzayım keşfetmek için beraberce haraket eder. Her bir parçacığın bir amaç fonksiyon değeri vardır ve hız vektörü yardımıyla en iyi çözümü bulmaya çalışır. Parçacıklar (sürü) ise problem uzayında birbirleriyle haberleşerek dolaşırlar. PSO'da her bir parçacığın başlangıç değerleri rastgele oluşturulduktan sonra herbir iterasyonda bu güncelleştirilir. PSO bir evrimsel algoritma olarak kabul edilebilir. Ayrıca arama işlemi, parçacığın kendi tecrübesi ve sürünün en iyisi göz önüne alınarak yapıldığı için sezgisel bir yöntem olarak sınıflandırılır. Atölye tipi çizelgeleme problemi şu şekilde tanımlanabilir, n adet iş m adet tezgahta işlenecektir. İşler tezgahta başladığında iptal etmeden bitirilecektir. Her bir işin önceden biline bir rotası ve herbir tezgahtaki işlem süreleri bilinmektedir. Bir tezgah aynı anda sadece bir işi işleyebilir. Aynı şekilde bir iş bir tezgaha sadece bir kez işlenir. Bütün işlerin operasyonları işleme hazırdır ve bu operasyonların hazırlık ve tezgahların tamir zamanlan işlem sürelerine dahil edilmiştir. Atölye tipi çizelgeleme problemi bütün işlerin operasyonlarım bitirecek minimum zamanı bulmaktır. Bu tezde, ilk olarak atölye tipi çizelgeleme problemleri için PSO ve Genetik Algoritma (GA) modeli tasarlanmış ve“tamamlanma zamanı (makespan)”başarım ölçütüne göre literatürde yer alan test problemleri üzerindeki performansları incelenmiştir. Daha sonra PSO ve GA modellerinin sonuçlan % 5,»% 1 ve %o 5 anlamlılık düzeylerinde istatistiksel olarak karşılaştırılıp incelenmiştir. Sonuçta, PSO modeli ile GA modelinin birbirine yalan performans gösterdiği, bazı zor problemlerde ise PSO modelinin GA modeline göre daha iyi sonuç verdiği görülmüştür. Bunlara ek olarak, basit ve etkili bir yerel arama yöntemi olan“Değişken Komşuluk Arama (VNS)”kullanılarak, yerel aramalı PSO ve GA modelleri geliştirilmiş ve XVIliteratürdeki bazı zor test problemlerine uygulanmıştır. Daha sonra bu iki model istatistiksel olarak karşılaştırılıp incelenmiştir. Sonuçta, yerel aramalı PSO modelinin, yerel aramalı GA modeline göre % 5 anlamlılık düzeyinde daha iyi olduğu görülmüştür. Ayrıca, yerel aramalı PSO modelinin sonuçlan, literatürde ün yapmış diğer sezgisel yöntemlerin sonuçlarıyla karşılaştırılmış, daha iyi veya eşdeğer seviyede olduğu görülmüştür. XVİİ

Özet (Çeviri)

A PARTICLE SWARM OPTIMIZATION APPROACH FOR THE JOB SHOP SCHEDULING PROBLEMS AND COMPARING WITH THE GENETIC ALGORITHM MODEL SUMMARY In this dissertation, a new meta-heuristic technique called Particle Swarm Optimization (PSO) is applied to Job Shop Scheduling (JSS) problem, which is one of the hardest combinatorial optimization problems. Particle Swarm Optimization (PSO) is one of the population based optimization technique inspired by social behavior of bird flocking and fish schooling. PSO inventers were inspired of such natural process based scenarios to solve the optimization problems. In PSO, each single solution, called a particle,' is considered as a bird, the group becomes a swarm (population) and the search space is the area to explore. Each particle has a fitness value calculated by a fitness function, and a velocity of flying towards the optimum. All particles fly across the problem space following the particle nearest to the optimum. PSO starts with initial population of solutions, which is updated iteration-by-iteration. Therefore, PSO can be counted as an evolutionary algorithm besides being a metaheuristics method, which allows exploiting the searching experience of a single particle as well as the best of the whole swarm. The JSS problem can be stated as follows: There is a set of n jobs to be processed by m machines without preemption. Each job has a sequence of operations with a predetermined processing order through machines. Each machine can handle no more than one operation at a time and each job must visit each machine only once. The release time of all operations is zero. Set-up and failure times of each machine are included in the processing times. Then, the JSS problem is to find a schedule of minimal time to complete all jobs. First of all, a PSO and a Genetic Algorithm(GA) model for the JSS problem are developed and applied to the well-known benchmark suites in the literature with the makespan criterion. Then, PSO and GA model results are compared statistically at 5 %, 1 % and 5 %o significant levels. It is concluded that, PSO results are competitive and sometimes better than GA results over the 122 benchmark problems. In addition, a simple but efficient local search method called Variable Neighborhood Search (VNS) is embedded to the PSO and GA models and applied to several hardest benchmark suites. Afterwards, PSO and GA model with VNS results are compared xvmstatistically and it is concluded that, PSO model with VNS results are better than GA model with VNS at 5 % significant level. The results for the PSO algorithm with VNS are also presented and compared with many efficient meta-heurislic algorithms in literature. As a final result, PSO with VNS results are generally found to be better than other results xix

Benzer Tezler

  1. Tez No

    372719

    Çok amaçlı esnek atölye tipi çizelgeleme problemlerinin geliştirilmiş parçacık sürü optimizasyonu ile çözümüne yönelik model önerileri

    Model proposals for the solution of scheduling problems of multi objective flexible job shop with improved particle swarm optimization

    SERKAN KAYA

    Doktora

    Türkçe

    Türkçe

    2014

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

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

    PROF. DR. NİLGÜN FIĞLALI

  2. Tez No

    382642

    A Heuristic Approach on Flexible Job-Shop Scheduling Problem with Maintenance Activities by Considering Weight of the Jobs

    İşlerin Ağırlıkları Gözetilerek Uygulanan Bakım Aktiviteleri ile Esnek Atölye Tipi Çizelgeleme Problemi Üzerine Sezgisel Bir Yaklaşım

    MEHMET DİREKLİ

    Yüksek Lisans

    İngilizce

    İngilizce

    2015

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

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

    YRD. DOÇ. DR. VAHİT KAPLANOĞLU

  3. Tez No

    633585

    Çizelgeleme problemlerinde endüstri 4.0 uygulaması

    Industry 4.0 application in scheduling problems

    MEHMET EMİN AYDOĞDU

    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ı

    DR. ÖĞR. ÜYESİ NURETTİN BEŞLİ

  4. Tez No

    786076

    A hybrid evolutionary algorithm for multi-objective flexible job shop problems

    Çok amaçlı esnek atölye tipi çizelgeleme problemlerine yönelik hibrit evrimsel bir algoritma

    ALPER TÜRKYILMAZ

    Doktora

    İngilizce

    İngilizce

    2023

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

    Mühendislik Yönetimi Ana Bilim Dalı

    PROF. DR. SEROL BULKAN

    DOÇ. DR. ÖZLEM ŞENVAR

  5. Tez No

    155222

    Analyzing and evaluating priority rules for job shop scheduling problems

    Atölye tipi çizelgeleme problemleri için öncelik kurallarının analiz edilmesi ve değerlendirilmesi

    MUSTAFA BATUHAN AYHAN

    Yüksek Lisans

    İngilizce

    İngilizce

    2004

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

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

    Y.DOÇ. SEROL BULKAN

Geri Dön