Newly proposed algorithms based on column generation and metaheuristics for flexible job shop scheduling problem
Esnek atölye tipi çizelgeleme problemi için geliştirilen sütun üretme ve metasezgisellere dayalı algoritmalar
- Tez No: 338213
- Danışmanlar: PROF. DR. YUSUF İLKER TOPCU
- Tez Türü: Doktora
- Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2013
- Dil: İngilizce
- Ü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ı: 249
Özet
Esnek Atölye Tipi Çizelgeleme Problemi (EATP), çözümü zor ve çizelgeleme teorisinde en sık araştırılan konulardan biri olan Atölye Tipi Çizelgeleme Probleminin (ATP) daha genel ve çok daha karmaşık halidir. Genel ATP'de operasyonların hangi makinada işleneceği bellidir. Oysa EATP hem operasyonların hangi makinaya atanacağı kararını, hem de makinalardaki iş sırası kararını içerir. Tezde EATP için, en düşük yayılma süresini veren çizelgeyi bulmayı hedefleyen iki yeni yöntem geliştirilmiştir. İlk yöntem çalışma kapsamında araştırılan EATP literatüründe kullanılmamış olan sütun üretme (SÜ) algoritmasına dayanır. SÜ algoritması çok sayıda değişkenin olduğu problemlerde gevşetilmiş doğrusal programlamanın en iyi sonucunu bulmak için kullanılır. Bu çalışmada SÜ algoritması uygulandıktan sonra, yaratılan tüm sütunları içeren bir karışık tamsayılı programlama probleminin tam çözümü bulunur. Literatürden alınan çeşitli EATP verileri üzerinde elde edilen sonuçlara göre, SÜ gelecek çalışmalarda yapılacak metasezgisel bir arama için yeterince iyi bir sınırlandırılmış arama uzayı elde etmiştir. Tez kapsamında geliştirilen ikinci yöntem ise önceliğe dayalı kodlama kullanılarak geliştirilen Genetik Algoritmadır (GA). Önerilen GA?da her kromozom olası tüm operasyonlar için bir gen içerir ve her bir gen tez kapsamında geliştirilen yapıcı sezgisel algoritmada ilgili operasyonun öncelik değerini verir. Geliştirilen yapıcı algoritma FSJP için aktif çizelge oluşturmak için kullanılır. Literatürden alınan problemlere önerilen GA uygulanmıştır. Sonuç olarak esnekliği en az olan ve zayıf alt sınıra sahip solduğu için diğerlerinden daha zor olan problemlerde, önerilen GA literatürdeki algoritmalardan daha iyi sonuçlar bulmuştur.
Özet (Çeviri)
One of the most researched topics in scheduling theory is job shop scheduling problem (JSP) which is known as difficult to solve. Flexible Job Shop Scheduling Problem (FJSP) is more complex and general than classical JSP. Unlike JSP; each operation can be processed by one of the machines in a given machine set. The aim of FJSP is finding both an assignment and a corresponding scheduling that minimize production time. In this thesis, two novel algorithms are developed for FJSP. The first algorithm is based on Column Generation (CG) approach which guarantees to find optimum solution of linear programming (LP) relaxation. CG is an exact algorithm to solve the LP models with an enormous number of variables. At the end of CG, a mixed integer programming problem with all generated columns is solved to find an integer solution. According to the computational results, the restricted search space is good enough to use metaheuristic search in further studies. The second approach developed in this study is Genetic Algorithms (GA) with priority based representation. Each gene of a chromosome represents the priority of corresponding operation which is used during constructive algorithm developed for decoding. The constructive algorithm can generate all active schedules which constitute a subset of feasible schedules including optimal one. The computational results showed that the proposed GA performs at the same level or better with respect to the makespan for the problems with low flexibility.
Benzer Tezler
- Bridging knowledge across architectural heritage and digital fabrication technologies
Mimari miras ile dijital fabrikasyon teknolojileri arasında bilgi köprüsü kurmak
BEGÜM HAMZAOĞLU
Doktora
İngilizce
2024
Mimarlıkİstanbul Teknik ÜniversitesiBilişim Ana Bilim Dalı
PROF. DR. MİNE ÖZKAR KABAKÇIOĞLU
- Timolol maleat içeren ticari farmasötik preparatlardaki etkin maddelerin spektrofotometrik ve kromatografik ölçümlere dayalı kemometrik yöntemlerle miktar tayinleri
Quantitative analysis of timolol maleate and active compounds in commercial pharmaceutical preparations based on spectrophotometric and chromatographic measurements with chemometric methods
EDA BIYIK
Doktora
Türkçe
2017
Eczacılık ve FarmakolojiAnkara ÜniversitesiAnalitik Kimya Ana Bilim Dalı
PROF. DR. ERDAL DİNÇ
- Grup teknolojisi imalat sistemi ve sezgisel bir kümelendirme yöntemi
Group technology manufacturing system and a heuristic clustering method
A. KAMİL ATALAR
Yüksek Lisans
Türkçe
1991
Endüstri ve Endüstri Mühendisliğiİstanbul Teknik ÜniversitesiPROF.DR. ATAÇ SOYSAL
- Fizyolojik süreçlerde model tabanlı yeni öğrenme yaklaşımları
Model based learning algorithms based on physiological processes
UĞUR AYAN
Doktora
Türkçe
2010
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolYıldız Teknik ÜniversitesiElektrik Mühendisliği Ana Bilim Dalı
PROF. DR. GALİP CANSEVER
- Design and development of novel obstacle avoidance algorithms using the fully autonomous wheelchair platform
Tam otonom tekerlekli sandalye platformu kullanarak yenilikçi engelden kaçınma algoritmalarının tasarımı ve geliştirilmesi
HOSEIN HOUSHYARI
Yüksek Lisans
İngilizce
2021
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiKontrol ve Otomasyon Mühendisliği Ana Bilim Dalı
DOÇ. DR. VOLKAN SEZER