Please use this identifier to cite or link to this item: http://hdl.handle.net/11452/5306
Title: İşlerin bölünerek çizelgelenmesi için geliştirilen genetik algoritma ve uygulama
Other Titles: Genetic algorithm for batch splitting & scheduling and application
Authors: Özmutlu, H. Cenk
Eroğlu, Duygu Yılmaz
Uludağ Üniversitesi/Fen Bilimleri Enstitüsü/Endüstri Mühendisliği Anabilim Dalı.
Keywords: İlişkisiz paralel makine çizelgeleme
İş bölme
İşin tamamlanma zamanı
Makine ve sıra bağımlı hazırlık süresi
Karışık tam sayılı programlama
Melez genetik algoritmalar
Büyük boyutlu problemler
Unrelated parallel machine scheduling
Job splitting
Makespan
Machine and sequence-dependent setup times
Mixed integer program
Hybrid genetic algorithms
Large scale problems
Issue Date: 16-Oct-2014
Publisher: Uludağ Üniversitesi
Citation: Eroğlu, D. Y. (2014). İşlerin bölünerek çizelgelenmesi için geliştirilen genetik algoritma ve uygulama. Yayınlanmamış doktora tezi. Uludağ Üniversitesi Fen Bilimleri Enstitüsü.
Abstract: Bu tez çalışmasında, bölünebilir ve aynı zamanda iş sırası ve makine bağımlı hazırlık süreli (Sijk) işler içeren, ilişkisiz paralel makine (Rm) çizelgeleme probleminde, işin tamamlanma zamanının (Cmax) en küçüklenmesi hedeflenerek, karışık tam sayılı modeller (MIP) ve genetik algoritmalar geliştirilmiştir. Tez çalışmasının literatüre ilk katkısı, iş bölme ve çizelgelemenin eş zamanlı yapıldığı, değişken alt iş sayıları içeren yeni algoritmalar tanıtması olmuştur. Bilindiği kadarıyla, işlerin bölünebildiği Rm/Sijk/Cmax problemi için, literatürde herhangi bir veri kümesi bulunmamaktadır. Önerilen algoritmanın doğrulanabilmesi amacıyla, Rm/Sijk/Cmax problemi için, literatürdeki veri kümesi dikkate alınmış ve önerilen algoritma, işlerin bölünmediği duruma indirgenmiştir. Daha rekabetçi sonuçlar elde edebilmek için ise, genetik algoritmaya yerel arama tekniği de dâhil edilmiş ve GALA geliştirilmiştir. Yerel arama sonuçlarını genetik algoritmaya adapte edebilen algoritmalar geliştirilmiştir ve bu da tez çalışmasının literatüre ikinci katkısıdır. Yeni melez yapıya dayanarak, işlerin bölünebildiği Rm/Sijk/Cmax problemi için geliştirilen algoritma tekrar tasarlanmış ve GAspLA ortaya çıkmıştır. Geliştirilen üç adet yeni MIP modeli, bölme çizelgeleme kararını eş zamanlı vermektedir ve tez çalışmasının literatüre üçüncü katkısıdır. GAspLA sonuçlarının, MIP modelini başlangıç çözüm kümesi ile beslediği GAspLAMIP uygulaması ise tez çalışmasının literatüre dördüncü katkısıdır. Çalışmanın, literatüre beşinci katkısı, tekstil endüstrisinde, gerçek çizelgeleme problemini de çözümleyebilmesidir. Bu aşamada, makine uygunluk kısıtı da eklenmiş, büyük boyutlu problemler için GAspLA_LSP geliştirilmiştir.
This thesis develops mixed integer programming models (MIP) and genetic algorithms for the scheduling problem of unrelated parallel machines (Rm) with job sequence- and machine-dependent setup times (Sijk) and job splitting properties to reduce makespan (Cmax). The first contribution of this thesis is to introduce novel algorithms which make splitting and scheduling simultaneously with a variable number of sub jobs. There is no dataset for the problem of Rm/Sijk/Cmax with job splitting in the literature according to our knowledge. To verify the proposed algorithm, datasets from the literature for the problem of Rm/Sijk/Cmax is considered and the proposed algorithm is demoted to the without job splitting property. To get more competitive results, a local search technique is implemented into the genetic algorithm and GALA is developed. Algorithms that satisfy the adaptation of local search results into genetic algorithms are developed and this is the second contribution of the thesis. According to the new hybrid structure, the algorithm for the problem of Rm/Sijk/Cmax with splitting is redesigned and the algorithm GAspLA is constituted. As the third contribution of this thesis, three new MIP models that simultaneously make splitting and scheduling decisions are developed. The fourth contribution of this thesis is the implementation of the GAspLAMIP, in which the result of the GAspLA feeds MIP formulation with initial solution set. The fifth contribution of this research is solving the real scheduling problem of the textile industry. In this step, machine eligibility constraint is enclosed and GAspLA_LSP is developed for large scale problems.
URI: http://hdl.handle.net/11452/5306
Appears in Collections:Doktora Tezleri / PhD Dissertations

Files in This Item:
File Description SizeFormat 
382261.pdf5.19 MBAdobe PDFThumbnail
View/Open


This item is licensed under a Creative Commons License Creative Commons