Geri Dön

Genetic algorithm approach to parallel machine total tardiness problems

Paralel makina toplam artı gecikme problemine genetik algoritma yaklaşımı

  1. Tez No: 129404
  2. Yazar: FURKAN KIRAÇ
  3. Danışmanlar: DOÇ. DR. ÜMİT BİLGE
  4. Tez Türü: Yüksek Lisans
  5. Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 2002
  8. Dil: İngilizce
  9. Üniversite: Boğaziçi Üniversitesi
  10. Enstitü: Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Sistem ve Kontrol Mühendisliği Ana Bilim Dalı
  12. Bilim Dalı: Belirtilmemiş.
  13. 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

  1. Parallel machine scheduling: An application in apparel industry

    Paralel makine çizelgeleme: Konfeksiyon endüstrisinde bir uygulama

    GÜLCE ÇİNİ

    Yüksek Lisans

    İngilizce

    İngilizce

    2023

    Mühendislik BilimleriYaşar Üniversitesi

    İşletme Mühendisliği Ana Bilim Dalı

    PROF. DR. AYHAN ÖZGÜR TOY

    DOÇ. DR. ÖNDER BULUT

  2. 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

    Türkçe

    2018

    Endüstri ve Endüstri Mühendisliğiİstanbul Teknik Üniversitesi

    Endüstri Mühendisliği Ana Bilim Dalı

    PROF. DR. RAMAZAN EVREN

  3. 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

    Türkçe

    1994

    Elektrik ve Elektronik Mühendisliğiİstanbul Teknik Üniversitesi

    DOÇ.DR. CÜNEYT GÜZELİŞ

  4. 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

    Türkçe

    1997

    Endüstri ve Endüstri Mühendisliğiİstanbul Teknik Üniversitesi

    Endüstri Mühendisliği Ana Bilim Dalı

    DOÇ. DR. M. BÜLENT DURMUŞOĞLU

  5. 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

    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