Geri Dön

Investigation of solution methodologies for the proposed combinatorial scheduling models

Önerilen kombinatoryel çizelgeleme modelleri için çözüm yöntemlerinin araştırılması

  1. Tez No: 138904
  2. Yazar: ŞEYDA TOPALOĞLU
  3. Danışmanlar: PROF. DR. İREM ÖZKARAHAN
  4. Tez Türü: Doktora
  5. Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
  6. Anahtar Kelimeler: kombinatoryel optimizasyon, karışık tamsayı programlama, kısıt programlama, çizelgeleme, combinatorial optimization, mixed integer programming, constraint programming, scheduling
  7. Yıl: 2003
  8. Dil: İngilizce
  9. Üniversite: Dokuz Eylül Üniversitesi
  10. Enstitü: Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
  12. Bilim Dalı: Endüstri Mühendisliği Bilim Dalı
  13. 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

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

    İngilizce

    2024

    Elektrik ve Elektronik MühendisliğiHasan Kalyoncu Üniversitesi

    Elektrik-Elektronik Mühendisliği Ana Bilim Dalı

    PROF. DR. MUSTAFA SADETTİN ÖZYAZICI

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

    İngilizce

    2020

    İnşaat Mühendisliğiİstanbul Teknik Üniversitesi

    İnşaat Mühendisliği Ana Bilim Dalı

    PROF. DR. ABDÜSSELAM ALTUNKAYNAK

  3. Microzonation with respect to rainfall-induced landslides

    Yağmur kaynaklı yamaç kaymaları için mikrobölgeleme

    OKAN İLHAN

    Yüksek Lisans

    İngilizce

    İngilizce

    2015

    Deprem MühendisliğiBoğaziçi Üniversitesi

    Deprem Mühendisliği Ana Bilim Dalı

    PROF. DR. ERDAL ŞAFAK

    PROF. DR. MUSTAFA ATİLLA ANSAL

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

    Türkçe

    2018

    Makine Mühendisliğiİstanbul Teknik Üniversitesi

    Makine Mühendisliği Ana Bilim Dalı

    PROF. DR. İSMAİL AHMET GÜNEY

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

    İngilizce

    2022

    İstatistikOrta Doğu Teknik Üniversitesi

    Bilimsel Hesaplama Ana Bilim Dalı

    PROF. DR. CEYLAN YOZGATLIGİL