Informace o projektu
Dynamické aspekty rozvrhování
- Kód projektu
- GA201/07/0205
- Období řešení
- 1/2007 - 12/2009
- Investor / Programový rámec / typ projektu
-
Grantová agentura ČR
- Standardní projekty
- Fakulta / Pracoviště MU
- Fakulta informatiky
- Klíčová slova
- plánování, rozvrhování, omezující podmínky, dynamicita
- Spolupracující organizace
-
Univerzita Karlova
- Odpovědná osoba prof. RNDr. Roman Barták, Ph.D.
Počítačový software pomáhá řešit plánovací a rozvrhovací problémy v řadě oblastí od vesmírného programu (Mars Rovers), přes výpočtově náročné počítačové aplikace (Grid computing), až po klasické výrobní problémy (job-shop a supply chain). Takové systémy typicky pracují ve vysoce dynamickém prostředí, které se vyznačuje změnami zadání řešeného problému vedoucími k zneplatnění nalezeného řešení, a tedy k nutnosti rychle nalézt řešení nového problému. Bohužel existující rozvrhovací technologie neposkytuje takovému dynamickému chování dostatečnou podporu.
Projekt se bude zabývat výše zmíněnými dynamickými aspekty řešení rozvrhovacích problémů. Cílem je navrhnout nové řešící techniky v kontextu splňování omezujících podmínek, které budou pokrývat dynamičnost reálných problémů. Konkrétně se budeme soustředit na inkrementální a otevřené propagační a filtrační techniky typicky integrující klasické metody diskrétní matematiky. Zamýšlíme také studovat možná rozšíření prohledávacích algoritmů pro řešení dynamických problémů, například použitím restartu, nebo metod lokálního prohledávání. V neposlední řadě plánujeme navržené techniky integrovat do podoby aplikovatelné na řešení reálných problémů. Experimentální ověření bude založeno především na reálných datech pocházejících z dalších projektů.
Výsledky
Cílem projektu je navrhnout nové techniky řešení dynamických problémů v kontextu splňování omezujících podmínek. Účelem je poskytnout dosud chybějící podporu dynamicity při řešení reálných rozvrhovacích a plánovacích problémů, a to formou nových propagačních a prohledávacích algoritmů.
Publikace
Počet publikací: 21
2011
-
Complex university course timetabling
Journal of Scheduling, rok: 2011, ročník: 14, vydání: 2, DOI
-
Efficient Grid Scheduling through the Incremental Schedule-based Approach
Computational Intelligence, rok: 2011, ročník: 27, vydání: 1, DOI
-
Event-based Optimization of Schedules for Grid Jobs
Rok: 2011, druh: Účelové publikace
2010
-
A supernodal formulation of vertex colouring with applications in course timetabling
Annals of Operations Research, rok: 2010, ročník: 179, vydání: 1
-
Alea 2 - Job Scheduling Simulator
SIMUTools'10 3rd International Conference on Simulation Tools and Techniques, rok: 2010
-
Decomposition, reformulation, and diving in university course timetabling
Computers & Operations Research, rok: 2010, ročník: 37, vydání: 3
2009
-
Alea 2 - job scheduling simulator
Rok: 2009
-
Complex Real-life Data Sets in Grid Simulations
Rok: 2009, druh: Konferenční abstrakty
-
Interactive Course Timetabling
Rok: 2009, druh: Další prezentace na konferencích
2008
-
A Branch-and-Cut Procedure for the Udine Course Timetabling Problem
Rok: 2008, druh: Další prezentace na konferencích