OR-Tools ile Ders Programı Oluşturma Mantığı

Öğretmenlik yaptığım yıllarda her eylül ayının kabusunu yakından gördüm: ders programı. Orta ölçekli bir okulda bile deneyimli bir müdür yardımcısının günlerini alan, buna rağmen "Salı 7. saatte iki sınıfım çakışıyor" telefonlarıyla düzeltile düzeltile oturan bir süreç. Bilgisayar mühendisi tarafım bunun çözülmüş bir problem sınıfı olduğunu biliyordu; bu yazıda o çözümün mantığını anlatacağım.

Ders programı neden zor?

Sezgisel olarak basit görünür: dersleri saatlere yerleştir. Ama sayılara bakalım. 20 şubeli, 50 öğretmenli, haftada 40 saatlik bir okulda yerleştirilecek yüzlerce ders bloğu var ve her yerleştirme diğerlerini kısıtlıyor. Bu, klasik bir NP-hard çizelgeleme problemi: kaba kuvvetle çözüm alanını taramak evrenin ömrüne sığmaz, "iyi bir sezgiyle elle yapmak" ise ya çakışma ya da adaletsiz dağılım üretir.

İşin insani boyutu da var: öğretmenin boş günü, ilk/son saat yükü, blok ders tercihi... Bunlar ihlal edilince program "çalışır" ama kimse ondan memnun olmaz.

Hard ve soft constraint ayrımı

Modellemenin ilk adımı, kuralları iki sınıfa ayırmak:

Hard constraint'ler — asla ihlal edilemez:

• Bir öğretmen aynı saatte iki yerde olamaz.
• Bir şube aynı saatte iki ders alamaz.
• Bir derslik aynı saatte iki şubeye tahsis edilemez.
• Dersin haftalık saat toplamı müfredattaki değere eşit olmalı.

Soft constraint'ler — ihlal edilebilir ama cezalandırılır:

• Öğretmenin tercih ettiği boş gün.
• Aynı dersin haftaya dengeli yayılması (matematiğin 6 saatinin tek güne yığılmaması).
• Blok ders tercihleri (laboratuvar dersleri için ardışık iki saat).
• İlk ve son saatlerin öğretmenler arasında adil dağılımı.

Bu ayrım sadece teknik değil, sosyal bir sözleşme: okula "şunlar garantidir, şunlar mümkün olduğunca sağlanır" diyebilmek, sistemin kabul görmesini sağlıyor.

CP-SAT yaklaşımı

Google OR-Tools'un CP-SAT çözücüsü, bu tip kombinatoryal problemler için bugün erişilebilecek en pratik araçlardan biri. Modelin çekirdeği, her (şube, ders, saat) üçlüsü için bir boolean değişken tanımlamak:

from ortools.sat.python import cp_model
 
model = cp_model.CpModel()
 
# x[şube, ders, gün, saat] = 1 ise o ders o saatte işleniyor
x = {}
for s in subeler:
    for d in dersler[s]:
        for g in range(5):
            for h in range(8):
                x[s, d, g, h] = model.new_bool_var(f"x_{s}_{d}_{g}_{h}")
 
# Hard: bir şube aynı saatte en fazla bir ders alır
for s in subeler:
    for g in range(5):
        for h in range(8):
            model.add_at_most_one(x[s, d, g, h] for d in dersler[s])
 
# Hard: bir öğretmen aynı saatte en fazla bir yerde olur
for o in ogretmenler:
    for g in range(5):
        for h in range(8):
            model.add_at_most_one(
                x[s, d, g, h]
                for (s, d) in atamalar[o]
            )
 
# Hard: haftalık saat toplamı müfredata eşit
for s in subeler:
    for d in dersler[s]:
        model.add(
            sum(x[s, d, g, h] for g in range(5) for h in range(8))
            == haftalik_saat[s, d]
        )

Soft constraint'ler ise ceza değişkenleriyle amaç fonksiyonuna girer:

cezalar = []
 
# Soft: öğretmenin tercih ettiği boş gün
for o in ogretmenler:
    if o in bos_gun_tercihi:
        g = bos_gun_tercihi[o]
        calisiyor = model.new_bool_var(f"calisiyor_{o}_{g}")
        model.add_max_equality(
            calisiyor,
            [x[s, d, g, h] for (s, d) in atamalar[o] for h in range(8)],
        )
        cezalar.append(calisiyor * AGIRLIK_BOS_GUN)
 
model.minimize(sum(cezalar))
 
solver = cp_model.CpSolver()
solver.parameters.max_time_in_seconds = 120
status = solver.solve(model)

CP-SAT'ın güzelliği şurada: add_at_most_one, add_max_equality gibi yüksek seviyeli kısıtlar sayesinde model, problemi tarif ettiğiniz dile yakın kalıyor. Çözücü, arama stratejisini kendisi yönetiyor ve 120 saniyelik limit içinde bile "kanıtlanmış optimal olmasa da pratikte mükemmel" çözümler dönüyor.

Gerçek okul verisi: teorinin bittiği yer

Modeli kurmak işin yarısı. Diğer yarısı, gerçek okul verisiyle yüzleşmek:

• Veri hiçbir zaman temiz değil. XLSX'ten gelen öğretmen listesinde aynı kişi üç farklı yazımla bulunur. İçe aktarma katmanındaki doğrulama ve eşleştirme, çözücü kadar emek istiyor.
• Kısıtlar konuşulmadan yazılamaz. "Beden eğitimi salonu aynı anda iki şube alabilir ama törende alamaz" gibi kuralları ancak okulda yaşamış biri sorar. Alan bilgisi burada doğrudan model kalitesi demek.
• Infeasible sonucu bir hata değil, bir teşhis. Model çözümsüz döndüğünde bunun sebebi genellikle gerçek hayatta da çözümsüz bir talep: 30 saatlik dersi 25 saatlik uygunluğa sığdırmaya çalışan bir atama. Sistemin "hangi kısıtlar çelişiyor" diye açıklayabilmesi, kullanıcının güvenini kazanıyor.
• Ağırlıklar birlikte kalibre edilir. Soft constraint ağırlıklarını masa başında belirlemek yerine, okulun ilk çıktılara verdiği tepkiyle ayarlamak çok daha iyi sonuç verdi.

Kapanış

Ders programı problemi, eğitim alan bilgisiyle algoritmik düşüncenin tam kesişiminde duruyor: model ne kadar şık olursa olsun, doğru kısıtları sormayı bilmeden işe yaramıyor; alan bilgisi ne kadar derin olursa olsun, CP-SAT gibi bir çözücü olmadan ölçeklenmiyor.

Benzer bir problem üzerinde çalışıyorsanız — okul, hastane vardiyası, kurs çizelgesi fark etmez — iletişime geçmekten çekinmeyin.