Parallel machine scheduling to minimize total cost functions
Paralel makina çizelgelemesinde toplam maliyet fonksiyonlarının enazlanması
- Tez No: 35725
- Danışmanlar: PROF. DR. ÖMER KIRCA
- Tez Türü: Doktora
- Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
- Anahtar Kelimeler: Çizelgeleme, Paralel Makinalar, Toplam Ağırlıklı Akış Süresi, Toplam Gecikme, Dal-Smır Algoritması, Makineler, Maliyet fonksiyonları, Scheduling, Parallel Machines, Total Weighted Flow Time, Total Tardiness, Branch and Bound Algorithm, Machinery, Cost functions
- Yıl: 1994
- 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
Öz PARALEL MAKİNA ÇİZELGELEMESİNDE TOPLAM MALİYET FONKSİYONLARININ ENAZLANMASI AZİZO?LU, Meral Doktora Tezi, Endüstri Mühendisliği Ana Bilim Dalı Tez Yöneticisi: Prof. Dr. Ömer Kırca Kasım 1994, 183 sayfa Paralel makina çizelgeleme teorisi, makinaların işlere dağılımı ve belli bir amaca göre her makinada işlem sırasının belirlenmesi ile ilgilidir. Paralel makina çizelgelemesi, yaygın uygulama alanlarının olmasından dolayı popüler bir araştırma konusu olmuştur ve bu popülarite son yıllarda paralel-işlemcili bilgisayar teknolojisinin gelişmesiyle önemli ölçüde artmıştır. Bu tezdeki temel amaç, iş bitiş sürelerinin artmayan bir fonksiyonu olan toplam maliyet minimizasyonunu hedefleyen paralel makina çizelgeleme problemlerine genel bir bakış açısı sağlamaktır. Genel toplam maliyet fonksiyonu için bazı mekanizmalar geliştirilmiş ve bu mekanizmalar, toplam ağırlıklı akış süresi ve toplam gecikme problemleri gibi çok iyi bilinen, pratik problemlerin çözümlemesinde kullanılmıştır.. Toplam ağırlıklı akış sürelerinin enazlanması problemi çalışılırken özdeş, birbiçimli ve ilgisiz paralel makina ortamları için dal- sınır algoritmaları geliştirilmiştir. Her üç makina ortamı için ayrı ayrı önerilen dal-sınır algoritmasında atama probleminin en iyi çözümünü kullanan polinom-zamanlı alt sınırlar ve geliştirilen baskınlık kurallarıkullanılmıştır. Algoritmaların literatürde sunulan metodlara olan üstünlüğü yapılan yaygın deneyler sonucunda gösterilmiştir. Toplam gecikme problemi çözümlenirken, temel olarak, özdeş paralel makinalar üzerinde yoğunlaşılmıştır. Özdeş paralel makinalar için geliştirilen dal-sınır algoritmasının verimliliği, polinom-zamanlı alt ve üst sınırlar ve baskınlık özelliklerinin kullanımıyla artırılmıştır, îşlemsel deneyim, algoritmanın orta boyutlu problemleri makul sürelerde çözebildiğim ve problem yaratmada kullanılan faktörlerin optimal çözümlere ulaşma zorluğu üzerinde baskın rol oynadığını göstermiştir. Çalışmanın son kısmında, özdeş paralel makina ortamları için elde edilen teorik sonuçlar, birbiçimli ve ilgisiz paralel makina ortamlarına, bu alanlarda optimizasyon algoritmalarının geliştirilmesi ümidiyle, uyarlanmıştır.
Özet (Çeviri)
ABSTRACT PARALLEL MACHINE SCHEDULING TO MINIMIZE TOTAL COST FUNCTIONS AZÎZO?LU, Meral Ph.D. in Industrial Engineering Supervisor: Prof. Dr. Ömer Kırca November 1994, 183 pages Parallel machine scheduling theory is concerned with the allocation of machines to a number of jobs, and the determination of the processing order of the jobs on each machine to achieve some prescribed goal. Parallel machine scheduling has been a popular research area due to its wide range of potential application areas and this popularity has been increased considerably during recent years by the emergence of parallel processor computer technology. In this dissertation, the main concern is to provide a general perspective to parallel machine scheduling problems that involve minimization of total costs expressed as nondecreasing functions of job completion times. The mechanisms are derived for the general total cost function and they are used in analyzing two well-known and practical scheduling problems, namely total weighted flow time and total tardiness problems. In studying total weighted flow time problem, we have proposed branch and bound algorithms for identical, uniform and unrelated parallel machine environments. A polynomial lower bounding scheme based upon the optimal solution of the assignment problem and new dominance rules are incorporated into a branch and 111bound algorithm for each machine environment. The results of the extensive computational tests have indicated that the algorithms are superior to prior methods presented in the literature. In analyzing the total tardiness problem, we have primarily concentrated on identical machine environments. For the identical parallel machine problem, we have developed a branch and bound algorithm whose efficiency is improved through the incorporation of polynomial lower and upper bounding schemes and dominance properties. Computational experience has shown that the algorithm can solve medium-sized problems within reasonable time limits and that the factors used in problem generation play a dominant role in the difficulty of attaining optimal solutions. In the final part of the study, the theoretical results derived for identical machines are extended to uniform and unrelated machine environments, with the hope of stimulating progress in the development of optimization algorithms for those machine environments.
Benzer Tezler
- Tam zamanında üretim sistemi ve bir yan sanayi işletmesinde değerlendirilmesi
Just in time production system and evaluation of fit
DİLEK DEMİRDAĞ
Yüksek Lisans
Türkçe
1997
İşletmeİstanbul Teknik Üniversitesiİşletme Mühendisliği Ana Bilim Dalı
PROF. DR. SITKI GÖZLÜ
- Hazırlık sürelerinin analizi ve azaltılması
Setup time analysis and reduction
RIFAT GÜRCAN ÖZDEMİR
Yüksek Lisans
Türkçe
1995
Endüstri ve Endüstri Mühendisliğiİstanbul Teknik ÜniversitesiDOÇ.DR. BÜLENT DURMUŞOĞLU
- A Web based graphical user interface for parallel machine scheduling
Özdeş makine çizelgelemesi için web tabanlı grafiksel kullanıcı arayüzü
M. KORAY ÇANDIR
Yüksek Lisans
İngilizce
1999
İşletmeOrta Doğu Teknik Üniversitesiİşletme Ana Bilim Dalı
YRD. DOÇ. DR. CEMAL AKYOL
- Ç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
Yüksek Lisans
Türkçe
1992
Endüstri ve Endüstri Mühendisliğiİstanbul Teknik ÜniversitesiPROF. DR. RAMAZAN EVREN