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
- Tez No: 166630
- Danışmanlar: Y.DOÇ.DR. MEHMET MUTLU YENİSEY
- Tez Türü: Doktora
- Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2005
- Dil: Türkçe
- Üniversite: İstanbul Teknik Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: Belirtilmemiş.
Ö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
- 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
2004
Endüstri ve Endüstri MühendisliğiMarmara ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
Y.DOÇ. SEROL BULKAN
- Atölye tipi çizelgeleme için uzman-tabu arama modeli
Expert-tabu search for job-shop scheduling
FARUK GEYİK
Doktora
Türkçe
2000
Endüstri ve Endüstri MühendisliğiSakarya ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. İSMAİL HAKKI CEDİMOĞLU
- Çok objektifli esnek atölye çizelgeleme problemlerinin sezgisel yöntemlerle modellenmesi, analizi ve çözümü
Modeling, analyzing and solving multiple-objective flexible job-shop scheduling problems by using meta-heuristic algorithms
LALE ÖZBAKIR
- Zeki etmenlerde öğrenme kabiliyetinin geliştirilmesi ve dinamik bir atölye tipi çizelgeleme uygulaması
Başlık çevirisi yok
MEHMET EMİN AYDIN
Doktora
Türkçe
1997
Endüstri ve Endüstri MühendisliğiSakarya ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DOÇ.DR. ERCAN ÖZTEMEL
- Atölyede iş çizelgeme
Operations scheduling in job shops
GÖKHAN KIPÇAK
Yüksek Lisans
Türkçe
1990
Endüstri ve Endüstri Mühendisliğiİstanbul Teknik ÜniversitesiPROF.DR. ATAÇ SOYSAL