Tez No	İndirme	Tez Künye	Durumu
199044		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 Yazar:MELİH ÖZLEN Danışman: PROF. DR. MERAL AZİZOĞLU Yer Bilgisi: Orta Doğu Teknik Üniversitesi / Fen Bilimleri Enstitüsü / Endüstri Mühendisliği Ana Bilim Dalı Konu:Endüstri ve Endüstri Mühendisliği = Industrial and Industrial Engineering Dizin:	Onaylandı Doktora İngilizce 2006 113 s.
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.Anahtar Kelimeler: İki Kriterli Ağ Akışları, Yeniden Çizelgeleme, Paralel İlgisizMakinalar, Toplam Akış Zamanı, Toplam Yeniden Atama Maliyeti
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.Keywords: Bicriteria Network Flows, Rescheduling, Parallel Unrelated Machines, TotalFlowtime, Total Reassignment Cost