Geri Dön

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

  1. Tez No: 338213
  2. Yazar: DİDEM ÇINAR
  3. Danışmanlar: PROF. DR. YUSUF İLKER TOPCU
  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: 2013
  8. Dil: İngilizce
  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ı: 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

  1. 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

    İngilizce

    2024

    Mimarlıkİstanbul Teknik Üniversitesi

    Bilişim Ana Bilim Dalı

    PROF. DR. MİNE ÖZKAR KABAKÇIOĞLU

  2. 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

    Türkçe

    2017

    Eczacılık ve FarmakolojiAnkara Üniversitesi

    Analitik Kimya Ana Bilim Dalı

    PROF. DR. ERDAL DİNÇ

  3. 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

    Türkçe

    1991

    Endüstri ve Endüstri Mühendisliğiİstanbul Teknik Üniversitesi

    PROF.DR. ATAÇ SOYSAL

  4. 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

    Türkçe

    2010

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolYıldız Teknik Üniversitesi

    Elektrik Mühendisliği Ana Bilim Dalı

    PROF. DR. GALİP CANSEVER

  5. 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

    İngilizce

    2021

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik Üniversitesi

    Kontrol ve Otomasyon Mühendisliği Ana Bilim Dalı

    DOÇ. DR. VOLKAN SEZER