Diplomová práce

Univerzitní rozvrhování pomocí celočíselného programování

Course timetabling with integer programming

Bc. Jakub Mareček, učo 98770
Anotace

Tato práce se zabývá optimalizací v rozvrhování, zejména technikou celočíselného lineárního programování a problémem z univerzity v italském Udine. Je popsáno několik obecněji použitelných výsledků: -- transformace problému barvení grafu na problém multibarvení grafu pomocí jistého rozkladu grafu na kliky, včetně algoritmu pro nalezení tohoto rozkladu v polynomiálním čase -- technika odvozování nových …více

Abstract

This thesis is concerned with optimisation problems in timetabling, in general, and the use of Integer Programming in Udine Course Timetabling Problem, in particular. First, a number of results of independent interests are described: -- a transformation of (Bounded) Graph Colouring to (Bounded) Graph Multicolouring via a particular clique partition obtainable in polynomial time -- a technique for deriving …více

Klíčová slova
mathematical programming integer programming combinatorial optimisation polyhedron graph colouring timetabling university course timetabling ILOG CPLEX Concert IBM optimalizace matematické programování celočíselné programování kombinatorická optimalizace barvení grafu grafový algoritmus polyedr graf rozvrhování univerzitní rozvrhování
Zadání práce
Problém univerzitního rozvrhování lze formulovat a řešit prostřednictvím barvení grafu jako bounded colouring, resp. pre-colouring extension s omezením na počet použití jedné barvy. Cílem práce je na příkladu rozvrhovacího problému z univerzity v Udine používaného v soutěži International Timetabling Competition 2007 prozkoumat možnosti využití:
  • reformulací problému
  • řezných rovin specifických pro daný problém a
  • heuristik pro hledání horních a dolních mezí
v řešičích založených na celočíselném programování. Výstupem diplomové práce bude teoretická analýza i implementace řešiče využívající ILOG CPLEX nebo ZIB SCIP.
Administrativní informace
Práce zkontrolována:
26. 5. 2009 12:28, doc. Mgr. Hana Rudová, Ph.D., učo 3840
Plný text práce
1,9 MB / soubor PDF
Jazyk práce
angličtina angličtina
Termín obhajoby
3. 7. 2009
Práce byla úspěšně obhájena

Vedoucí

doc. Mgr. Hana Rudová, Ph.D., učo 3840
KSUZD FI MU

Oponent

prof. RNDr. Petr Hliněný, Ph.D., učo 168881
KTP FI MU

Literatura

  • NEMHAUSER, George L. Integer and combinatorial optimization. Edited by Laurence A. Wolsey. New York: John Wiley & Sons, 1999, xiv, 763. ISBN 0471359432.
  • DI GASPERO, Luca a Andrea SCHAERF. Neighborhood Portfolio Approach for Local Search Applied to Timetabling Problems. Journal of Mathematical Modelling and Algorithms. 2006, roč. 5, č. 1, s. 65-89. ISSN 1570-1166.
Citovat tuto práci
Masarykova univerzita Fakulta informatiky
Studijní program
Aplikovaná informatika
Obor

Práce na příbuzné téma

Seznam prací, které mají shodná klíčová slova.

Podobné práce

  • Přidání souboru

    Soubor nebo složku lze nahrát pomocí tlačítka Přidat.

  • Další operace se soubory

    Podrobnosti lze zjistit označením příslušného řádku.

  • Pohled pro experty

    Pro častou práci je možné zvolit režim Více možností.

  • Vyhledávání souborů

    Vyhledávaný výraz můžete zadat přímo do adresního řádku.

  • Rychlý přístup k souborům

    Pomocí funkce Nedávné je možné se rychle vrátit k právě prohlíženým souborům. Oblíbené soubory je také možné označit Hvězdičkou.