Timetabling Problemi ve Kısıt Memnuniyeti (CSP) Nedir?

Timetabling (çizelgeleme) problemi, sınırlı sayıda zaman dilimi ve kaynağa, birbiriyle çakışmaması gereken etkinlikleri yerleştirme problemidir. Ders programı bunun en bilinen örneğidir ve hesaplama karmaşıklığı açısından NP-zor sınıfına girer: problem büyüdükçe olası çözüm sayısı katlanarak artar ve hepsini tek tek denemek pratik olarak imkânsız hale gelir. Bu yüzden modern çözümler denemeye değil, kısıtlarla elemeye dayanır.

Problemin biçimsel tanımı

Ders çizelgeleme bir kısıt memnuniyeti problemi (Constraint Satisfaction Problem, CSP) olarak ifade edilir. Bir CSP üç bileşenden oluşur:

• Değişkenler (X): yerleştirilecek her ders bir değişkendir.
• Alanlar (D): her değişkenin alabileceği değerler kümesi — burada gün-saat kombinasyonları (ve gerekiyorsa derslik).
• Kısıtlar (C): değişkenlerin birlikte alabileceği değerleri sınırlayan kurallar.

Bir çözüm, tüm değişkenlere alanlarından birer değer atayan ve hiçbir kısıtı ihlal etmeyen bir atamadır.

Ders programı kısıtlarının CSP karşılıkları

Neden NP-zor?

Ders çizelgeleme, bilinen NP-tam problemlerden graf boyamaya indirgenebilir. Bu indirgemeyi görmek problemin doğasını anlatır:

Her dersi bir düğüm olarak düşünün. İki ders aynı öğretmeni, aynı sınıfı veya aynı dersliği paylaşıyorsa aralarına bir kenar çizin. Şimdi soru şu hale gelir: bu grafı, komşu düğümler aynı rengi almayacak şekilde en fazla k renkle boyayabilir miyiz? Renkler zaman dilimleridir.

Graf boyama NP-tam bir problemdir. Ders çizelgeleme onu içerdiği için en az onun kadar zordur — üstelik gerçek okullarda blok ders, kapasite ve tercih gibi ek kısıtlar problemi daha da karmaşıklaştırır.

Arama uzayının büyüklüğü

Somut bir hesap yapalım. Haftada 6 gün, günde 12 ders saati olan bir kurumda 72 zaman dilimi vardır. 700 ders yerleştirilecekse, kısıtları hiç dikkate almadan olası atama sayısı 72⁷⁰⁰'dür.

Bu sayının büyüklüğünü kavramak zordur; evrendeki atom sayısından kat kat fazladır. Saniyede milyar atama deneyen bir bilgisayar bile evrenin yaşından uzun sürede bitiremez.

Buradan çıkan sonuç nettir: çözüm, olasılıkları denemekten geçmez.

Kısıt yayılımı: elemenin mantığı

CSP çözücülerinin temel tekniği kısıt yayılımıdır (constraint propagation). Bir değişkene değer atandığında, bu atamanın etkisi ilişkili tüm değişkenlerin alanlarına anında yansıtılır.

Örnek: 9-A sınıfının matematik dersi pazartesi 1. saate atandı. Bu anda,

• 9-A'nın diğer tüm derslerinin alanından "pazartesi 1. saat" çıkarılır,
• aynı matematik öğretmeninin diğer tüm derslerinin alanından da çıkarılır,
• kullanılan derslik varsa, o dersliği kullanan diğer derslerden de çıkarılır.

Bu eleme zincirleme devam eder. Bir değişkenin alanı tamamen boşalırsa — yani o derse hiçbir saat kalmazsa — o daldaki tüm olasılıklar çözümsüzdür ve hiç denenmeden elenir. Astronomik arama uzayını yönetilebilir kılan şey budur.

Değişken ve değer seçim sezgileri

Çözücünün hangi değişkeni önce ele alacağı performansı doğrudan etkiler. İki klasik sezgi kullanılır:

• En kısıtlı önce (MRV — minimum remaining values): alanı en dar olan değişken önce atanır. Ders programında bu, dar müsaitlikli öğretmenlerin derslerinin önce yerleşmesi demektir. Sezgi şudur: zor olanı sona bırakırsanız, sona geldiğinizde yer kalmaz.
• En az kısıtlayan değer (LCV): seçilen değişkene, diğer değişkenlerin alanını en az daraltan değer atanır. Böylece ileride manevra alanı kalır.

Zorunlu kısıt ve tercih: CSP'den COP'a

Saf CSP "geçerli bir çözüm var mı" sorusunu yanıtlar. Gerçek okullarda ise geçerli çözümlerin çoğu kullanışsızdır: çakışmasızdır ama dersler dağınık, öğretmenler boş bekliyordur.

