Studentské projekty

Aktuální neobsazené a řešené projekty

Minulé projekty

Diplomová práce: Rozvrhování zdravotních sester v nemocnici

Zadání: Přiřazení zdravotních sester na směny představuje složitý problém z oblasti rozvrhování zaměstnanců. Cílem práce je studium existujících metod pro řešení tohoto problému, výběr vhodných modelů a algoritmů pro jeho řešení a následovně jejich implementaci. Implementované algoritmy budou experimentálně ověřeny z pohledu kvality dosaženého řešení i časové efektivity.

Řešení problému by mělo být navrženo tak, aby umožňovalo řešit reálný problém rozvrhování zdravotních sester v nemocnici. Vzhledem k malému rozsahu tohoto problému by navržené modely a algoritmy měly být aplikovatelné i na vybraných problémech z archivu Personnel Scheduling Data Sets and Benchmarks na University of Nottingham.

• Search methodologies :introductory tutorials in optimization and decision support techniques. Edited by Edmund Burke - Graham Kendall. New York : Springer, 2005.
• Burke, Edmund K. - de Causmaecker, Patrick - Vanden Berghe, Greet - Van Landeghem, Hendrik. The State of the Art of Nurse Rostering. Journal of Scheduling, 7, 6, od s. 441-499. 2004.

Student: Šimon Tóth
Web: kopie CD přiložené k práci

Diplomová práce: Plánování úloh v paralelním a distribuovaném prostředí

Zadání: Gridy, tedy rozsáhlé distribuované systémy výpočetních, datových a informačních zdrojů spojených vysokorychlostní počítačovou sítí, se snaží vytvořit iluzi jednotného virtuálního systému. Součástí této iluze je i odpovídající systém plánování úloh a zdrojů tak, aby byl uživatel oddělen od výběru konkrétních zdrojů a přitom byl celý distribuovaný systém efektivně využíván.

Práce se zabývá problematikou plánování úloh a zdrojů na Gridech. Prvotním cílem práce je prostudovat simulační nástroj GridSim umožňující modelování a simulaci úloh i zdrojů a návrh a evaluaci plánovacích algoritmů. Tento nástroj bude použit k vytvoření modelu Gridu s jeho zdroji i dynamicky přibývajícími úlohami. Hlavním cílem práce je studium a návrh algoritmů pro plánování úloh v paralelním a distribuovaném prostředí. Základní i pokročilejší plánovací algoritmy pro řešení statických i dynamických problémů budou implementovány a experimentálně ověřeny prostřednictvím GridSimu. Práce se bude zabývat i možnostmi použití a rozšíření algoritmů z oblasti programování z omezujícími podmínkami pro problémy plánování úloh na Gridech.

Literatura:

• Dechter, Rina. Constraint processing. San Francisco : Morgan Kaufmann Publishers, 2003.
• Miguel, Ian. Dynamic Flexible Constraint Satisfaction and its Application to AI Planning. : Springer, 2004. Distinquished Dissertations.
• Pinedo, Michael. Planning and Scheduling in Manufacturing and Services. : Springer, 2005. Springer Series in Operations Research.
• Foster, Ian - Kesselman, Carl. The grid : blueprint of a new computing infrastructure [2nd ed.]. 2nd ed. Amsterdam : Morgan Kaufmann, 2004.

Student: Dalibor Klusáček, URL projektu
Web: kopie CD přiložené k práci

Bakalářská práce: Porovnání systémů pro programování s omezujícími podmínkami

Zadání: Cílem práce je porovnání různých přístupů a systémů pro programování s omezujícími podmínkami. Čistě deklarativní přístup logického programování s omezujícími podmínkami v SICStus Prologu je protikladem k systému ILOG, knihovně pro omezující podmínky v C++. Gecode/J představuje Java rozhraní k Gecode C++ knihovně s omezujícími podmínkami a jako reprezentant řady nově vznikajících systému vyniká podporou pro výuku programování s omezujícími podmínkami.

V rámci bakalářské práce implementujte sadu příkladů, porovnejte styl programování při práci s omezujícími podmínkami v SICStus Prologu, ILOGu a Gecode/J a diskutujte možnosti použití jednotlivých knihoven.

Student: Miroslava Plachá
Materiály: viz IS MU

Bakalářská práce: Rozvrhování pomocí logického programování s omezujícími podmínkami

Zadání: Cílem práce je studium možností logického programování s omezujícími podmínkami pro řešení problémů z oblasti rozvrhování. Porovnejte možnosti řešičů omezujících podmínek nad konečnými doménami, řešičů umožňující detekci nesplněných omezení a možnosti hybridního řešiče. Zaměřte se na klasické i dynamické problémy rozvrhování úloh s disjunktivními a kumulativními zdroji. Při implementaci použijte knihovny systému ECLiPSe. V rámci projektu navrhněte a implementujte sadu rozvrhovacích problémů, srovnejte efektivitu a možnosti řešení problémů jednotlivými knihovnami.

Literatura:

