Geri Dön

A bicriteria rescheduling problem on unrelated parallel machines: Network flow and enumeration based approaches

İlgisiz paralel makinelerde iki kriterli yeniden çizelgeleme problemi: Ağ akış ve birerleme tabanlı yaklaşımlar

  1. Tez No: 199044
  2. Yazar: MELİH ÖZLEN
  3. Danışmanlar: PROF. DR. MERAL AZİZOĞLU
  4. Tez Türü: Doktora
  5. Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
  6. Anahtar Kelimeler: İki Kriterli Ağ Akışları, Yeniden Çizelgeleme, Paralel İlgisizMakinalar, Toplam Akış Zamanı, Toplam Yeniden Atama Maliyeti, Bicriteria Network Flows, Rescheduling, Parallel Unrelated Machines, TotalFlowtime, Total Reassignment Cost
  7. Yıl: 2006
  8. Dil: İngilizce
  9. Üniversite: Orta Doğu 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ı: 113

Özet

Bu çalışmada enaz maliyetli ağ akış problemine iki kriterli yaklaşımlar, ve buyaklaşımların uygulandığı bir yeniden çizelgeleme problemi ele alınmaktadır.İki kriterli kesikli enaz maliyetli ağ akış probleminin tüm verimli noktaları ikiaşamada bulunmuştur. İlk aşamada sürekli iki kriterli enaz maliyetli ağ akış problemininamaç uzayında köşe noktalarda yer alan, köşe destekli verimli noktalar bulunmuştur.İkinci aşamada, destekli olmayan verimli noktalar, ve köşe olmayan destekli verimlinoktalar, Tam Sayılı Programlamaya dayalı yaklaşımlarla bulunmuştur.Yeniden çizelgeleme problemimiz ilgisiz parallel makinalar ortamlarında elealınmıştır. Verimlilik ölçütü olarak toplam akış zamanı kriteri, ve tutarlılık ölçütüolarak toplam yeniden atama maliyeti kriteri kullanılmıştır. İki kriterin doğrusalfonksiyonunu ele alan problemlerin iki kriterli enaz maliyetli ağ akış modellerikullanılarak ifade edilebileceği gösterilmiştir. Tüm verimli noktaların yaratılması için,tek kısıtlı ağ akışı probleminin en iyi çözümlerine dayalı Klasik Yöntem kullanılmıştır,ve köşe destekli verimli noktalarla başlayan Dal ve Sınır yöntemi önerilmiştir. İkikriterin her hangi bir doğrusal olmayan fonksiyonun en iyi çözümünü bulmak için,verimli kümenin daha iyi çözümler sağlayamayacak kısımlarını eleyen, Tam SayılıProgramlamaya dayalı bir yöntem, ve Dal-Sınır yöntemi önerilmiştir.Bu çalışmada iki kriterli ağ akış problemleri için çözüm yöntemleri önerilerek,ve bu önerilen yöntemler, doğası gereği iki kriterli olan bir yeniden çizelgelemeproblemi üzerinde uygulanarak, hem ağ akışları ve hem de çizelgeleme alanlarına katkıyapılmıştır.100 iş, ve 12 makinalı problemleri çözebilen geniş çaplı deneysel çalışmamızınsonuçları, Dal-Sınır yönteminin, Klasik yöntemle karşılaştırıldığında, tüm verimlinoktaları daha az çözüm zamanı harcayarak bulduğunu göstermiştir. Doğrusal olmayanbir fonksiyonun en azlanmasında, Tam Sayılı Programlama tabanlı yöntem ve Dal-Sınıralgoritmasının her ikisinin de oldukça başarılı oldukları görülmüştür.

Özet (Çeviri)

This study considers bicriteria approaches to the minimum cost network flowproblem and a rescheduling problem where those approaches find their applications.For the bicriteria integer minimum cost network flow problem, we generate allefficient solutions in two phases. The first phase generates the extreme supportedefficient points that are the extreme points of the objective space of the continuousbicriteria network flow problem. In the second phase, we generate the nonextremesupported and unsupported efficient points by Integer Programming Based approaches.Our rescheduling problem considers parallel unrelated machine environments.The criteria are the total flow time as an efficiency measure and the total reassignmentcost as a stability measure. We show that the problems that address linear functions ofthe two criteria can be represented by bicriteria network flow models. To generate allefficient solutions, we use a Classical Approach that is based on the optimal solutions ofthe singly constrained network flow problem and provide a Branch and Bound approachthat starts with extreme supported efficient set and uses powerful bounds. To find anoptimal solution to any nonlinear function of the two criteria, we provide a Branch andBound approach and an Integer Programming Based approach that eliminates someportions of the efficient set that cannot provide improved solutions.We contribute both to the network flow and scheduling literature by proposingalgorithms to the bicriteria network flow models and applying them to a reschedulingproblem that is bicriteria in nature.The results of our extensive computations with up to 100 jobs and 12 machineshave revealed that, the Branch and Bound algorithm finds the efficient set in lesscomputational effort compared to the classical approach. In minimizing a nonlinearfunction of the two criteria both IP Based approach and Branch and Bound algorithmperform quite satisfactory.

Benzer Tezler

  1. Time/cost trade-offs in machine scheduling with controllable processing times

    Kontrol edilebilir işlem süreleriyle makine çizelgelemede maliyet/zaman ilişkileri

    SİNAN GÜREL

    Doktora

    İngilizce

    İngilizce

    2008

    Endüstri ve Endüstri Mühendisliğiİhsan Doğramacı Bilkent Üniversitesi

    Endüstri Mühendisliği Bölümü

    PROF. DR. M. SELİM AKTÜRK

  2. Rescheduling parallel machines with controllable processing times

    Kontrol edilebilir işlem süreleriyle paralel makinalarda yeniden çizelgeleme

    MÜGE MUHAFIZ

    Yüksek Lisans

    İngilizce

    İngilizce

    2012

    Endüstri ve Endüstri Mühendisliğiİhsan Doğramacı Bilkent Üniversitesi

    Endüstri Mühendisliği Ana Bilim Dalı

    PROF. DR. M. SELİM AKTÜRK

  3. A Bicriteria approach to the two-machine flowshop scheduling problem

    İki makineli akış sistemlerinde çizelgeleme problemine iki kriterli bir yaklaşım

    BERKİN TOKTAŞ

    Yüksek Lisans

    İngilizce

    İngilizce

    2000

    Endüstri ve Endüstri MühendisliğiOrta Doğu Teknik Üniversitesi

    Endüstri Mühendisliği Ana Bilim Dalı

    PROF. DR. SUNA KONDAKCI

    DOÇ. DR. MERAL AZİZOĞLU

  4. Robotik hücrelerde iki kriterli hat dengeleme

    Bicriteria line balancing in robotic cells

    ELİF BÜŞRA ATASEVEN

    Yüksek Lisans

    Türkçe

    Türkçe

    2014

    Endüstri ve Endüstri MühendisliğiTOBB Ekonomi ve Teknoloji Üniversitesi

    Endüstri Mühendisliği Ana Bilim Dalı

    DOÇ. DR. HAKAN GÜLTEKİN

  5. Zamanla değişen parametreler için bir ölçüt

    Başlık çevirisi yok

    YÜKSEL VARDAR

    Doktora

    Türkçe

    Türkçe

    1993

    İstatistikHacettepe Üniversitesi

    İstatistik Ana Bilim Dalı

    DOÇ. DR. AHMET YALNIZ