Ders programı neden zor bir problemdir? CP-SAT ile hard/soft constraint modelleme, öğretmen-şube-derslik kısıtları ve gerçek okul verisinin öğrettikleri.
Yayınlayan: FutureGo Studio
Öğ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.
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.
Modellemenin ilk adımı, kuralları iki sınıfa ayırmak:
Hard constraint'ler — asla ihlal edilemez:
Soft constraint'ler — ihlal edilebilir ama cezalandırılır:
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.
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.
Modeli kurmak işin yarısı. Diğer yarısı, gerçek okul verisiyle yüzleşmek:
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.