A simulated annealing algorithm for the faculty-level university course timetabling problem

Abstract

In this study, faculty-level university course timetabling problem with double major and minor program constraints where classrooms are shared with several faculties is taken into account. This is the first study considering all these constraints together. A goal programming model is proposed to solve the considered problem. Since it is not possible to find a feasible solution for large-size problems with the proposed model in a time limit, a simulated annealing algorithm is developed. The performance of the proposed solution methods is tested by using randomly generated test problems. In addition, a case study is performed at the engineering faculty of a private university. Computational results show the success of the proposed simulated annealing algorithm to solve large-sized problems. An 83% improvement was achieved with the proposed algorithm for the real-life problem.

Bu çalışmada, dersliklerin fakülteler arasında paylaşıldığı, çift anadal ve yan dal kısıtlarının olduğu fakülte seviyesinde üniversite ders çizelgeleme problemi ele alınmıştır. Bu çalışma, tüm bu kısıtları bir arada ele alan ilk çalışmadır. Ele alınan problemi çözmek için bir hedef programlama modeli önerilmiştir. Önerilen model ile büyük boyutlu problemler için süre limiti içinde uygun çözüm bulmak mümkün olmadığından, bir tavlama benzetimi algoritması geliştirilmiştir. Önerilen çözüm yöntemlerinin performansı rassal türetilmiş test problemleri kullanılarak sınanmıştır. Ayrıca özel bir üniversitenin mühendislik fakültesinde vaka çalışması yapılmıştır. Deneysel sonuçlar, önerilen tavlama benzetimi algoritmasının büyük boyutlu problemleri çözmedeki başarısını ortaya koymuştur. Gerçek hayat problemi için önerilen algoritma ile %83 oranında iyileşme sağlanmıştır