Minimizing schedule length on identical parallel machines: An exact algorithm
Başlık çevirisi mevcut değil.
- Tez No: 15110
- Danışmanlar: DOÇ.DR. ÖMER S. BENLİ
- Tez Türü: Doktora
- Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
- Anahtar Kelimeler: Deterministic Machine Scheduling, Identical Parallel Machines, Minimizing Makespan, Computational Complexity Theory, Approximation Algorithms, Optimizing Algorithms, Perfor mance Bounds. 11
- Yıl: 1991
- Dil: İngilizce
- Üniversite: İhsan Doğramacı Bilkent Üniversitesi
- Enstitü: Mühendislik ve Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Belirtilmemiş.
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 123
Özet
Özet ÖZDEŞ PARALEL MAKİNALARDA ÇİZELGE UZUNLUĞUNUN ENAZLANMASI: BİR KESİN ÇÖZÜM ALGORİTMASI H. Cemal Akyel Endüstri Mühendisliği Doktora Tez Yöneticisi: Doç. Dr. Ömer S. Benli Haziran 1991 Tek aşamalı özdeş paralel makinalı çizelgeleme problemlerinin kombinatoryel özelliklerinin incelenmesi ve hesap zamanı açısından uygulanabilir bir dal- sınır yönteminin geliştirilmesi bu çalışmanın ana içeriğini oluşturmaktadır. Çizelgeleme literatüründe bu problemle ilgili pek çok çalışma olmakla beraber, bu çalışmaların çoğu yaklaşık algoritmalar geliştirilmesi ve yaklaşık algoritmaların performans analizi ile ilgilidir. Literatürde önerilen kesin çözüm algoritmaları ise bilgisayar uygulamaları açısından bir takım problemleri içerir. Tek-aşamalı çizelgeleme problemleri için, MV-zot olmalarına rağmen, eniyi çözüm veren, çalışma zamanı açısından uygulanabilir algoritmalara ihtiyaç vardır. Zira böyle bir algoritma çok-aşamalı paralel makinalı çizelgeleme problemlerinin çözümü için gereklidir ki bu son sınıftaki problemler çizelgeleme kuramında hemen hiç dokunulmamış bir alanı belirlerler. Bu çalışmada, tek aşamalı özdeş paralel makinalı çizelgeleme problemleri için bir iiidal-smır algoritması önerilmiştir. Algoritmanın deneysel performans analizinden elde edilen sonuçlar ümit vericidir. Buna ek olarak dal-smır ağacmdaki bir düğümdeki alt ve üst sınırları bulmak için geliştirilen algoritmanın kendi başına uygulanabileceği pratik durumlar da söz konusudur. Bu algoritma eniyi çözüm çarpı 4/3'e istenen ölçüde yakın sonuçlar verebilmektedir. Bu da adı geçen problem için bildiğimiz en iyi sınırdır. Anahtar y. -S Sözcükler: Deterministik Makina Çizelgelemesi, Özdeş Paralel Maki- nalar, Çizelge Uzunluğunun Enazlanması, Hesap Karmaşıklığı Teorisi, Yaklaşık Algoritmalar, Kesin Çözüm Algoritmaları, Performans Sınırları. iv
Özet (Çeviri)
Abstract MINIMIZING SCHEDULE LENGTH ON IDENTICAL PARALLEL MACHINES: AN EXACT ALGORITHM H. Cemal Akyel Ph. D. in Industrial Engineering Supervisor: Assoc. Prof. Dr. Ömer S. Benli June 1991 The primary concern of this study is to investigate the combinatorial aspects of the single-stage identical parallel machine scheduling problem and to develop a computationally feasible branch and bound algorithm for its exact solution. Although there is a substantial amount of literature on this problem, most of the work in this area is on the development and performance analysis of approximation algorithms. The few optimizing algorithms proposed in the literature have major drawbacks from the computer implementation point of view. Even though the single-stage scheduling problem is known to be unary ?/V'P-hard, there is still a need to develop a computationally feasible optimizing algorithm that solves the problem in a reasonable time. Development of such an algorithm is necessary for solving the multi-stage parallel machine scheduling problems which are currently an almost untouched issue in the deterministic scheduling theory.In this study, a branch and bound algorithm for the single-stage identical parallel machine scheduling problem is proposed. Promising results were obtained in the empirical analysis of the performance öf this algorithm. Furthermore, the procedure that is developed to determine tight bounds at a node of the enumeration tree, is an approximation algorithm that solves a special class of identical parallel machine scheduling problems of practical interest. This algorithm delivers a solution that is arbitrarily close to 4/3 times the optimum. To our knowledge this is the best result obtained for this problem so far.
Benzer Tezler
- Deep-learning based optimization framework for wireless powered communication networks
Enerji hasadı yapan kablosuz ağlar için derin öğrenme tabanlı eniyileme
AYSUN GURUR ÖNALAN KÖPRÜ
Doktora
İngilizce
2023
Elektrik ve Elektronik MühendisliğiKoç ÜniversitesiElektrik ve Elektronik Mühendisliği Ana Bilim Dalı
PROF. DR. SİNEM ÇÖLERİ
- Minimum length scheduling in wireless networks with successive interference cancellation
Ardışık enterferans silme özellikli kablosuz ağlarda çizelgenin optimize edilmesi
MEHMET KONTİK
Yüksek Lisans
İngilizce
2014
Bilim ve TeknolojiKoç ÜniversitesiElektrik-Elektronik Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. SİNEM ÇÖLERİ ERGEN
- Dağıtımda stok sistemleri ve hedef programlama uygulaması
Distribution planning
METE KÜÇÜKSOLAK
Yüksek Lisans
Türkçe
1994
Endüstri ve Endüstri Mühendisliğiİstanbul Teknik ÜniversitesiPROF.DR. NAHİT SERASLAN
- Dokuma kumaştan klasik erkek eketi üretiminde gerçekleştirilen optimizasyon çalışmaları
Başlık çevirisi yok
PINAR ÇİFTOK
Yüksek Lisans
Türkçe
1998
Tekstil ve Tekstil Mühendisliğiİstanbul Teknik ÜniversitesiTekstil Mühendisliği Ana Bilim Dalı
PROF. DR. BÜLENT ÖZİPEK
- Demiryolu projelerinde inşaata başlama bölgesinin belirlenmesi için çok kriterli karar verme yaklaşımı: Bir vaka analizi
Multi-criteria decision-making approach for selecting the starting location of construction in railway projects: A case study
SERRA ACAR
Yüksek Lisans
Türkçe
2022
İnşaat Mühendisliğiİstanbul Teknik Üniversitesiİnşaat Mühendisliği Ana Bilim Dalı
DOÇ. DR. ATİLLA DAMCI