liu.seSearch for publications in DiVA
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Models and methods for school timetabling using a column generation approach
Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.
2002 (English)Licentiate thesis, monograph (Other academic)
Abstract [en]

Creating timetables for educational institutions is a complex task, and the quality of the timetables affects a large number of students and teachers. This process involves assigning teachers to courses, students to classes, classrooms to lessons and setting the starting time of the lessons.

In this thesis, models and solution methods are presented for the assignment of starting times and classrooms as appearing in Swedish schools. This school system has two aspects that make timetabling particularly hard. The first is the mix of both individual and class based timetables, and the second that lessons can have any length unlike many other school systems which only has lessons of the same length. For the timetables to be of practical interest, modelling of quality aspects of a timetable is also a major issue.

A first generalised set-packing model is presented for the problem, with a column representing a feasible schedule for one class. Solution techniques involving column generation and constraint branching are developed and presented. This model is deemed too complex to solve, and a sequential solution approach that solves the problem in several stages is presented. The models and solution techniques in the sequential solution approach also involve column generation and constraint branching. The models allow for a capturing many quality aspects of a timetable. The sequential solution approach is tested on a test database, and the results are presented and discussed. A study of improving the performance of the branch-andbound method is finally presented.

Place, publisher, year, edition, pages
Linköping: Linköpings universitet , 2002. , p. 79
Series
Linköping Studies in Science and Technology. Thesis, ISSN 0280-7971 ; 937
National Category
Mathematics
Identifiers
URN: urn:nbn:se:liu:diva-144751ISBN: 9173733067 (print)OAI: oai:DiVA.org:liu-144751DiVA, id: diva2:1179838
Presentation
2002-04-19, BL32, hus B, Campus Valla, Linköping, 10:15 (English)
Opponent
Available from: 2018-02-02 Created: 2018-02-02 Last updated: 2018-04-03Bibliographically approved

Open Access in DiVA

No full text in DiVA

Authority records BETA

Eveborn, Patrik

Search in DiVA

By author/editor
Eveborn, Patrik
By organisation
Optimization The Institute of Technology
Mathematics

Search outside of DiVA

GoogleGoogle Scholar

isbn
urn-nbn

Altmetric score

isbn
urn-nbn
Total: 16 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf