Metaheuristic approaches to single machine total weighted tardiness problem
Tek makinada toplam ağırlıklı artı gecikme problemine metahüristik yaklaşımlar
- Tez No: 129390
- Danışmanlar: DOÇ. DR. ÜMİT BİLGE
- Tez Türü: Yüksek Lisans
- Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
- Anahtar Kelimeler: Genetik algoritmalar, Makineler, Tabu arama, Toplam ağırlıklı gecikme, Genetic algorithms, Machinery, Tabu search, Total weighted tardiness
- Yıl: 2002
- Dil: İngilizce
- Üniversite: Boğaziçi Ü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
ÖZET TEK MAKİNADA TOPLAM AĞIRLIKLI ARTI GECİKME PROBLEMİNE METAHÜRİSTİK YAKLAŞIMLAR Bu tezin konusu, Tek Makina Toplam Ağırlıklı Artı Gecikme (TMTAG) problemi için Tabu Arama (TA) ve Genetik Algoritmalar (GA) yaklaşımlarını kullanarak geliştirilen çözüm yöntemleridir. Ele alman problem, bağımsız, boşaltmasız n sayıdaki işin tek bir makinaya atanarak toplam artı gecikmenin enküçüklenmesidir. Bu çalışmada, bahsi geçen probleme genel bir yaklaşım izlenmekte ve her bir iş için sıfırdan farklı ve ayrı termin tarihleri, sisteme giriş zamanlan, işlem zamanlan ve işin önemini belirten ağırlıklar ele alınmaktadır. TMTAG'nın teorik bazı, problemin NP-Zor doğasını ortaya çıkarmaktadır. Bu nedenle problem, ilginç ve iddialı bir araştırma konusu haline gelmiştir. Geliştirilen çözüm yöntemlerinin performans analizi literatürden alınmış bir problem seti üzerinde yapılmıştır. Bu problem setinin özelliği, TMTAG probleminin statik versiyonundan oluşması, yani sisteme giriş zamanlarının her iş için aynı ve sıfır olmasıdır. Ayrıca, bu problem setinde iş hazırlık zamanlan da sıraya bağlı değildir. Sağlam bir TA ve GA mekanizması geliştirmek için bu meta-hüristik yöntemlerin temel öğeleri incelenmiştir. TA yaklaşımı için ele alman öğeler arasında tabu klasifikasyonu, aday liste stratejisi, tabu süresi ve detaylı tarama-kuvvetlendirme yer almaktadır. GA için ele alman temel öğeler, jenerasyon tipi, başlangıç toplumunun yapısı, ana-baba seçimi, gen kesiştirme ve mutasyondur. Geliştirilen TA ve GA yaklaşımları karşılaştırılmış ve tamamen deterministik olan TA yaklaşımı rassal GA yaklaşımından daha iyi sonuçlar ortaya çıkarmıştır. Her iki yöntem de literatürde yayınlanmış bilinen en iyi çözümlerle karşılaştırıldıklarında, yüksek kalitede sonuçlar vermektedir.
Özet (Çeviri)
IV ABSTRACT METAHEURISTIC APPROACHES TO SINGLE MACHINE TOTAL WEIGHTED TARDINESS PROBLEM In this thesis, a Tabu Search (TS) and a Genetic Algorithm (GA) approach to the Single Machine Total Weighted Tardiness problem (SMTWT) is presented. The problem considered consists of a set of independent jobs to be scheduled on a single machine to minimize the total weighted tardiness. This study addresses the generic version of SMTWT, where distinct ready times, processing times, due dates and weights for each job are considered. The theoretical foundation of SMTWT reveals the NP-Hard nature of the problem, and the problem becomes an interesting and challenging area of research. The performance evaluation for the strategies developed is done on a set of problems obtained from the literature, where ready times are all identically equal to zero and setup times are not sequence dependent. In order to develop robust TS and GA mechanisms, the key elements of each metaheuristic are investigated. For the TS approach, the key elements tackled are the tabu classification, candidate list strategy, tabu tenure and intensification whereas for the GA approach, generation type, initial population structure, parent selection, crossover and mutation are some of the fundamentals addressed. The TS and GA approaches are compared and the totally deterministic TS approach dominates the probabilistic GA approach in different performance measures. Both methods yield high quality results with respect to the optimal/best-known values reported in the literature.
Benzer Tezler
- Ç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
- A Genetic algorithm based meta-heuristic for capacitated vehicle routing problem with simultaneous pick-up and delivery
Eş zamanlı dağıtım ve toplama içeren kapasiteli araç rotalama problemi için genetik algoritma bazlı sezgisel yaklaşım
ARİF VOLKAN VURAL
Yüksek Lisans
İngilizce
2003
Endüstri ve Endüstri MühendisliğiSabancı ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. BÜLENT ÇATAY
- 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
MEHMET ŞEVKLİ
Doktora
Türkçe
2005
Endüstri ve Endüstri Mühendisliğiİstanbul Teknik ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
Y.DOÇ.DR. MEHMET MUTLU YENİSEY
- Performance analysis of hyperheuristics and their use with hill-climbers
Yardımlı buluşsal algoritmalar ve bunların tepe tırmanma operatörleri ile kullanımının başarım çözümlenmesi
BURAK BİLGİN
Yüksek Lisans
İngilizce
2006
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolYeditepe ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
Y.DOÇ.DR. ENDER ÖZCAN
- Ant colony optimization for the model U-type assembyl line balancing problem
Tek modelli U-tipi montaj hattı dengelenmesi problemi için karınca kolonisi optimizasyonu
ARDA ALP
Yüksek Lisans
İngilizce
2004
Endüstri ve Endüstri Mühendisliğiİhsan Doğramacı Bilkent ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
PROF.DR. İHSAN SABUNCUOĞLU