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ı, Scheduling, Parallel Machines, Total Weighted Flow Time, Total Tardiness, Branch and Bound Algorithm
- 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ı: 196
Ö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
- Özdeş paralel makineli bir üretim sisteminin karınca koloni algoritması ile çizelgelenmesi
Identical parallel machine scheduling using with ant colony algorithm
BİRGÜL KÜÇÜK
Doktora
Türkçe
2010
Endüstri ve Endüstri Mühendisliğiİstanbul Üniversitesiİşletme Bölümü
DOÇ. DR. NECDET ÖZÇAKAR
- Bulanık ortamda bozulma ve öğrenme etkileri altında çok amaçlı paralel makine çizelgeleme problemleri
Multi objective parallel machine scheduling problems under effects of learning and deterioration in fuzzy environment
OĞUZHAN AHMET ARIK
Doktora
Türkçe
2017
Endüstri ve Endüstri MühendisliğiErciyes ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DOÇ. DR. MEHMET DURAN TOKSARI
- Bulanık çok modlu kaynak kısıtlı proje çizelgeleme problemlerinin çözümü için matematiksel bir model
A mathematical model for the solution of the fuzzy multi mode resource-constrained project scheduling problems
ÖMER ATLI
Doktora
Türkçe
2012
Endüstri ve Endüstri MühendisliğiHava Harp Okulu KomutanlığıEndüstri Mühendisliği Ana Bilim Dalı
PROF. DR. CENGİZ KAHRAMAN
- 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
Mühendislik Bilimleriİstanbul Teknik Üniversitesiİşletme Mühendisliği Ana Bilim Dalı
PROF. DR. SITKI GÖZLÜ
- Paint shop scheduling in a bus plant: Re-entrant hybrid flow shop model with zero buffer and no-wait stations
Otobüs fabrikasında boyahane çizelgelemesi: Sıfır ara depolama ve beklemesiz istasyon; döngülü hibrit akış tipi modeli
EBRU VEYSEL
Yüksek Lisans
İngilizce
2019
Endüstri ve Endüstri MühendisliğiBoğaziçi ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DOÇ. DR. ALİ TAMER ÜNAL