Genetik programlama ile öncelik kuralları ve çizelgeleme algoritmalarının keşfi
Discovering priority rules and scheduling algorithms using genetic programming
Yazar: METE ALİKALFA
Danışman: PROF. DR. MUZAFFER KAPANOĞLU
Eskişehir Osmangazi Üniversitesi / Fen Bilimleri Enstitüsü / İstatistik Ana Bilim Dalı
Derece: Doktora, 2013
Konu: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control ; Endüstri ve Endüstri Mühendisliği = Industrial and Industrial Engineering ; İstatistik = Statistics

Özet:
Günümüzün verimlilik odaklı dünyasında çizelgeleme önemli ekonomik fırsatlara sahip kritik bir problemdir.  Diğer yandan, çizelgeleme problemleri birçok optimizasyon probleminin belkemiği olarak değerlendirilebilir.  Bu problemlerin fırsatları ve zorluğu yıllar içinde birçok araştırmacının ilgisini çekmiştir.  Çizelgeleme problemlerinin çeşitliliği ve karmaşıklığı sonucunda birçok çizelgeleme kuralı ve algoritma ortaya çıkmıştır.  Bunların çoğu kabul edilebilir hesaplama sürelerinde yaklaşık sonuçlar bulmakta, bazıları ise optimum çözüm sunmaktadır.
Bu doktora tezinde, çizelgeleme problemlerinin çözümü amacıyla çizelgeleme kuralları ve algoritmalarının otomatik keşfi ile ilgili bir yapı sunulmaktadır.  Bu çalışmanın altında yatan motivasyon, tam otomatik çizelgeleme sistemlerinin olanaklı hale getirilmesidir.  Bu tür sistemlerin hayata geçirilebilmesi endüstriyel sistemlerden lojistik ve servis sistemlerine kadar geniş bir alanda, anında ve önemli bir katkı sağlayabilecektir.  Uzun vadede, çizelgeleme kurallarının ve algoritmaların otomatik keşfi, çizelgelemenin ötesinde herhangi bir problem için algoritmik çözümlerin keşfine olanak sağlayabilecektir. 
Çizelgeleme kurallarının ve algoritmaların otomatik keşfi çoklu ifade genetik programlama tekniği kullanılarak ve öncül alan bilgileri verilmeden gerçekleştirilmiştir.  Geliştirilmiş öğrenme sistemi, çizelgeleme kuralları ve algoritmaları çok basit operatörleri ve problemle ilgili nitelikleri kullanarak sıfırdan keşfetmiştir.  Deneysel sonuçlarımız keşfettiğimiz çizelgeleme kuralları ve algoritmaların literatürdekilerden çok daha iyi olduğunu göstermektedir.  Buna ek olarak, aynı yaklaşımla iyi bilinen iki algoritma da keşfedilmiştir.  Elde ettiğimiz sonuçlar araştırmacıları çizelgeleme problemlerini yeni bir doğrultuda ele almak bakımından cesaretlendirecektir: Problemlerin kendilerini çözmek yerine yeni çizelgeleme kuralları ve algoritmaların keşfinin tercih edilmesi.

Abstract:
In today's productivity-oriented world, scheduling is a critical problem having significant economic opportunities.  On the other hand, scheduling problems can be considered as the backbone of a wide range of combinatorial optimization problems. The opportunities as well as challenges of the scheduling problems have attracted many researchers over years.  The variety and the complexity of scheduling problems have resulted in a list of dispatching rules and algorithms to address the practitioners needs mostly approximate solutions with acceptable computation times and few with optimal solutions.
This dissertation proposes the automated discovery of dispatching rules and algorithms for scheduling problems.   The underlying motive of the study is to enable fully automated scheduling systems with no supervision.   The realization of such systems may seem to have immediate and significant contributions on the applications of the industrial systems to logistics and service systems as well.  In the long-term, the impact of the automated discovery of dispatching rules and algorithms may lead to discover algorithmic solutions solely on computational intelligence for any problem beyond scheduling.
The automated generation of dispatching rules and algorithms have been achieved by using a novel multi-expression genetic programming with no a priori domain knowledge.  The developed multi-expression genetic programming have discovered the dispatching rules and algorithms from scratch by using very simple operators and attributes related to the problem in hand.  Experimental results show that automatically discovered priority rules and scheduling algorithms by our genetic programming framework outperforms the literature.  Moreover, the two well-known algorithms have been discovered by the same approach. We expect the results will encourage researchers towards a new direction in dealing with scheduling problems: Discovering a new dispatching rule or algorithm might be preferred over solving the problem itself.