A Decomposition of the Max-min Fair Curriculum-based Course Timetabling
  Problem
  We propose a decomposition of the max-min fair curriculum-based course
timetabling (MMF-CB-CTT) problem. The decomposition models the room assignment
subproblem as a generalized lexicographic bottleneck optimization problem
(LBOP). We show that the generalized LBOP can be solved efficiently if the
corresponding sum optimization problem can be solved efficiently. As a
consequence, the room assignment subproblem of the MMF-CB-CTT problem can be
solved efficiently. We use this insight to improve a previously proposed
heuristic algorithm for the MMF-CB-CTT problem. Our experimental results
indicate that using the new decomposition improves the performance of the
algorithm on most of the 21 ITC2007 test instances with respect to the quality
of the best solution found. Furthermore, we introduce a measure of the quality
of a solution to a max-min fair optimization problem. This measure helps to
overcome some limitations imposed by the qualitative nature of max-min fairness
and aids the statistical evaluation of the performance of randomized algorithms
for such problems. We use this measure to show that using the new decomposition
the algorithm outperforms the original one on most instances with respect to
the average solution quality.
