Penalising Patterns in Timetables: Novel Integer Programming Formulations

BURKE, Edmund K., Jakub MAREČEK, Andrew J. PARKES a Hana RUDOVÁ. Penalising Patterns in Timetables: Novel Integer Programming Formulations. In Operations Research Proceedings 2007. Berlin: Springer, 2008, s. 409-414. ISBN 978-3-540-77902-5.

Základní údaje

Originální název

Penalising Patterns in Timetables: Novel Integer Programming Formulations

Název česky

Penalizace vzorů v rozvrzích: Celočíselné formulace

Autoři

BURKE, Edmund K. (826 Velká Británie a Severní Irsko), Jakub MAREČEK (203 Česká republika, garant), Andrew J. PARKES (826 Velká Británie a Severní Irsko) a Hana RUDOVÁ (203 Česká republika)

Vydání

Berlin, Operations Research Proceedings 2007, od s. 409-414, 6 s. 2008

Nakladatel

Springer

---

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Německo

Utajení

není předmětem státního či obchodního tajemství

Odkazy

URL DOI

Kód RIV

RIV/00216224:14330/08:00025638

Organizační jednotka

Fakulta informatiky

ISBN

978-3-540-77902-5

ISSN

UT WoS

000264978100063

Klíčová slova anglicky

integer programming; course timetabling; patterns

Štítky

course timetabling, integer programming, patterns

Příznaky

Mezinárodní význam, Recenzováno

---

Anotace

V originále

Many complex timetabling problems, such as university course timetabling and employee rostering, have an underpinning graph colouring component, a pattern penalisation component and a number of side constraints. In real-life settings, it might be relatively easy to come up with feasible solutions to instances of graph colouring, which correspond to hard constraints such as ``each student attends all events of courses of his choice and no student can be in two rooms at the same time'' even for hundreds of events and hundreds of distinct enrollments. Much more challenging are requirements such as ``students should not have gaps in their individual daily timetables'', which often make the problem over-constrained. On the example of the Udine Course Timetabling Problem, this paper studies several integer programming formulations of such pattern penalising constraints.

Česky

Práce se zabývá formulacemi celočíselného programování pro penalizaci vyskytu vzorů v řešení universitního rozvrhovacího problému.

---

Návaznosti

MSM0021622419, záměr

Název: Vysoce paralelní a distribuované výpočetní systémy Investor: Ministerstvo školství, mládeže a tělovýchovy ČR, Vysoce paralelní a distribuované výpočetní systémy