Page 30 - Fister jr., Iztok, Andrej Brodnik, Matjaž Krnc and Iztok Fister (eds.). StuCoSReC. Proceedings of the 2019 6th Student Computer Science Research Conference. Koper: University of Primorska Press, 2019
P. 30
Roomy capacity: The capacity of a room can be vio- 6. ACKNOWLEDGMENTS
lated, but every student above the capacity is worth 1
point. Ma´t´e Pint´er was supported by ”Integrated program for train-
ing new generation of scientists in the fields of computer
• Room stability: If lectures of a course are scheduled science”, no EFOP-3.6.3- VEKOP-16-2017-0002 (supported
into more than one room, then the penalty for each by the European Union and co-funded by the European
room beyond the first is 1 point. Social Fund). Bala´zs Da´vid acknowledges the European
Commission for funding the InnoRenew CoE project (Grant
• Minimum number of days: If a course is scheduled Agreement #739574) under the Horizon2020 Widespread-
on less days than the minimum required number, 5 Teaming program and the Republic of Slovenia (Investment
penalty points are given for missing each day. funding of the Republic of Slovenia and the European Union
of the European regional Development Fund), and is thank-
Test results of the algorithm are presented in Table 2. The ful for the support of the National Research, Development
algorithm was executed ten times for each instance, and the and Innovation Office - NKFIH Fund No. SNN-117879.
rounded average of these solutions is give by the table. The
destructive search ran for 30 steps in each iteration. 7. REFERENCES
Table 2: Test results [1] E. A. Akkoyunlu. A linear algorithm for computing
Instance Runningtime Penalty the optimum university timetable*. The Computer
Journal, 16(4):347–350, 1973.
Early Datasets
[2] H. Babaei, J. Karimpour, and A. Hadidi. A survey of
Comp01 32s 51 approaches for university course timetabling problem.
Computers & Industrial Engineering, 86:43–59, 2015.
Comp02 16M26s 328
[3] R. Bellio, S. Ceschia, L. D. Gaspero, A. Schaerf, and
Comp03 9M16s 314 T. Urli. Feature-based tuning of simulated annealing
applied to the curriculum-based course timetabling
Comp04 8M25s 348 problem. ArXiv, abs/1409.7186, 2014.
Comp05 7M32s 423 [4] A. Bettinelli, V. Cacchiani, R. Roberti, and P. Toth.
An overview of curriculum-based course timetabling.
Comp06 14M54s 503 TOP: An Official Journal of the Spanish Society of
Statistics and Operations Research, 23(2):313–349,
Comp07 15M46s 592 2015.
Late Datasets [5] E. Burke, Y. Bykov, J. Newall, and S. Petrovi´c. A
time-predefined approach to course timetabling.
Comp08 10M31s 361 Yugoslav Journal of Operations Research,
13(2):139–151, 2003.
Comp09 12M3s 285
[6] I. T. Competition. International timetabling
Comp10 16M17s 536 competition 2007.
http://www.cs.qub.ac.uk/itc2007/index.htm, 2007.
Comp11 43s 37 Accessed: 2019-07-30.
Comp12 11M4s 525 [7] G. Dueck. New optimization heuristics: The great
deluge algorithm and the record-to-record travel.
Comp13 9M42s 331 Journal of Computational Physics, 104(1):86 – 92,
1993.
Comp14 7M32s 434
[8] S. Even, A. Itai, and A. Shamir. On the complexity of
The table presents the total running time of both stages time table and multi-commodity flow problems. In
for each instance, as well as the total penalty of the best 16th Annual Symposium on Foundations of Computer
achieved solution. It can be seen from the results that while Science, pages 184–193, 1975.
the running times are acceptable, the penalties in some cases
are a bit high. This means that there is still room for the [9] G. Lach and M. E. Lu¨bbecke. Curriculum based
improvement of the algorithm. course timetabling: new solutions to udine benchmark
instances. Annals of Operations Research,
5. CONCLUSIONS AND FUTURE WORK 194(1):255–272, 2012.
In this paper, we examined the curriculum-based univer- [10] Z. Lu¨ and J.-K. Hao. Adaptive tabu search for course
sity course timetabling problem, and developed a two-stage timetabling. European Journal of Operational
heuristic algorithm for its solution. This algorithm uses a Research, 200(1):235–244, 2010.
greedy recursive approach to construct an initial solution,
then increases its quality with the help of a local search [11] T. Mu¨ller. Itc2007 solver description: a hybrid
method. While the local search itself is not fully a tabu approach. Annals of Operations Research, 172(1):429,
search algorithm, it utilizes a tabu list to store forbidden 2009.
transformations. A destructive step is also executed to es-
cape local optima at the end of each iteration. [12] K. Shaker, S. Abdullah, A. Alqudsi, and H. Jalab.
Hybridizing meta-heuristics approaches for solving
The algorithm was tested on the datasets of the 2007 Inter- university course timetabling problems. In P. Lingras,
national Timetabling Competition. While feasible solutions M. Wolski, C. Cornelis, S. Mitra, and P. Wasilewski,
were found for all instances, both their running time and editors, Rough Sets and Knowledge Technology, pages
quality can be improved. We would like to implement faster 374–384. Springer Berlin Heidelberg, 2013.
approaches for creating the initial solution, as well as im-
plementing a proper tabu search algorithm instead of the
current local search.
StuCoSReC Proceedings of the 2019 6th Student Computer Science Research Conference 30
Koper, Slovenia, 10 October
lated, but every student above the capacity is worth 1
point. Ma´t´e Pint´er was supported by ”Integrated program for train-
ing new generation of scientists in the fields of computer
• Room stability: If lectures of a course are scheduled science”, no EFOP-3.6.3- VEKOP-16-2017-0002 (supported
into more than one room, then the penalty for each by the European Union and co-funded by the European
room beyond the first is 1 point. Social Fund). Bala´zs Da´vid acknowledges the European
Commission for funding the InnoRenew CoE project (Grant
• Minimum number of days: If a course is scheduled Agreement #739574) under the Horizon2020 Widespread-
on less days than the minimum required number, 5 Teaming program and the Republic of Slovenia (Investment
penalty points are given for missing each day. funding of the Republic of Slovenia and the European Union
of the European regional Development Fund), and is thank-
Test results of the algorithm are presented in Table 2. The ful for the support of the National Research, Development
algorithm was executed ten times for each instance, and the and Innovation Office - NKFIH Fund No. SNN-117879.
rounded average of these solutions is give by the table. The
destructive search ran for 30 steps in each iteration. 7. REFERENCES
Table 2: Test results [1] E. A. Akkoyunlu. A linear algorithm for computing
Instance Runningtime Penalty the optimum university timetable*. The Computer
Journal, 16(4):347–350, 1973.
Early Datasets
[2] H. Babaei, J. Karimpour, and A. Hadidi. A survey of
Comp01 32s 51 approaches for university course timetabling problem.
Computers & Industrial Engineering, 86:43–59, 2015.
Comp02 16M26s 328
[3] R. Bellio, S. Ceschia, L. D. Gaspero, A. Schaerf, and
Comp03 9M16s 314 T. Urli. Feature-based tuning of simulated annealing
applied to the curriculum-based course timetabling
Comp04 8M25s 348 problem. ArXiv, abs/1409.7186, 2014.
Comp05 7M32s 423 [4] A. Bettinelli, V. Cacchiani, R. Roberti, and P. Toth.
An overview of curriculum-based course timetabling.
Comp06 14M54s 503 TOP: An Official Journal of the Spanish Society of
Statistics and Operations Research, 23(2):313–349,
Comp07 15M46s 592 2015.
Late Datasets [5] E. Burke, Y. Bykov, J. Newall, and S. Petrovi´c. A
time-predefined approach to course timetabling.
Comp08 10M31s 361 Yugoslav Journal of Operations Research,
13(2):139–151, 2003.
Comp09 12M3s 285
[6] I. T. Competition. International timetabling
Comp10 16M17s 536 competition 2007.
http://www.cs.qub.ac.uk/itc2007/index.htm, 2007.
Comp11 43s 37 Accessed: 2019-07-30.
Comp12 11M4s 525 [7] G. Dueck. New optimization heuristics: The great
deluge algorithm and the record-to-record travel.
Comp13 9M42s 331 Journal of Computational Physics, 104(1):86 – 92,
1993.
Comp14 7M32s 434
[8] S. Even, A. Itai, and A. Shamir. On the complexity of
The table presents the total running time of both stages time table and multi-commodity flow problems. In
for each instance, as well as the total penalty of the best 16th Annual Symposium on Foundations of Computer
achieved solution. It can be seen from the results that while Science, pages 184–193, 1975.
the running times are acceptable, the penalties in some cases
are a bit high. This means that there is still room for the [9] G. Lach and M. E. Lu¨bbecke. Curriculum based
improvement of the algorithm. course timetabling: new solutions to udine benchmark
instances. Annals of Operations Research,
5. CONCLUSIONS AND FUTURE WORK 194(1):255–272, 2012.
In this paper, we examined the curriculum-based univer- [10] Z. Lu¨ and J.-K. Hao. Adaptive tabu search for course
sity course timetabling problem, and developed a two-stage timetabling. European Journal of Operational
heuristic algorithm for its solution. This algorithm uses a Research, 200(1):235–244, 2010.
greedy recursive approach to construct an initial solution,
then increases its quality with the help of a local search [11] T. Mu¨ller. Itc2007 solver description: a hybrid
method. While the local search itself is not fully a tabu approach. Annals of Operations Research, 172(1):429,
search algorithm, it utilizes a tabu list to store forbidden 2009.
transformations. A destructive step is also executed to es-
cape local optima at the end of each iteration. [12] K. Shaker, S. Abdullah, A. Alqudsi, and H. Jalab.
Hybridizing meta-heuristics approaches for solving
The algorithm was tested on the datasets of the 2007 Inter- university course timetabling problems. In P. Lingras,
national Timetabling Competition. While feasible solutions M. Wolski, C. Cornelis, S. Mitra, and P. Wasilewski,
were found for all instances, both their running time and editors, Rough Sets and Knowledge Technology, pages
quality can be improved. We would like to implement faster 374–384. Springer Berlin Heidelberg, 2013.
approaches for creating the initial solution, as well as im-
plementing a proper tabu search algorithm instead of the
current local search.
StuCoSReC Proceedings of the 2019 6th Student Computer Science Research Conference 30
Koper, Slovenia, 10 October
