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.
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.