A column generation approach to high school timetabling modeled as a multicommodity flow problem

Árton P. Dorneles, Olinto C.B. de Araújo and Luciana S. Buriol

European Journal of Operational Research, 2017, vol. 256, issue 3, 685-695

Abstract: School timetabling is a classic optimization problem that has been extensively studied due to its practical and theoretical importance. It consists in scheduling a set of class-teacher meetings in a predetermined period of time, satisfying requirements of different types. Given the combinatorial nature of this problem, solving medium and large instances of timetabling to optimality is a challenging task. When resources are tight, often it is difficult to find even a feasible solution. Several techniques have been developed in the literature to tackle the high school timetabling problem. Since the use of exact methods, as mathematical programming techniques, are considered impracticable to solve large real world instances, metaheuristics and hybrid metaheuristics are the most used solution approaches. In this paper we propose a multicommodity flow model for the high school timetabling problem. In addition, we apply Dantzig–Wolfe decomposition to the proposed model, propose a column generation algorithm, and present experimental results on well known instances of the problem. The results show that the lower bounds obtained through our approach are tight and can be generated faster than previous approaches reported in the literature.

Keywords: Timetabling; MILP; Column generation; Multicommodity flow (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (5)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221716305392
Full text for ScienceDirect subscribers only

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:eee:ejores:v:256:y:2017:i:3:p:685-695

DOI: 10.1016/j.ejor.2016.07.002

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().