Genetic algorithm approach to parallel machine total tardiness problems
Paralel makina toplam artı gecikme problemine genetik algoritma yaklaşımı
- Tez No: 129404
- Danışmanlar: DOÇ. DR. ÜMİT BİLGE
- Tez Türü: Yüksek Lisans
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2002
- Dil: İngilizce
- Üniversite: Boğaziçi Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Sistem ve Kontrol Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 82
Özet
ÖZET PARALEL MAKİNA TOPLAM ARTI GECİKME PROBLEMİNE GENETİK ALGORİTMA YAKLAŞIMI Bu tezin konusu olan çalışmada Genetik Algoritmaların (GA) parametre bağımlılıklarını azaltmak için uyarlanımlı bir kontrol mekanizması geliştirilmiştir. Geliştirilen yaklaşım, bir takım bağımsız işin birkaç parallel işlemci üzerinde toplam artı gecikmeyi enküçüklemek amacıyla çizelgelenmesinden oluşan Paralel Makina Toplam Artı Gecikme problemi (PMTAG) üzerine uygulanmıştır. Bu çalışma, PMTAGnin en genel şeklini ele aldığından her iş için sıfırdan farklı ve ayrı termin tarihleri, sisteme giriş zamanlan, işlem zamanlan ve dizine bağlı iş hazırlık zamanlan dahil edilmektedir. NP-Zor yapısı nedeniyle problem, ilginç ve iddialı bir araştırma konusu haline gelmiştir. Bunlara bağlı olarak, bu çalışmanın motivasyonu Genetik Algoritmaların özellik ve yeterliklerini inceleyerek çeşitli uyarlanımlı kontrol mekanizmaları geliştirmek yönünde geleneksel paralel makina çizelgeleme probleminin getirdiği zorluklan aşmaktır. Sağlam bir GA mekanizması geliştirmek için, meta-hüristik yöntemin jenerasyon tipi, başlangıç toplumunun yapısı, ana-baba seçimi, gen kesiştirme ve mutasyon gibi temel öğeleri incelenmiştir. Basit bir Genetik Algoritmanın performansı için kritik olan bir takım parametreler baz alınarak uyarlanımlı kontrol mekanizmalan geliştirilmiştir. Geliştirilen yöntemlerin performans değerlendirmesi, literatürden alınmış ve biri deterministik Tabu Arama, diğeri de Genetik Algoritmalardan oluşan iki ayn çalışma ile ele alınmış birtakım problemler üzerinde yapılmıştır. Bu tezin konusu olan GA yaklaşımı ayrıntılı deneylerle incelenmiştir. Sonuç olarak, geliştirilen uyarlanımlı GA yönteminin literatürde yayınlanan“bilinen en iyi”veya“en iyi”çözümlere göre yüksek kalitede sonuçlar geliştirdiği görülmüştür. Bunun yanısıra, literatürde yayınlanan bazı“bilinen en iyi”sonuçlar daha iyi çözümler bulunarak geliştirilmiştir. Elde edilen geliştirilmiş çözümler, GA açısından oldukça önemli bir basan ve kazanımdır.
Özet (Çeviri)
IV ABSTRACT GENETIC ALGORITHM APPROACH TO PARALLEL MACHINE TOTAL TARDINESS PROBLEM In this thesis, an adaptive control mechanism to reduce the parameter dependence of a Basic Genetic Algorithm (GA) is developed. The approach is implemented over the Parallel Machine Total Tardiness problem (PMTT), which consists of a set of independent jobs to be scheduled on a number of parallel processors to rmnimize total tardiness. As this study considers the generic version of PMTT, distinct ready times, processing times, due dates and sequence dependent setup times for each job are incorporated. The NP-hard nature of the problem renders it a challenging area for research. Hence, the motivation of this study has been to explore the ability of Genetic Algorithms and develop several adaptive control mechanisms to overcome the difficulties superimposed on the traditional parallel machine scheduling problem. In order to develop a robust GA mechanism, the key elements of the metaheuristic such as generation type, initial population structure, parent selection, crossover and mutation are investigated. Based on a Basic Genetic Algorithm, adaptive control mechanisms are implemented, which are structured over some parameters that are found to be critical for the GA performance. The performance evaluation for the strategies developed is done on a set of problems obtained from the literature, where the same problems are addressed in two different studies, one consisting of a GA approach and the other study consisting of a deterministic Tabu Search approach to the problem. The GA approach developed is extensively tested. As a result, it is seen that the adaptive GA approach developed in this study yields good quality results with respect to the optimal'best-known values reported in the literature. Also, some of the best-known results reported in the literature are further improved, which is a notable achievement from the GA point of view.
Benzer Tezler
- Parallel machine scheduling: An application in apparel industry
Paralel makine çizelgeleme: Konfeksiyon endüstrisinde bir uygulama
GÜLCE ÇİNİ
Yüksek Lisans
İngilizce
2023
Mühendislik BilimleriYaşar Üniversitesiİşletme Mühendisliği Ana Bilim Dalı
PROF. DR. AYHAN ÖZGÜR TOY
DOÇ. DR. ÖNDER BULUT
- Yenilenebilir enerji planlaması için bütünleşik çok amaçlı bir karar modeli önerisi
An integrated multi-objective decision model for renewable energy planning
BEYZANUR ÇAYIR ERVURAL
Doktora
Türkçe
2018
Endüstri ve Endüstri Mühendisliğiİstanbul Teknik ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
PROF. DR. RAMAZAN EVREN
- Hücresel yapay sinir ağları için iki öğrenme algoritması ve görüntü işleme uygulamaları
Two learning algorithms for cellular neural networks and their image processing applications
SİNAN KARAMAHMUT
Yüksek Lisans
Türkçe
1994
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiDOÇ.DR. CÜNEYT GÜZELİŞ
- GT yöntemlerinin sınıflandırması, performans ölçütleri, üretimle ilgili verileri kullanan yeni yöntemlere örnekler ve genetik algoritmalar
Taxonomy of GT methods, performance measures,some new GT methods that is able to incorporate pertinent manufacturing data and genetic algorithms
HATİCE DERİCİ
Yüksek Lisans
Türkçe
1997
Endüstri ve Endüstri Mühendisliğiİstanbul Teknik ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DOÇ. DR. M. BÜLENT DURMUŞOĞLU
- 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