Öğrenme etkili ve farklı geliş zamanlı tek makineli çizelgelemede toplam ağırlıklı gecikme probleminin çözümü

Abstract

Bu tez çalışmasında ilk defa, öğrenme etkili ve farklı geliş zamanlı tek makineli çizelgeleme problemi ele alınmıştır. Problemde ele alınan amaç fonksiyonu toplam ağırlıklı gecikme minimizasyonudur. Ele alınan problem için matematiksel programlama modeli oluşturulmuş ve küçük boyutlu problemlerde optimal çözümler bulunmuştur. Büyük boyutlu problemleri çözmek için 4 adet sezgisel yöntem kullanılmıştır. Bu sezgiseller; genetik, çözüm kombinasyonlu genetik, kanguru ve genetik-kanguru hibrid algoritmalarıdır. Genetik algoritmanın başlangıç popülasyonunda, 7 farklı sıralama metodundan elde edilen ve rasgele oluşturulan çizelgeler kullanılmıştır. İşlem süresi ve çözüm kalitesi göz önünde bulundurularak popülasyon büyüklüğü 100 ve iterasyon sayısı 2000 nesil olarak belirlenmiştir. Genetik operatörler olarak, iki noktalı çaprazlama ve yer değişimli mutasyon yöntemleri kullanılmıştır. Bir diğer sezgisel olan çözüm kombinasyonlu genetik algoritmada farklı olarak; işlerle pozisyonlar arasındaki ilişkiye göre, popülasyondaki her bir çizelge için amaç fonksiyonu üzerindeki etki belirlenmiştir. Devamında her iş için en verimli pozisyon belirlenerek yeni bir çizelge elde edilmiştir. Kanguru algoritmasında, iki işin yer değişimiyle gerçekleşen yürüyüş ve belirli bir kurala göre birden fazla yer değişimi yapan zıplama fonksiyonları kullanılmıştır. Başlangıç çözümü olarak, genetik algortimada olduğu gibi 7 farklı sıralama metodu arasından en iyi sonuç kullanılmıştır. İşlem süresi ve çözüm kalitesi göz önünde bulundurularak yürüyüş 100, zıplama 50 ve toplam iterasyon sayısı 300 olarak belirlenmiştir. Son olarak genetik-kanguru hibrid algoritmada, ilk genetik algoritma çalıştırılmıştır. Devamında, genetik algoritmadan elde edilen en iyi sonuç kanguru algoritmasında başlangıç çözümü olarak kullanılmıştır. Hibrid yöntemde, genetik ve kanguru algoritmalarındaki parametreler kullanılmıştır. Sadece kanguru algoritmasının toplam iterasyon sayısı 150 olarak değiştirilmiştir. 1000 iş boyutundaki problemleri de kapsayan 8640 adet soru oluşturulmuş ve geliştirilen yöntemler birbiriyle karşılaştırılarak çözüm sonuçları sunulmuştur.

In this thesis, single machine scheduling problem with learning effect and unequal release dates is studied for the first time. Objective function of the studied problem is minimization of total weighted tardiness. Mathematical programming model is developed for the studied problem and optimal solutions are obtained for small size problems. For large size problems, 4 heuristic methods are developed. These heuristics are; genetic, genetic with solution combination, kangaroo and genetic-kangaroo hybrid algorithms. Schedules generated by 7 different dispatching rules and schedules generated randomly are used in initial population of genetic algorithm. Population size and number of generation are determined 100 and 2000 respectively, considering running time and solution quality. Two points crossover and swapping mutation are used for genetic operators. Differently in another heuristic that genetic algorithm with solution combination, according to relationship between jobs and sequences, impact on objective function is determined for each schelude in population. Then a new schedule is generated by determining the most efficient position for each job. In kangaroo algorithm, walk and jump functions are used which respectively occured by swapping once and occured by swapping many times according to a definite rule. As well as the genetic algorithm, the best result from 7 different dispatching rules is used in the form of initial solution. Walk, jump and iteration numbers are determined 100, 50 and 300 respectively, considering running time and solution quality. In the last heuristic that genetic-kangaroo hybrid algorithm, genetic algorithm is first run. Subsequently, the best result obtained by genetic algorithm is used as initial solution in kangaroo algorithm. In hybrid algorithm, genetic and kangaroo algorithms parameters are used. Only, the iteration number of kangaroo algorithm is changed to 150. 8640 problems including the size of 1000 jobs are generated and solutions are presented in conjunction with comparing developed methods to each other.