İki ölçütlü tek makinalı çizelgeleme problemi için sezgisel bir yaklaşım

A heuristic approach for the secondary criterion scheduling problem on a single machine

Özet

Bu çalışmada, en küçük geciken iş kısıtı altında en büyük erken tamamlanma zamanının en küçüklendiği ikincil ölçütlü bir problem dikkate alınmıştır. Bu problem için geliştirilmiş olan dal-sınır algoritmasında çözüm zamanı, problem büyüklüğüne bağlı olarak üstel artış göstermektedir. Son yıllarda, çizelgeleme problemlerin çözümünde global en iyi çözümü bulmada başarılı olan genetik algoritmalar, tavlama benzetimi, tabu arama ve sinir ağları gibi yeni tekniklerin sıkça kullanıldığı görülmektedir. Bu çalışmada, bu problem için tavlama benzetimi tekniğine dayalı bir algoritma geliştirilmiştir. Geliştirilen algoritmanın performansında çeşitli komşu üretim mekanizmalarının etkileri rassal üretilen test problemleri üzerinde incelenmiştir.

Abstract

In this study, the secondary criteria problem that is minimizing the maximum earliness subject to minimum number of tardy jobs has been considered. The solution time of the branch and bound algorithm which was developed for this problem increases exponentially based on problem size. Recently, some techniques such as simulated annealing, tabu search, genetic algorithms, and neural networks have been used often in finding global solution. In this study, an algorithm was developed based on simulated annealing for this problem. The effectiveness of the developed algorithm was evaluated on randomly generated problems by using various neighborhood search strategies.