An Analysis Framework for Examination Timetabling.Report as inadecuate

An Analysis Framework for Examination Timetabling. - Download this document for free, or read online. Document in PDF available to download.

1 Heudiasyc - Heuristique et Diagnostic des Systèmes Complexes Compiègne

Abstract : An examination timetabling problem taken from real world universities was proposed at the International Timetabling Competition ITC2007. The aim was to establish a common base for comparing different solution approaches. This paper presents new preprocessing methods that disclose hidden constraints and significantly increase the number of new edges that can be added to the conflict graph. Results show that the size of the maximum clique of the obtained conflict graph has been more than doubled for two instances as a result of our preprocessing. These larger cliques mean that instances can be analyzed in advance of a solution and end users gain useful information for making decisions. In addition, we have looked at the different criteria that compose the objective function, in order to provide more useful insights into the difficulty of problems in practice. We propose new integer programming formulations using clique inequalities to compute optimal solutions for 4 criteria and to obtain lower bounds for the 3 others. Results are presented and discussed for all the benchmark instances

Keywords : Integer programming Preprocessing Lower Bounds

Author: Taha Arbaoui - Jean-Paul Boufflet - Aziz Moukrim -



Related documents