Yazan : Şadi Evren ŞEKER

Klasik bir optimizasyon problemidir. Basitçe belirli bir süreye, en verimli şekilde belirli kurallara uyarak olayları yerleştirmeyi hedefler. Örneğin öğrencilerin haftalık programının yapılması, doktor / hemşirelerin nöbet çizelgeleri, televizyon kanallarının yayın akışları gibi.

Daha basit anlaşılacağı için öğrenci programlarını örnek vererek konuyu açıklamaya çalışayım. Bir öğrenci probleminde, sistemin uyması istenen kıstaslar(constraints) şunlar olabilir: Örneğin öğrencilerin haftada 7 adet ders almaları gerekiyor. Bu dersler 3’er saat olsun ve her ders 2+1 şeklinde bölünecek olsun. Yani 3 saat üst üste olmayacak 2 saat farklı bir günde 1 saat farklı bir günde olacak. Dersi veren hocalardan 1. Dersi veren hoca, pazartesileri gelemiyor olsun. 3. Dersi veren hoca aynı zamanda farklı bir sınıfın farklı bir dersini veriyor olsun. …

Yukarıda bu saydıklarımız klasik bir öğrenci programı hazırlanması sırasında yaşanan problemlerden sadece bazılarıdır. Bilgisayar mühendisliği, bu problem için çözüm geliştiren programların yazılması ile ilgilenir ve bu problem, tanımı itibariyle NP-Complete sınıfında kabul edilebilir. Yani problemin çözülmesi polinom olmayan bir zamanda üstsel olarak artan hesaplama gerektirir. Örneğin n adet kıstasın olduğu (constraint) bir sisteme yeni bir kıstas girildiğinde, sistemin daha önceki n kıstas ile bu yeni girilen kıstasın uyumunu kontrol etmesin ve çakıştırmamaya çalışması gerekir. Görüldüğü üzere her yeni kıstas kendinden öncekilerin çarpımı kadar, yani basit bir hesaplama ile n! kontrol gerektirir.

Zaman çizelgeleme problemlerinin çözümü için çeşitli seviyelerde yöntemler geliştirilmiştir. Bunlardan ilki, problemin modellenmesidir. Problem modellemesi için kullanılan yöntemlerden birisi de TTML (time tabling markup language) kullanımıdır.

Problem çözümü için kıstas programlama (constraint programming) yaklaşımları kullanılabilir.

Ayrıca problemin verimli bir çözümü olup olmadığı veya hangi yöntemin kullanılması gerektiği bilinmediği durumlarda, genetik programlama yaklaşımları olumlu sonuçlar verebilmektedir. Bu yüzden literatürde, zaman çizelgeleme problemlerinin genetik algoritmalar ile çözümüne de rastlanmaktadır.

Bir Cevap Yazın

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir


6 − bir =