Citation
A Decomposition of the Max-min Fair Curriculum-based Course Timetabling Problem: The Impact of Solving Subproblems to Optimality. In proceedings of the 6th Multidisciplinary International Conference on Scheduling : Theory and Applications (MISTA 2013), 27 - 30 Aug 2013, Ghent, Belgium, pages 300-313, 2013.
Paper
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 subproblemoftheMMF-CB-CTTproblemcanbesolvedef?ciently.Weapplythisresultto apreviouslyproposedheuristicalgorithmfortheMMF-CB-CTTproblem,inwhichsolving 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.
You can download the pdf of this publication from here
doi
This publication does not have a doi, so we cannot provide a link to the original source
What is a doi?: A doi (Document Object Identifier) is a unique identifier for sicientific papers (and occasionally other material). This provides direct access to the location where the original article is published using the URL http://dx.doi/org/xxxx (replacing xxx with the doi). See http://dx.doi.org/ for more information
URL
This pubication does not have a URL associated with it.
The URL is only provided if there is additional information that might be useful. For example, where the entry is a book chapter, the URL might link to the book itself.
Bibtex
@INPROCEEDINGS{2013-300-313-P, author = {M. Muhlenthaler and R. Wanka},
title = {A Decomposition of the Max-min Fair Curriculum-based Course Timetabling Problem: The Impact of Solving Subproblems to Optimality},
booktitle = {In proceedings of the 6th Multidisciplinary International Conference on Scheduling : Theory and Applications (MISTA 2013), 27 - 30 Aug 2013, Ghent, Belgium},
year = {2013},
editor = {G. Kendall and B. McCollum and G. {Venden Berghe}},
pages = {300--313},
note = {Paper},
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 subproblemoftheMMF-CB-CTTproblemcanbesolvedef?ciently.Weapplythisresultto apreviouslyproposedheuristicalgorithmfortheMMF-CB-CTTproblem,inwhichsolving 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.},
owner = {Graham},
timestamp = {2017.01.16},
webpdf = {2013-300-313-P.pdf} }