Genetik algoritmalarla öncelik kısıtları altında paralel makine çizelgeleme

Abstract

Anahtar Kelimeler: Paralel Makine Çizelgeleme, Toplam Gecikme ve erken bitme maliyeti, Genetik Algoritma, Performans Kriterleri. Çoklu makine çizelgeleme teorisinin ana konusu, işlere göre makinelerin mükemmel ya da mükemmele yalan eşlemesini sağlama ve bunun yanında bazı emri verilmiş amaçları yapabilmek için her bir makine üzerindeki iş sıralama sürecine karar vermedir. Bu çalışma ile amaçlanan büyük örnek kümeleri ve öncelik kısıtlan altında, genetik algoritma yöntemlerinden faydalanarak, daha düşük tamamlanma süresi ve maliyet değerlerine ulaşmaktır. Bu amaçlada bir yazılım geliştirilmiştir. Bu yazılım sayesinde SPT, LPT ve EDD öncelik kısıtlan ile bulunan çözümler ile genetik operatörlerle (çaprazlama ve mutasyon) bulunan çözümler kolaylık elde edilmektedir. Paralel makine sistemlerinde genellikle 2 makineli çözüm üzerinde durulurken hazırlanan yazılım sayesinde 2, 3, 4 ve 5 makineli sistemler üzerinde sonuçlar araştırılmıştır. Toplamda 100 olmak üzere her bir makine sistemi için 25 'er örnek çözümlenmiştir. Literatürde SPT, LPT ve EDD öncelik kısıtlan altında en uygun çözümler elde edilmektedir. Bu çalışmada genetik algoritmalarda kullanılan iki genetik operatör olan çaprazlama ve mutasyon işlemleri gerçekleştirilmiştir. Elde edilen sonuçlar geleneksel metotlarla elde edilen sonuçlar ile karşılaştırılmıştır. Çalışmanın sonuçlan genetik operatörler ile elde edilen sonuçların diğer algoritmalardan daha iyi sonuçlar elde ettiğini göstermektedir. IX

PARALLEL MACHINE SCHEDULING USING GENETIC ALGORITHM UNDER PRIORITY RESTRICTIONS SUMMARY Key words: Parallel Machine Scheduling, Total Tardiness / Earliness Costs, Genetic Algorithm, Performance Criteria. Main subject of multi machine scheduling is to obtain the perfect matching of the work and the machine and to decide the priority in the work order process on each machine to maintain the commanded targets. The objective of this study is to attain shorter complement periods and costs, under major sample clusters and priority restrictions, by using genetic algorithm methods. With this purpose a software has been developed. By the help of this software, solutions achieved by SPT, LPT and EDD priority constraints could easily be achieved using genetic operators (crossover, mutation etc.). In parallel machine systems usually solutions are based on two machine structures. However the developed software give opportunity to research on 2, 3, 4 and 5 machine system results. Being totally 100 examples, 25 examples for each machine has been analyzed. In the literature, by SPT, LPT and EDD precedence rules best suitable solutions are being achieved. In this study two genetic operators called crossover and mutation processes are carried out. The results are compared with the results obtained by traditional methods. Conclusion of this study shows that the results achieved by using genetic algorithms are much better than results achieved by other various methods.