Penalising Patterns in Timetables: Novel Integer Programming Formulations
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
- PDF / 188,560 Bytes
- 6 Pages / 439.37 x 666.142 pts Page_size
- 96 Downloads / 200 Views
2
Automated Scheduling, Optimisation and Planning Group The University of Nottingham School of Computer Science and IT Jubilee Campus in Wollaton Road, Nottingham NG8 1BB, UK Masaryk University Faculty of Informatics Botanick´ a 68a, Brno 602 00, The Czech Republic
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. Throughout the paper, the Udine Course Timetabling Problem is used as an illustrative example of timetabling with soft constraints. The problem has been formulated by Schaerf and Di Gaspero [6, 7] at the University of Udine. Its input can be outlined as follows: • C, T , R, D, P are sets representing courses, teachers, rooms, days, and periods, respectively • U is a set representing distinct enrolments in courses (“curricula”), with Inc being the mapping from curricula to (possibly overlapping) subsets of C • F is a set of pairs c, p ∈ C × P , representing deprecated periods p of courses c
410
Jakub Mareˇcek et al.
• HasEC maps courses to numbers of weekly unit-length events • HasStud maps courses to numbers of enrolled students • HasMinD maps courses to recommended minimum numbers of days of instruction per week • Teaches maps teachers to disjunctive sets of elements of C • HasCap maps rooms to their capacity • HasP maps days to tuples of corresponding periods in ascending order. Given this input, the task is to assign events to rooms and periods so that: for each course, HasEC[c] events are timetabled; no two events take place in the same room at the same period; no two events of one course are timetabled at the same period; events of no two courses in a single curriculum are taught at the same time; events of no two courses taught by a single teacher are timetabled at the same period; for all c, p ∈ F , events of course c are not taught at period p. The objective is to minimise the following weighted sum: the number of students left without a seat, summed across all events, with weight 1; the number of events timetabled for a curriculum outside of a single consecutive block of two or more events per day, summed across all curricula, with weight 2; the number of missing days of instruction, summed across all courses, with weight 5. In integer programming, most researchers [9
Data Loading...
