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ı: 137
Ö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
Doktora
İngilizce
2022
EnerjiSabancı ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
PROF. DR. BÜLENT ÇATAY
DR. ÖĞR. ÜYESİ DUYGU TAŞ KÜTEN
- 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Ğ
Yüksek Lisans
İngilizce
2006
Endüstri ve Endüstri MühendisliğiKoç ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. SELÇUK SAVAŞ
YRD. DOÇ. DR. METİN TÜRKAY
- Optimal server placement, service deployment, and resource allocation in next-generation computer networks
Yeni nesil bilgisayar ağlarında sunucu yerleştirme, servis dağıtımı ve kaynak tahsisi eniyilemesi
BETÜL AKTEL
Doktora
İngilizce
2022
Endüstri ve Endüstri MühendisliğiBoğaziçi ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
PROF. DR. MUSTAFA NECATİ ARAS
PROF. DR. İSMAİL KUBAN ALTINEL
- Parça yerleştirme algoritmalarının postal oluşturma problemine uygulanması
Başlık çevirisi yok
FİLİZ BUNYAK
Yüksek Lisans
Türkçe
1996
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiDOÇ.DR. FÜSUN TUNALI (SEÇUK)
- Global optimization methods for optimal power flow and transmission switching problems in electric power systems
Başlık çevirisi yok
BURAK KOCUK
Doktora
İngilizce
2016
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolGeorgia Institute of TechnologyDOÇ. DR. SANTANU S. DEY
YRD. DOÇ. DR. X. ANDY SUN