Regisztráció és bejelentkezés

Órarendtervezés genetikus algoritmus segítségével

Az órarendtervezés öt évtizede intenzíven kutatott problémakör, mivel ismert NP-teljes feladatról van szó [1]. Egy órarend elkészítése során korlátozott erőforrások figyelembevételével kell előállítani egy olyan beosztást (helyszínek, oktatók, csoportok és egyéb erőforrások összerendelését), mely adott feltételeknek felel meg. A probléma nem csak a lehetséges megoldások megtalálásáról szól, de azok között az adott mérőszámok szerinti optimum megkereséséről is.

Dolgozatomban a 2007-es International Timetabling Contest által kiírt feladatot oldottam meg, mely egy valós, egyetemi órarend elkészítésén alapul. A verseny lezárása óta számos, az órarendkészítéssel kapcsolatos kutatás vette kiindulási alapul ezt az adathalmazt és igyekeztek különböző módszerekkel minél jobb megoldásokat adni. A nagyméretű keresési tér miatt én genetikus algoritmus segítségével adtam az optimumhoz konvergáló megoldást. Dolgozatomban bemutatom és mérésekkel alátámasztom, miként lehet egy órarendtervező algoritmust a feladathoz igazítani, és konkrét módszereket ajánlok a konvergencia gyorsítására.

Az elkészült algoritmusom képes a feltételeknek megfelelő órarendet előállítani, majd a megoldásokat iteratívan javítva az optimumhoz konvergáló eredményt adni. Amennyiben a bemeneti és kimeneti formátumok megfelelnek a fenti verseny formátumának, szinte bármely más órarend-készítési feladatra képes lehetséges megoldást adni.

Felhasznált irodalom:

[1] S. Even, A. Itai, A. Shamir, On the complexity of time table and multi-commodity flow problems, 1976.

szerző

  • Hideg Attila
    mérnökinformatikus
    nappali

konzulens

  • Dr. Kővári Bence
    docens, Automatizálási és Alkalmazott Informatikai Tanszék

helyezés

Jutalom