abstract

• In this paper, we present the construction process of a per-instance algorithm selection model to improve the initial solutions of Curriculum-Based Course Timetabling (CB-CTT) instances. Following the meta-learning framework, we apply a hybrid approach that integrates the predictions of a classifier and linear regression models to estimate and compare the performance of four meta-heuristics across different problem sub-spaces described by seven types of features. Rather than reporting the average accuracy, we evaluate the model using the closed SBS-VBS gap, a performance measure used at international algorithm selection competitions. The experimental results show that our model obtains a performance of 0.386, within the range obtained by per-instance algorithm selection models in other combinatorial problems. As a result of the process, we conclude that the performance variation between the meta-heuristics has a significant role in the effectiveness of the model. Therefore, we introduce statistical analyses to evaluate this factor within per-instance algorithm portfolios. © 2021 Elsevier Ltd

authors

• de la Rosa-Rivera F.
• Núñez Varela José Ignacio

publication date

• 2021-01-01

funding provided via

• DE-AC04-94-AL85000; U.S. Department of Energy, USDOE; Chemical Sciences, Geosciences, and Biosciences Division, CSGB  Grant

published in

• Expert Systems with Applications  Journal

keywords

• Algorithm selection; Educational timetabling; Meta-heuristic; Meta-learning Genetic algorithms; Heuristic algorithms; Learning algorithms; Regression analysis; Algorithm selection; Construction process; Course timetabling; Educational timetabling; Initial solution; Metaheuristic; Metalearning; Performance; Selection model; Timetabling problem; Scheduling

Digital Object Identifier (DOI)

• 10.1016/j.eswa.2021.114694

PubMed ID

start page

end page

volume

• 174

issue