Penalising Patterns in Timetables: Novel Integer Programming Formulations

Edmund K. Burke, Jakub Mareček, Andrew J. Parkes and Hana Rudová
Additional contact information
Edmund K. Burke: The University of Nottingham School of Computer Science and IT
Jakub Mareček: The University of Nottingham School of Computer Science and IT
Andrew J. Parkes: The University of Nottingham School of Computer Science and IT
Hana Rudová: Masaryk University Faculty of Informatics

A chapter in Operations Research Proceedings 2007, 2008, pp 409-414 from Springer

Abstract: Abstract Many complex timetabling problems have an underpinning bounded graph colouring component, a pattern penalisation component and a number of side constraints. The bounded graph colouring component corresponds to hard constraints such as “students are in at most one place at one time” and “there is a limited number of rooms” [3]. Despite the hardness of graph colouring, it is often easy to generate feasible colourings. However, real-world timetabling systems [5] have to cope with much more challenging requirements, such as “students should not have gaps in their individual daily timetables”, which often make the problem over-constrained. The key to tackling this challenge is a suitable formulation of “soft” constraints, which count and minimise penalties incurred by matches of various patterns. Several integer programming formulations are presented and discussed in this paper.

Keywords: Soft Constraint; Hard Constraint; Timetabling Problem; Integer Programming Formulation; Binary Array (search for similar items in EconPapers)
Date: 2008
References: Add references at CitEc
Citations: View citations in EconPapers (3)

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:oprchp:978-3-540-77903-2_63

Ordering information: This item can be ordered from
http://www.springer.com/9783540779032

DOI: 10.1007/978-3-540-77903-2_63

Access Statistics for this chapter

More chapters in Operations Research Proceedings from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().