- James Sakal ORCID:orcid.org/0009-0006-3585-720914,
- Jonathan Fieldsend ORCID:orcid.org/0000-0002-0683-258314 &
- Edward Keedwell ORCID:orcid.org/0000-0003-3650-648714
Part of the book series:Lecture Notes in Computer Science ((LNCS,volume 14091))
Included in the following conference series:
233Accesses
Abstract
The University Course Timetabling Problem is a combinatorial optimisation problem in which feasible assignments of lectures are sought. Weighted sums of violations of various constraints are used as a quality measure, with lower scores (costs) being more desirable. In this study, we develop a domain-specific many-objective optimiser, based on constructive heuristics and NSGA-III, in which the violations of different constraints are cast as separate objectives to be minimised concurrently. We show that feasible solutions can be attained consistently in a first phase and that a targeted objective can be fully optimised in a second phase. A set of non-dominated solutions is returned, representing a well-spread approximation to the Pareto front, from which a decision maker could ultimately choose according toa posteriori preferences.
This is a preview of subscription content,log in via an institution to check access.
Access this chapter
Subscribe and save
- Get 10 units per month
- Download Article/Chapter or eBook
- 1 Unit = 1 Article or 1 Chapter
- Cancel anytime
Buy Now
- Chapter
- JPY 3498
- Price includes VAT (Japan)
- eBook
- JPY 7435
- Price includes VAT (Japan)
- Softcover Book
- JPY 9294
- Price includes VAT (Japan)
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Abdullah, S., Turabieh, H.: On the use of multi neighbourhood structures within a tabu-based memetic approach to university timetabling problems. Inf. Sci.191, 146–168 (2012)
Atsuta, M., Nonobe, K., Ibaraki, T.: ITC-2007 Track 2: An approach using general CSP solver. In: Proceedings of the Practice and Theory of Automated Timetabling (2007)
Bagger, N.C.F., Sørensen, M., Stidsen, T.R.: Dantzig-Wolfe decomposition of the daily course pattern formulation for curriculum-based course timetabling. Eur. J. Oper. Res.272(2), 430–446 (2019)
Bonutti, A., De Cesco, F., Di Gaspero, L., Schaerf, A.: Benchmarking curriculum-based course timetabling: formulations, data formats, instances, validation, visualization, and results. Ann. Oper. Res.194(1), 59–70 (2012)
Clark, M., Henz, M., Love, B.: QuikFix a repair-based timetable solver. In: 7th International Conference on the Practice and Theory of Automated Timetabling, PATAT 2008 (2008)
Deb, K., Jain, H.: An evolutionary many-objective optimization algorithm using reference-point based non-dominated sorting approach, part i: solving problems with box constraints. IEEE Trans. Evol. Comput.18(4), 577–601 (2013)
Deb, K., Pratap, A., Agarwal, S., Meyarivan, T.: A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Trans. Evol. Comput.6(2), 182–197 (2002)
Fieldsend, J.E.: Data structures for non-dominated sets: implementations and empirical assessment of two decades of advances. In: GECCO 2020 - Proceedings of the 2020 Genetic and Evolutionary Computation Conference, pp. 489–497 (2020)
di Gaspero, L., Schaerf, A., McCollum, B.: The second international timetabling competition: curriculum-based course timetabling (Track 3). In: Proceedings of the 1st International Workshop on Scheduling a Scheduling Competition (2007)
Geiger, M.J.: An application of the threshold accepting metaheuristic for curriculum based course timetabling. In: Proceedings of the 7th International Conference on the Practice and Theory of Automated Timetabling (PATAT) (2008)
Geiger, M.J.: Multi-criteria curriculum-based course timetabling—a comparison of a weighted sum and a reference point based approach. In: Ehrgott, M., Fonseca, C.M., Gandibleux, X., Hao, J.-K., Sevaux, M. (eds.) EMO 2009. LNCS, vol. 5467, pp. 290–304. Springer, Heidelberg (2009).https://doi.org/10.1007/978-3-642-01020-0_25
Geiger, M.J.: Applying the threshold accepting metaheuristic to curriculum based course timetabling. Ann. Oper. Res.194(1), 189–202 (2012)
Gozali, A.A., Fujimura, S.: Solving university course timetabling problem using multi-depth genetic algorithm. SHS Web Conf.77, 01001 (2020)
Hafsa, M., Wattebled, P., Jacques, J., Jourdan, L.: A Multi-objective evolutionary approach to professional course timetabling: a real-world case study. In: 2021 IEEE Congress on Evolutionary Computation, pp. 997–1004 (2021)
Kiefer, A., Hartl, R.F., Schnell, A.: Adaptive large neighborhood search for the curriculum-based course timetabling problem. Ann. Oper. Res.252(2), 255–282 (2017)
Lewis, R., Paechter, B., Rossi-Doria, O.: Metaheuristics for university course timetabling. Stud. Comput. Intell.49, 237–272 (2007)
Müller, T.: ITC2007 solver description: a hybrid approach. Ann. Oper. Res.172(1), 429–446 (2009)
Pillay, N., Özcan, E.: Automated generation of constructive ordering heuristics for educational timetabling. Ann. Oper. Res.275(1), 181–208 (2019)
Rossi-Doria, O., et al.: A comparison of the performance of different metaheuristics on the timetabling problem. Pract. Theory Autom. Timetabling IV2740, 329–351 (2003)
Tian, Y., Cheng, R., Zhang, X., Jin, Y.: PlatEMO: A MATLAB platform for evolutionary multi-objective optimization. IEEE Comput. Intell. Mag.12(4), 73–87 (2017)
Zhang, X., Tian, Y., Cheng, R., Jin, Y.: An efficient approach to nondominated sorting for evolutionary multiobjective optimization. IEEE Trans. Evol. Comput.19(2), 201–213 (2015)
Author information
Authors and Affiliations
University of Exeter, Exeter, UK
James Sakal, Jonathan Fieldsend & Edward Keedwell
- James Sakal
You can also search for this author inPubMed Google Scholar
- Jonathan Fieldsend
You can also search for this author inPubMed Google Scholar
- Edward Keedwell
You can also search for this author inPubMed Google Scholar
Corresponding author
Correspondence toJames Sakal.
Editor information
Editors and Affiliations
University of Bordeaux, Talence, France
Pierrick Legrand
University of Lille, Lille, France
Arnaud Liefooghe
University of Exeter, Exeter, UK
Edward Keedwell
Université de Haute-Alsace, Mulhouse, France
Julien Lepagnot
Université de Haute Alsace, Mulhouse, France
Lhassane Idoumghar
Ecole Polytechnique de Université de Tours, Tours, France
Nicolas Monmarché
INRA, Thirverval-Grignon, France
Evelyne Lutton
Rights and permissions
Copyright information
© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Sakal, J., Fieldsend, J., Keedwell, E. (2023). Towards a Many-Objective Optimiser for University Course Timetabling. In: Legrand, P.,et al. Artificial Evolution. EA 2022. Lecture Notes in Computer Science, vol 14091. Springer, Cham. https://doi.org/10.1007/978-3-031-42616-2_10
Download citation
Published:
Publisher Name:Springer, Cham
Print ISBN:978-3-031-42615-5
Online ISBN:978-3-031-42616-2
eBook Packages:Computer ScienceComputer Science (R0)
Share this paper
Anyone you share the following link with will be able to read this content:
Sorry, a shareable link is not currently available for this article.
Provided by the Springer Nature SharedIt content-sharing initiative