Penalising Patterns in Timetables: Novel Integer Programming Formulations

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

Basic information

Original name

Penalising Patterns in Timetables: Novel Integer Programming Formulations

Name in Czech

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

Authors

BURKE, Edmund K. (826 United Kingdom of Great Britain and Northern Ireland), Jakub MAREČEK (203 Czech Republic, guarantor), Andrew J. PARKES (826 United Kingdom of Great Britain and Northern Ireland) and Hana RUDOVÁ (203 Czech Republic)

Edition

Berlin, Operations Research Proceedings 2007, p. 409-414, 6 pp. 2008

Publisher

Springer

---

Other information

Language

English

Type of outcome

Stať ve sborníku

Field of Study

10201 Computer sciences, information science, bioinformatics

Country of publisher

Germany

Confidentiality degree

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

References:

URL DOI

RIV identification code

RIV/00216224:14330/08:00025638

Organization unit

Faculty of Informatics

ISBN

978-3-540-77902-5

ISSN

UT WoS

000264978100063

Keywords in English

integer programming; course timetabling; patterns

Tags

course timetabling, integer programming, patterns

Tags

International impact, Reviewed

---

Abstract

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.

In Czech

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

---

Links

MSM0021622419, plan (intention)

Name: Vysoce paralelní a distribuované výpočetní systémy Investor: Ministry of Education, Youth and Sports of the CR, Highly Parallel and Distributed Computing Systems