İşlerin bölünerek çizelgelenmesi için geliştirilen genetik algoritma ve uygulama

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.