Cut generation based algorithms for unrelated parallel machine scheduling problems
Alakasız paralel makine çizelgeleme problemlerine kesi türetme tabanlı algoritmalar
- Tez No: 420263
- Danışmanlar: DOÇ. DR. KEREM BÜLBÜL
- Tez Türü: Doktora
- Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2015
- Dil: İngilizce
- Üniversite: Sabancı Üniversitesi
- Enstitü: Mühendislik ve Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: Belirtilmemiş.
Özet
Alakasız paralel makine ortamındaki çizelgeleme problemleri üzerindeki araştırmalar en iyimser bakış açısıyla sınırlı durumdadırlar. Dahası, bu alanda var olan çalışmaların neredeyse tümü iş tamamlanma zamanıyla alakalı performans ölçütlerinin enküçüklenmesine yoğunlaşmış durumdadır ve literatürdeki mevcut çözüm yaklaşımları ölçeklenebilirlik sorunlarından muzdaripdirler. Bu tezde, matematiksel programlama tabanlı ayrıştırma yaklaşımlarının başarısından güç alınarak, dört adet NP-zor alakasız paralel makine çizelgeleme problemine ölçeklenebilir, etkili ve yüksek verimli kesi türetme tabanlı algoritmalar tasarlanmıştır. İlk kısımda, toplam ağırlıklandırılmış gecikme ve toplam ağırlıklandırılmış erkenlik/gecikme problemleri için yeni bir geçişli gevşetme geliştirilmiş ve bir karışık tamsayılı doğrusal program olarak formüle edilmiş bu geçişli gevşetmeyi çözmek için bir Bender ayrıştırma algoritması tasarlanmıştır. Yaklaşımımızın etkinliğini göstermek üzere 5 makine ve 200 iş büyüklüğüne kadar örnekler çözülmüştür. İkinci kısım toplam ağırlıklandırılmış tamamlanma zamanı problemini ele almakta ve ilk kısımda geliştirilen geçişli gevşetmenin bu problem için pekin bir gösterim olduğunu ispatlamaktadır. Dahası, bu performans ölçütünün yapısal özelliklerinden faydalanılarak, 8 makine ve 1000 iş büyüklüğüne kadar örneklerin eniyi çözümlerine saniyeler içerisinde ulaşan pekin bir Benders ayrıştırma algoritması elde edilmiştir. Sonuncu kısımda ise kısıtlandırılmamış ortak termin zamanlı tam zamanında çizelgeleme problemi ele alınmakta ve mantık tabanlı Benders ayrıştırma algoritması geliştirilmektedir. Bu problem için en başarılı çözüm yaklaşımını sunmanın yanı sıra, bu kısım, düzenli olmayan enküçük-toplam performans ölçütlü çizelgeleme problemleri için ölçeklenebilir bir mantık tabanlı algoritma tasarlamanın mümkün olduğunu göstermektedir.
Özet (Çeviri)
Research on scheduling in the unrelated parallel machine environment is at best scarce. Moreover, almost all existing work in this area is focused on the minimization of completion time related performance measures and the solution approaches available in the literature suffer from scalability issues. In this dissertation, we leverage on the success of the mathematical programming based decomposition approaches and devise scalable, efficient, and effective cut generation based algorithms for four NP-hard unrelated parallel machine scheduling problems. In the first part, we develop a new preemptive relaxation for the total weighted tardiness and total weighted earliness/tardiness problems and devise a Benders decomposition algorithm for solving this preemptive relaxation formulated as a mixed integer linear program. We demonstrate the effectiveness of our approach with instances up to 5 machines and 200 jobs. The second part deals with the problem of minimizing the total weighted completion time and proves that the preemptive relaxation developed in part one is an exact formulation for this problem. By exploiting the structural properties of the performance measure, we attain an exact Benders decomposition algorithm which solves instances with up to 1000 jobs and 8 machines to optimality within a few seconds. In the last part, we tackle the unrestricted common due date just-in-time scheduling problem and develop a logic-based Benders decomposition algorithm. Aside from offering the best solution approach for this problem, we demonstrate that it is possible to devise scalable logic-based algorithms for scheduling problems with irregular minsum objectives.
Benzer Tezler
- Column generation-based methods for the electric vehicle routing problems with time windows
Zaman pencereli elektirikli araç rotalama problemi için sütun türetme algoritmasına dayalı çözüm yöntemleri
ECE NAZ DUMAN
- Algorithms for the vehicle routing problem with time windows and the location-routing problem
Zaman çerçeveli araç rotalama problemi ve yer bulma-rotalama problemi için algoritmalar
SUAT BOĞ
- Relaying opportunities for wireless networks by applying network coding
Kablosuz ağlar için ağ kodlamalı aktarma fırsatları
SEMİHA TEDİK BAŞARAN
Doktora
İngilizce
2019
İstanbul Teknik ÜniversitesiElektronik ve Haberleşme Mühendisliği Ana Bilim Dalı
Yükleniyor...
- Global optimization methods for optimal power flow and transmission switching problems in electric power systems
Başlık çevirisi yok
BURAK KOCUK
- A fully automatic shape based geo-spatial object recognition
Tam otomatik şekil tabanlı yer uzamsal nesne tanıma
MUSTAFA ERGÜL
Yüksek Lisans
İngilizce
2012
Orta Doğu Teknik ÜniversitesiElektrik-Elektronik Mühendisliği Ana Bilim Dalı
Yükleniyor...