Examination timetabling problem

Sınav zaman çizelgeleme problemi birçok eğitim kurumu tarafından büyük bir sorundur. İlgilenilen problem NP-zor olduğu için ve gerçek problemlerin eniyilenmesi zor olduğu için, birçok akademik çalışma bu problemin çözümü için bulgusal yöntemler kullanmaktadır. Adil bir sınav takviminin önemi sınav zaman çizelgeme problemi için kesin çözümleri gerekli kılmaktadır. Bu çalışmada, bu problem için kesin çözüm yöntemleri araştırılmış ve bu yöntemlerin yeterliği literatürdeki problemler ve Bilkent Üniversitesi problemi üzerinde denenmiştir. Tez kapsamında, p-merkez ortanca aktarma merkezi ve ikinci dereceden atama problemleri kaynaklarındaki formulasyonlar sınav zaman çizelgeleme problemine uyarlanmıştır ve bu formulasyonlara farklı Bender's ayrıştırma metodu ve dal ve kesme metotları uygulanmıştır. Az sayıda zaman aralığı içeren problemler için öğrencilerin potansiyel takvimlerini kullanan yeni bir formulasyon tanımlanmıştır. Büyük ölçekli problemlerde uygulanmak için alt sınır hesaplama metotları ve önerilen formulasyonlara dayalı bulgusal yaklaşımlar önerilmiştir. Çalışmanın sonucunda çözülemeyen problemler için etkili alt sınırlar bulunmuş ve küçük boyutlu problemler kısa zamanda kesin olarak çözülebilmiştir.