Friedrich-Alexander-Universität DruckenUnivisEnglish FAU-Logo
Techn. Fakultät Willkommen am Department Informatik FAU-Logo
Lehrstuhl für Informatik 12
Department Informatik  >  Informatik 12  >  Personal  >  Rolf Wanka  >  Veröffentlichungen  >  MW13

A Decomposition of the Max-min Fair Curriculum-based Course Timetabling Problem: The Impact of Solving Subproblems to Optimality

Moritz Mühlenthaler and Rolf Wanka

Department of Computer Science
University of Erlangen-Nuremberg, Germany

Abstract. 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 (GLBOP). We show that the GLBOP can be solved in polynomial time if the corresponding sum optimization problem can be solved in polynomial time as well. Thus, the room assignment subproblem of the MMF-CB-CTT problem can be solved efficiently. We apply this result to a previously proposed heuristic algorithm for the MMF-CB-CTT problem, in which solving the room assignment subproblem is a key ingredient. Our experimental results indicate that using the proposed 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 and the average solution quality. Furthermore, we introduce a measure for the quality of a solution to a (generalized) lexicographic bottleneck 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.

Full article in PDF

arXiv:1303.5601 (2013)

Published in: Proc. 6th Multidisciplinary International Scheduling Conference: Theory & Applications (MISTA), pp. 300-313, 2013.

  Impressum Stand: 04 September 2013.   R.W.