Bu yüzden pratik sistemler problemi bir kısıtlı optimizasyon problemine (Constraint Optimization Problem, COP) genişletir. Zorunlu kısıtlar ihlal edilemez; tercihler ise bir amaç fonksiyonunda puanlanır:

• Öğretmen başına toplam boş saat (pencere) → azaltılmalı
• Aynı dersin bir güne yığılması → cezalandırılmalı
• Zor derslerin sabah saatlerine gelmesi → ödüllendirilmeli
• Yerleştirilen toplam ders sayısı → artırılmalı

Çözücü, tüm zorunlu kısıtları sağlayan çözümler arasından bu puanı en iyi yapanı arar.

Değişken kurulumunun iki yolu

Çizelgeleme problemini modellerken değişkenlerin nasıl tanımlandığı, çözücünün performansını doğrudan etkiler. İki yaygın kurulum vardır.

Tamsayı kurulumu: her ders bir değişkendir ve değeri atandığı zaman dilimidir. Değişken sayısı azdır (ders sayısı kadar) ve model kompakttır. Hepsi-farklı kısıtları doğrudan ifade edilir.

İkili (boolean) kurulumu: her ders ve zaman dilimi çifti için bir 0/1 değişkeni tanımlanır. Değişken sayısı ders çarpı zaman dilimi kadardır — çok daha fazla. Buna karşılık kapasite ve sayma kısıtları daha kolay yazılır.

Modern CP-SAT çözücüleri genellikle ikisini birlikte kullanır: temel yerleşim tamsayı değişkenlerle, kapasite ve sayma kısıtları ikili değişkenlerle ifade edilir ve aralarında tutarlılık kısıtları kurulur.

Bu seçim akademik bir ayrıntı değildir; kötü kurulmuş bir model, aynı problemi kat kat yavaş çözer.

Katı ve esnek kısıtların sınıflandırılması

Literatürde timetabling problemi için kısıtlar iki gruba ayrılır ve bu ayrım standart terminolojiye sahiptir.

Katı kısıtlar (hard constraints): ihlali çözümü geçersiz kılar. Ders programında bunlar öğretmen müsaitliği, üç çakışma türü, derslik kapasitesi ve blok bütünlüğüdür. Bir çözüm ancak tüm katı kısıtları sağlıyorsa uygulanabilir (feasible) sayılır.

Esnek kısıtlar (soft constraints): ihlali çözümü geçersiz kılmaz, yalnız kalitesini düşürür. Boş saat sayısı, ders yığılması ve pedagojik sıralama bu gruptadır. Her ihlale bir ceza puanı verilir ve toplam ceza en aza indirilmeye çalışılır.

Bu sınıflandırma neden önemli? Çünkü bir kısıtı yanlış gruba koymak sonucu bozar. Örneğin "öğretmenin gün içinde boşluğu olmasın" kuralını katı kısıt yapmak, çoğu okulda problemi çözümsüz hale getirir — oysa esnek kısıt olarak tanımlandığında sistem mümkün olduğunca sağlar ve gerektiğinde ödün verir.

Problemin ölçek göstergeleri

Bir çizelgeleme örneğinin ne kadar zor olduğunu üretimden önce kestirmek mümkündür. Üç gösterge kullanılır:

• Doluluk oranı: toplam ders saati ÷ (sınıf sayısı × zaman dilimi sayısı). 0,85'in üzerindeki değerler problemi belirgin biçimde zorlaştırır.
• Öğretmen esneklik oranı: ortalama müsait saat ÷ ortalama ders yükü. 1,5'in altına düştüğünde dengeli çözüm bulmak zorlaşır.
• Kaynak yoğunluğu: özel derslik gerektiren ders saati ÷ özel derslik kapasitesi. 1'e yaklaştıkça derslik çakışmaları belirleyici hale gelir.

Bu üç oran üretimden önce hesaplandığında, "program neden zor çıkıyor" sorusu deneme-yanılmayla değil ölçümle yanıtlanır.

Çözümsüzlük ve darboğaz analizi

Bazı örnekler gerçekten çözümsüzdür ve bunu ayırt etmek önemlidir. Klasik gösterge güvercin yuvası ilkesidir: belirli bir zaman diliminde ders yapması gereken sınıf sayısı, o dilimde müsait öğretmen sayısından fazlaysa çakışmasız çözüm yoktur.

Bu bir yazılım sınırı değil aritmetik bir gerçektir. Gerçek bir örnekte, 600 ders saatlik bir programda 4 dersin yerleşememesinin sebebi tek bir zaman diliminde 17 sınıfın 15 öğretmene ihtiyaç duymasıydı. İki öğretmenin o saate müsaitlik açması sorunu tamamen çözdü.

İyi bir sistem "çözüm yok" demekle yetinmez; hangi kaynağın darboğaz olduğunu raporlar. Böylece düzeltme programın tamamını kurcalamak yerine hedefli yapılır.