Investigation of solution methodologies for the proposed combinatorial scheduling models
Önerilen kombinatoryel çizelgeleme modelleri için çözüm yöntemlerinin araştırılması
- Tez No: 138904
- Danışmanlar: PROF. DR. İREM ÖZKARAHAN
- Tez Türü: Doktora
- Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
- Anahtar Kelimeler: kombinatoryel optimizasyon, karışık tamsayı programlama, kısıt programlama, çizelgeleme, combinatorial optimization, mixed integer programming, constraint programming, scheduling
- Yıl: 2003
- Dil: İngilizce
- Üniversite: Dokuz Eylül Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Endüstri Mühendisliği Bilim Dalı
- Sayfa Sayısı: 287
Özet
ÖZET Bu tez üç farklı kombinatoryel optimizasyon problemiyle ilgilenmektedir. Amaç karışık tamsayı programlama (KTP), kısıt programlama (KP) ve bunların ortak çözümlerini kullanarak etkin modeller ve çözüm yöntemleri geliştirmektir. İlk olarak, kombinatoryel optimizasyon problemleri, komplekslik analizi, uygulama alanları ve çözüm teknikleri tartışılmaktadır. Matematiksel programlama tekniklerine alternatif bir yöntem olarak kısıt programlama KTP ile karşılaştırılmakta ve bu iki yaklaşımın entegrasyonuyla ilgili literatür ayrıntılı bir şekilde aktarılmaktadır. Birinci uygulamada tek makine için, ardışık işler arasında şuaya bağlı ayarların bulunduğu bir iş sıralama problemi dikkate alınmaktadır, öncelikle, bu problemin KTP ve KP modelleri sunulmakta ve ardından bu iki modelden oluşan birleşik bir model tanıtılmaktadır. Daha sonra, KP arama işlemi için probleme özgü bilgiyi ve KTP ile KP çözücülerinin entegrasyonunu kullanan birtakım sezgisel yöntemler geliştirilmektedir. Karşılaştırmalı performans analizi bu sezgisel yöntemler ile KTP ve KP çözücüleri arasında ayrıntılı olarak verilmektedir. ikinci uygulama olarak, personel çizelgeleme problemi için bir amaç programlama modeli (AP) önerilmektedir. Model esnek çizelgeleme alternatiflerini ve personelin çalışma saatleri ile ilgili tercihlerini içermektedir. Modelin değişen çizelgeleme ihtiyaçlarına göre etkinliği ve cevap verebilirliği test edilmekte ve işlemsel analizin sonuçları aktarılmaktadır. Alternatif olarak KP'ye dayalı bir çözüm yöntemi önerilmekte ve bu yaklaşımın AP modeline göre etkinliği araştırılmaktadır. Son uygulama asistan doktorların aylık çizelgelenmesiyle ilgilidir. İlk olarak, asistanların görev saatleri ile ilgili düzenlemeleri ve ihtisas programının ihtiyaçlarımiçeren bir KTP modeli tartılmaktadır. Bu model kısıtlı sayıda asistan çizelgelediği için, iki aşamalı bir çözüm yaklaşımı önerilmektedir. İlk aşamada geliştirilen bir KP modeli ile asistanlardan bağımsız uygun iş çizelgeleri türetilmekte ve ikinci aşamada önerilen bir başka KTP modeli ile asistanların bu çizelgelerin bir kısmına optimum olarak dağıtılması sağlanmaktadır. Bu yaklaşım farklı çizelgeleme ortamları ve senaryoları için test edilmektedir. Test sonuçlan gittikçe artan sayıdaki asistan çizelgelemesi için verilmektedir.
Özet (Çeviri)
ABSTRACT This thesis deals with three different combinatorial optimization problems (COPs). The goal is to develop efficient models and solution methods using mixed integer programming (MIP), constraint programming (CP) and their collaboration. Initially, combinatorial optimization problems, their complexity analysis, application areas and solution techniques are discussed. As an alternative method to the traditional mathematical programming techniques, an in-depth overview of CP is presented, including a comparative analysis of CP and MIP and an overview of related research concerning the integration of the two approaches. Our first application is a job sequencing problem for a single machine with sequence dependent setups between consecutive jobs. At first, the MIP and CP models are presented for this problem. Subsequently, a combined model consisting of these two models is introduced. Then, several search heuristics are developed for the CP approach using problem specific information and integration of the MIP and CP solvers. A detailed comparative performance analysis is made between the search heuristics, and the MIP and CP solvers. As the second application, a goal programming model (GP) is proposed for an employee scheduling problem. The model accommodates flexible scheduling alternatives and employee work preferences. The efficiency and the responsiveness of the model to the changing scheduling requirements are tested, and the results of the computational analysis are given. As an alternative, a CP-based solution approach is proposed, and its efficiency is investigated with comparison to the GP model.The last application involves the scheduling of hospital residents on a monthly basis. A MIP model is first introduced that accommodates resident duty hour regulations and requirements of the residency program. This model is limited to scheduling a very small number of residents. For this reason, a two-phase solution approach is proposed, which generates feasible individual schedules apart from the residents by a developed CP model in the first phase and then assigns residents to a subset of these schedules optimally in the second phase by another proposed MIP model. The approach is tested for different scheduling environments and scenarios. The testing results for scheduling an increasing number of residents are given.
Benzer Tezler
- Investigation of transposition models, optimization of tilt angles, and solar radiation intensity for fixed and tracked south-facing solar photovoltaic surfaces in provinces of türkiye
Transpozisyon modellerinin incelenmesi, türkiye illerinde sabit ve güneş takipli güneye bakan fotovoltaik yüzeyler için eğim açılarının ve güneş radyasyon yoğunluğunun optimizasyonu
BATUR ALP AKGÜL
Doktora
İngilizce
2024
Elektrik ve Elektronik MühendisliğiHasan Kalyoncu ÜniversitesiElektrik-Elektronik Mühendisliği Ana Bilim Dalı
PROF. DR. MUSTAFA SADETTİN ÖZYAZICI
- A novel approach for the incipience of sediment entrainment in a wide range of flow conditions via experimentally driven geno-fuzzy inference system model
Deneysel veri tabanlı geliştirilen özgün genetik-fuzzy yöntemi ile akım şartlarının geniş aralığında sediment hareketinin başlangıcının araştırılması
HUSSEIN BIZIMANA
Doktora
İngilizce
2020
İnşaat Mühendisliğiİstanbul Teknik Üniversitesiİnşaat Mühendisliği Ana Bilim Dalı
PROF. DR. ABDÜSSELAM ALTUNKAYNAK
- Microzonation with respect to rainfall-induced landslides
Yağmur kaynaklı yamaç kaymaları için mikrobölgeleme
OKAN İLHAN
Yüksek Lisans
İngilizce
2015
Deprem MühendisliğiBoğaziçi ÜniversitesiDeprem Mühendisliği Ana Bilim Dalı
PROF. DR. ERDAL ŞAFAK
PROF. DR. MUSTAFA ATİLLA ANSAL
- Bir hafif hibrit elektrikli şehir içi otobüs uygulamasının performans, yakıt ekonomisi ve çevresel etkileri açısından incelenmesi
The investigation of the impact of mild hybrid electric city bus application on performance, fuel economy and emissions
ALİCAN YILMAZ
Yüksek Lisans
Türkçe
2018
Makine Mühendisliğiİstanbul Teknik ÜniversitesiMakine Mühendisliği Ana Bilim Dalı
PROF. DR. İSMAİL AHMET GÜNEY
- Probabilistic forecasting of multiple time series with single recurrent neural network
Bir özyineli sinir hücresi ağı ile çoklu zaman serilerinin olasılıksal tahminlenmesi
SARP TUĞBERK TOPALLAR
Yüksek Lisans
İngilizce
2022
İstatistikOrta Doğu Teknik ÜniversitesiBilimsel Hesaplama Ana Bilim Dalı
PROF. DR. CEYLAN YOZGATLIGİL