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
- Tez No: 199044
- Danışmanlar: PROF. DR. MERAL AZİZOĞLU
- Tez Türü: Doktora
- Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
- 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
- Yıl: 2006
- Dil: İngilizce
- Üniversite: Orta Doğu Teknik Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: Belirtilmemiş.
Ö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
- 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
- Rescheduling parallel machines with controllable processing times
Kontrol edilebilir işlem süreleriyle paralel makinalarda yeniden çizelgeleme
MÜGE MUHAFIZ
Yüksek Lisans
İngilizce
2012
İhsan Doğramacı Bilkent ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
Yükleniyor...
- Çok amaçlı karar verme metodları ve tekstil sanayiinde bir uygulama
Multiple criteria decision making methods and an application to the textile industry
H.EDA ÖZTÜRK
- 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
2000
Orta Doğu Teknik ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
Yükleniyor...
