LUNCH: an Answer Set Programming System for Course Scheduling
Resumo
Timetable scheduling is a known NP-hard problem; despite this, there have been many efforts to enable fast and efficient algorithms and heuristics for such a challenging task. Within the realm of timetable scheduling lies the particularly complex problem of Course Scheduling (CS). The goal in CS is to find an optimal timetable configuration of courses within the constraints set by faculty, course requirements and departmental functions. Answer Set Programming (ASP) is a declarative logic programming paradigm for solving combinatorial search tasks; instead of explicitly writing the solution to the problem, ASP programs define the problem’s constraints and knowledge in a high-level language, leaving the model search to a highly optimized solver. In this work, we construct and showcase LUNCH, an easily extensible, free and open-source system for course scheduling. Notably, we study the use of ASP for course scheduling within the specific context of the Computer Science Department at the University of São Paulo, showing how LUNCH fares against the manual scheduling done in previous years.
Referências
Alghamdi, H., Alsubait, T., Alhakami, H., and Baz, A. (2020). A review of optimization algorithms for university timetable scheduling. Engineering, Technology and Applied Science Research, 10(6):6410–6417.
Baral, C. (2003). Knowledge Representation, Reasoning and Declarative Problem Solving. Cambridge University Press.
Calimeri, F., Faber, W., Gebser, M., Ianni, G., Kaminski, R., Krennwallner, T., Leone, N., Maratea, M., Ricca, F., and Schaub, T. (2020). Asp-core-2 input language format. Theory and Practice of Logic Programming, 20(2):294–309.
Carter, M. W. and Laporte, G. (1998). Recent developments in practical course timetabling. In Practice and Theory of Automated Timetabling II: Second International Conference, PATAT’97 Toronto, Canada, August 20–22, 1997 Selected Papers 2, pages 3–19. Springer.
Cataldo, A., Ferrer, J.-C., Miranda, J., Rey, P. A., and Sauré, A. (2017). An integer programming approach to curriculum-based examination timetabling. Annals of Operations Research, 258(2):369–393.
Cooper, T. B. and Kingston, J. H. (2005). The complexity of timetable construction problems. International Conference on the Practice and Theory of Automated Timetabling.
Daskalaki, S., Birbas, T., and Housos, E. (2004). An integer programming formulation for a case study in university timetabling. European journal of operational research, 153(1):117–135.
de Werra, D. (1985). An introduction to timetabling. European journal of operational research, 19(2):151–162.
Gebser, M., Kaminski, R., Kaufmann, B., Lindauer, M., Ostrowski, M., Romero, J., Schaub, T., Thiele, S., and Wanko, P. (2019). Potassco User Guide, 2 edition.
Gebser, M., Kaminski, R., Kaufmann, B., and Schaub, T. (2017). Multi-shot ASP solving with clingo. CoRR, abs/1705.09811.
Gebser, M., Kaufmann, B., and Schaub, T. (2012). Conflict-driven answer set solving: From theory to practice. Artif. Intell., 187:52–89.
Gelfond, M. and Lifschitz, V. (1991). Classical negation in logic programs and disjunctive databases. New Generation Computing, 9:365–385.
Holm, D. S., Mikkelsen, R. Ø., Sørensen, M., and Stidsen, T. J. (2022). A graph-based mip formulation of the international timetabling competition 2019. Journal of Scheduling, 25(4):405–428.
Larabi Marie-Sainte, S. (2015). A survey of particle swarm optimization techniques for solving university examination timetabling problem. Artificial Intelligence Review, 44(4):537–546.
Phillips, A. E., Walker, C. G., Ehrgott, M., and Ryan, D. M. (2017). Integer programming for minimal perturbation problems in university course timetabling. Annals of Operations Research, 252(2):283–304.
Schaerf, A. (1999). A survey of automated timetabling. Artificial intelligence review, 13:87–127.
Zilberstein, S. and Russell, S. (1996). Using anytime algorithms in intelligent systems. The Springer International Series in Engineering and Computer Science.
