Dovoľujeme si oznámiť, že dňa
25. 3. 2009 o 11:00
sa bude konať na Fakulte informatiky a informačných technológií STU v Bratislave
v miestnosti D 220 obhajoba dizertačnej práce
Ing. Mariána Lekavého
Názov dizertačnej práce:
Plánovanie a zmena harmonogramu
Odbor: 25-11-900 Aplikovaná informatika
Školiteľ: prof. Ing. Pavol Návrat, PhD., Fakulta informatiky a informačných technológií STU v Bratislave
Oponenti dizertačnej práce:
prof. Ing. Peter Sinčák, PhD., Fakulta elektrotechniky a informatiky TU v Košiciach
prof. Ing. Vladimír Kvasnička, DrSc., Fakulta informatiky a informačných technológií STU v Bratislave
doc. Ing. Ján Paralič, PhD., Fakulta elektrotechniky a informatiky TU v Košiciach
Abstrakt:
Práca obsahuje výsledky v dvoch príbuzných oblastiach. Prvou oblasťou je automatizované plánovanie. Prístupy k doménovo nezávislému automatizovanému plánovaniu je možné rozdeliť do dvoch skupín: plánovanie typu STRIPS (založené na operátoroch) a plánovanie typu HTN (založené na hierarchickej dekompozícii). Všeobecne sa predpokladá, že expresivita plánovania typu STRIPS je nižšia než expresivita plánovania typu HTN. To by znamenalo, že plánovanie typu STRIPS dokáže vyriešiť menej úloh, než plánovanie typu HTN. V tejto práci ukazujeme, že expresivita oboch prístupov je rovnaká a že oba prístupy dokážu vyriešiť všetky problémy riešiteľné Turingovym strojom s konečnou páskou (tzn. riešiteľné bežným počítačom).
Druhá časť práce sa venuje zmene harmonogramu. V prípade, že máme pevne daný a neposunuteľný termín dokončenia harmonogramu, musíme na meškanie aktivít reagovať skrátením zvyšnej časti harmonogramu. V tejto práci ukazujeme, že každé skrátenie harmonogramu zodpovedá rezu grafu alebo superpozícii rezov grafov. Na základe tohto poznatku potom navrhujeme nový algoritmus pre hľadanie najlacnejšej zmeny harmonogramu. Algoritmus je založený na konverzii problému zmeny harmonogramu na problém minimálneho rezu grafu.
This thesis presents results in two areas. The first area is automated planning. Approaches to domain-independent automated planning can be divided into two groups: STRIPS-like planning (based on operators) and HTN-like planning (based on hierarchical decomposition). It is widely believed, that the expressivity of STRIPS-like planning is lower than the expressivity of HTN-like planning. This would mean that HTN-like planning can solve more problems than STRIPS-like planning. In this thesis we show, that the expressivity of both approaches is identical and that both approaches can solve all problems solvable by a finite tape Turing machine (i.e. solvable by a common computer).
The second part of this thesis addresses rescheduling. If we have a schedule with unmovable deadline, we need to react on late activities by shortening of the remaining schedule part. In this thesis, we show that every rescheduling corresponds to a graph cut or the superposition of several graph cuts. Based on this fact, we designed a new algorithm for the cheapest rescheduling. The algorithm is based on the conversion of the rescheduling problem to the problem of minimal graph cut.
Dizertačná práca je k nahliadnutiu na Študijnom oddelení FIIT STU.