Measuring the complexity of university timetabling instances

Felipe Rosa-Rivera (), Jose I. Nunez-Varela (), Cesar A. Puente-Montejano () and Sandra E. Nava-Muñoz ()
Additional contact information
Felipe Rosa-Rivera: Universidad Autónoma de San Luis Potosí
Jose I. Nunez-Varela: Universidad Autónoma de San Luis Potosí
Cesar A. Puente-Montejano: Universidad Autónoma de San Luis Potosí
Sandra E. Nava-Muñoz: Universidad Autónoma de San Luis Potosí

Journal of Scheduling, 2021, vol. 24, issue 1, No 8, 103-121

Abstract: Abstract University timetabling is a real-world problem frequently encountered in higher education institutions. It has been studied by many researchers who have proposed a wide variety of solutions. Measuring the variation of the performance of solution approaches across instance spaces is a critical factor for algorithm selection and algorithm configuration, but because of the diverse conditions that define the problem within different educational contexts, measurement has not been formally addressed within the university timetabling context. In this paper, we propose a set of metrics to predict the performance of combinatorial optimization algorithms that generate initial solutions for university timetabling instances. These metrics, derived from the fields of enumerative combinatorics and graph coloring, include size-related instance properties, counting functions, feature ratios and constraint indexes evaluated through a feature selection methodology that, based on regression algorithms, characterizes the empirical hardness of a subspace of synthetically generated instances. The results obtained with this methodology show the current need not only to develop solution strategies for particular cases of the problem, but also to produce a formal description of the conditions that make instance spaces hard to solve, in order to improve and integrate the available solution approaches.

Keywords: University timetabling; Empirical hardness; Feature selection; Instance generator (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10951-020-00641-y Abstract (text/html)
Access to the full text of the articles in this series is restricted.

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:spr:jsched:v:24:y:2021:i:1:d:10.1007_s10951-020-00641-y

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10951

DOI: 10.1007/s10951-020-00641-y

Access Statistics for this article

Journal of Scheduling is currently edited by Edmund Burke and Michael Pinedo

More articles in Journal of Scheduling from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().