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: Atölye çizelgelemesi, Genetik algoritmalar, Sütun üretme, Tam sayılı programlama, Job shop scheduling, Genetic algorithms, Column generation, Integer programming
- 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ı: Belirtilmemiş.
Ö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
- 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
BiyoistatistikYıldız Teknik ÜniversitesiElektrik Mühendisliği Ana Bilim Dalı
PROF. DR. GALİP CANSEVER
- Genomik verinin analizinde yapay arı koloni algoritması temelli yeni tekniklerin geliştirilmes
Developing new techniques based on artificial bee colony algorithm for analysis of genomic data
SELÇUK ASLAN
Doktora
Türkçe
2016
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolErciyes ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
PROF. DR. DERVİŞ KARABOĞA
- Enterkonnekte güç si̇stemleri̇nde rüzgâr enerji̇ si̇stemleri̇ni̇n güç akiş anali̇zi̇ne etki̇leri̇ni̇n modern opti̇mi̇zasyon tekni̇kleri̇ i̇le i̇ncelenmesi̇
Investigation of the effects of wind energy systems on power flow analysis in interconnected power systems by modern optimization techniques
MEHMET GÜÇYETMEZ
Doktora
Türkçe
2016
EnerjiKırıkkale ÜniversitesiElektrik-Elektronik Mühendisliği Ana Bilim Dalı
DOÇ. DR. ERTUĞRUL ÇAM