Órarendtervezés korlát-logikai programozás segítségével

OData támogatás
Konzulens:
Dr. Mann Zoltán Ádám
Számítástudományi és Információelméleti Tanszék

Az órarendtervezés feladata egy igen ismert probléma: leggyakrabban oktatási intézményekben találkozhatunk vele, de más területeken is megtalálható. Egy órarend megtervezésének folyamán úgy kell kialakítani az órák beosztását, hogy az minden résztvevőnek megfelelő legyen, vagyis ne kelljen senkinek sem egy időpontban több órán részt vennie.

Egy órarend megtervezése folyamán egyéb követelmények is felmerülhetnek: például ha egy tanárnak egy nap nincs sok órája, akkor ideális esetben ezeket az órákat közvetlenül egymás után tarthatja meg, hogy ne legyen lyukasórája. Bár egy ilyen követelmény betartása nem kötelező, mégis jobb órarendet kapunk, ha betartjuk. Ezeket a követelményeket nevezzük laza korlátoknak, szemben a kemény korlátokkal, amelyeknek a betartása kötelező.

Két évvel ezelőtt az órarendtervezés problémájára egy genetikus algoritmuson alapuló megoldást készítettem, ebben az évben viszont korlát-logikai programozás segítségével oldottam meg a problémát.

Diplomamunkám folyamán a korábbi munkámra adott visszatekintés után egy rövid leírást adok a deklaratív és a logikai programozásról, valamint a Prolog nyelvről. Bemutatom azt a modellt, amelynek segítségével a munkám során dolgoztam, illetve annak a Prolog nyelvű megvalósítását.

Bemutatom a megoldó program megtervezésének lépéseit, a kezdeti, egy problémára specializált megoldástól az általános megoldásig. Ismertetem az implementáció során fellépő problémákat és az azokra adott megoldásokat.

Az elkészült algoritmus a specifikáció alapján képes egy egyszerűbb órarend megtervezésére a megadott korlátok betartásával. Amennyiben laza korlátok is jelen vannak a bemeneti adathalmazban, az algoritmus az órarendet optimalizálni próbálja a megadott korlátokra.

Letölthető fájlok

A témához tartozó fájlokat csak bejelentkezett felhasználók tölthetik le.