• Dechter, Rina. Constraint processing. San Francisco : Morgan Kaufmann Publishers, 2003.
• Baptiste, Philippe - Le Pape, Claude - Nuijten, Wim. Constraint-based scheduling : applying constraint programming to scheduling problems. Boston : Kluwer Academic Publishers, 2001. International series in operations research & management science.
• Miguel, Ian. Dynamic Flexible Constraint Satisfaction and its Application to AI Planning. : Springer, 2004. Distinquished Dissertations.
• Cheadle, Andrew M. - Eremin, Andrew - Harvey, Warwick - Sadler, Andrew J. - Schimpf, Joachim - Shen, Kish - Wallace, Mark G. ECLiPSe: An Introduction. : IC-Parc, Imperial College London, 2005. IC-Parc-05-1.

Student: Martin Šmérek
Materiály: URL projektu, kopie CD přiložené k práci, prezentace na obhajobe (pdf)

Diplomová práce: Měkké podmínky při rozvrhování

Zadání: Práce se zabývá oblastí měkkých (soft) omezujících podmínek a optimalizací jejich splnění. Měkké podmínky budou použity při řešení reálných problémů z oblasti universitního rozvrhování. Prvotním úkolem je zpracování jednotného přehledu algoritmů používaných při řešení obecného systému měkkých omezení. Další úkol představuje studium specifických globálních měkkých podmínek, klusacek lze využít v rozvrhování, a následovné zpracování přehledu existujících algoritmů. Na základě těchto znalostí budou navržena inferenční pravidla a propagační algoritmy pro vybraná měkká omezení z oblasti rozvrhování. Při kombinaci optimalizačních kritérii pro jednotlivé třídy měkkých omezení bude využito přístupů z oblasti multikriteriálních optimalizací používaných při rozvrhování. Implementace algoritmů bude realizována v rozvrhovacím systému pro řešení problémů rozvrhování na Purdue University, USA. Součástí práce je experimentální vyhodnocení navržených algoritmů a srovnání s obdobnými algoritmy.

Literatura:

• Rina Dechter. Constraint processing. San Francisco : Morgan Kaufmann Publishers, 2003.
• Stefano Bistarelli, Helene Fargier, Ugo Montanari, Francesca Rossi, Thomas Schiex and Gerard Verfaillie, Semiring-based CSPs and Valued CSPs: Basic Properties and Comparison. Over-Constrained Systems, Springer-Verlag LNCS 1106, 1996.
• Javier Larrosa, Tomas Schiex, Solving weighted CSP by maintaining arc consistency. Artificial Intelligence, 159, 1-2, strany 1-26. 2004.
• Schaerf: A Survey of Automated Timetabling. CWI Report, 1996.
• Hana Rudová, Keith Murray, University Course Timetabling with Soft Constraints. Theory and Practice of Automated Timetabling, Springer-Verlag LNCS 2740, 2003.

Student: Miroslav Vlk
Web: kopie CD přiložené k práci

Diplomová práce: Algoritmy pro řešení problémů s omezujícími podmínkami

Zadání: Práce se zabývá oblastí problémů s omezujícími podmínkami a jejich aplikacemi v oblasti rozvrhování. Cílem práce je studium a návrh rozšíření prohledávacích algoritmů pro obtížně řešitelné problémy s omezujícími podmínkami, které mohou být potencionálně příliš podmíněné. Funkčnost navržených algoritmů ověřte experimentálně pro řešení reálného problému univerzitního rozvrhu a vhodně navržených náhodných problémů.

Literatura:

• Hooker: Logic-Based Methods for Optimization: Combining Optimization and Constraint Satisfaction. John Wiley and Sons, 2000.
• Michalewicz, Fogel: How to Solve It: Modern Heuristics. Springer-Verlag, 1999.
• Marriot, Stuckey: Programming with Constraints: An Introduction. MIT Press, 1998.
• Pinedo: Scheduling : theory, algorithms and systems. Prentice Hall, 1995.

Zadání: Vytvořte systém pro plnění, údržbu a prohledávání internetového archivu obsahující například databáze lidí, publikací, konferencí nebo aplikačního softwaru. Součástí systému musí být i návrh a implementace WWW rozhraní s jeho bezpečnostním mechanismem pro přidávání a změnu položek databází libovolným uživatelem internetu. Cílem tohoto projektu je jeho následovné využití pro shromažďování informací v oblasti programování s omezujícími podmínkami (constraint programming). Po dohodě možné i v rámci výpočetní techniky.
Příklad neinteraktivních archivů: Constraints Archive, Digital Library of PDPLab
Příklad neinteraktivní databáze publikací umožňující prohledávání: WATT Bibliography

Kód projektu: I995 (1 semestr-Inf)
Student: Roman Čech
Text práce: PostScript

Bakalářský projekt: WWW rozhraní a databáze požadavků učitelů na rozvrh

Zadání: Vytvořte interaktivní WWW rozhraní, které umožní učiteli zadávat požadavky na dobu výuky jeho jednotlivých předmětů. Učitel může specifikovat své požadavky na základě výběru typu požadavku z databáze požadavků a volbou konkrétních dat pro daný typ požadavku prostřednictvím WWW.

Kód projektu: P999 (2 semestry-VT)
Student: Jana Janečková
Text práce: PDF