|
|
|
Mathematical model and simulated annealing algorithm for Chinese high school timetabling problems under the new curriculum innovation |
Xingxing HAO, Jing LIU( ), Yutong ZHANG, Gustaph SANGA |
| Key Laboratory of Intelligent Perception and Image Understanding of Ministry of Education, Xidian University, Xi’an 710071, China |
|
|
|
|
Abstract As the first attempt, this paper proposes a model for the Chinese high school timetabling problems (CHSTPs) under the new curriculum innovation which was launched in 2014 by the Chinese government. According to the new curriculum innovation, students in high school can choose subjects that they are interested in instead of being forced to select one of the two study directions, namely, Science and Liberal Arts. Meanwhile, they also need to attend compulsory subjects as traditions. CHSTPs are student-oriented and involve more student constraints that make them more complex than the typical “Class-Teacher model”, in which the element “Teacher” is the primary constraint. In this paper, we first describe in detail the mathematical model of CHSTPs and then design a new two-part representation for the candidate solution. Based on the new representation, we adopt a two-phase simulated annealing (SA) algorithm to solve CHSTPs. A total number of 45 synthetic instances with different amounts of classes, teachers, and levels of student constraints are generated and used to illustrate the characteristics of the CHSTP model and the effectiveness of the designed representation and algorithm. Finally,we apply the proposed model, the designed two-part representation and the two-phase SA on10 real high schools.
|
| Keywords
timetabling
Chinese high school timetablingproblem
simulated annealing
two-part representation
|
|
Corresponding Author(s):
Jing LIU
|
|
Just Accepted Date: 26 February 2020
Issue Date: 24 September 2020
|
|
| 1 |
S Kristiansen, T R Stidsen. A comprehensive study of educational timetabling-a survey. Department of Management Engineering, Technical University of Denmark, DTU Management Engineering Report, Denmark, 2013
|
| 2 |
N Pillay. A survey of school timetabling research. Annals of Operations Research, 2014, 218(1): 261–293
https://doi.org/10.1007/s10479-013-1321-8
|
| 3 |
S M Al-Yakoob, H D Sherali. Mathematical models and algorithms for a high school timetabling problem. Computers & Operations Research, 2015, 61: 56–68
https://doi.org/10.1016/j.cor.2015.02.011
|
| 4 |
L F Kwok, S C Kong, Y Y Kam. Timetabling in Hong Kong secondary schools. Computers & Education, 1997, 28(3): 173–183
https://doi.org/10.1016/S0360-1315(97)00009-2
|
| 5 |
H G Santos, L S Ochi, M J F Souza. An efficient tabu search heuristic for the school timetabling problem. In: Proceedings of International Workshop on Experimental and Efficient Algorithms. 2004, 468–481
https://doi.org/10.1007/978-3-540-24838-5_35
|
| 6 |
H G Santos, L S Ochi, M J F Souza. A tabu search heuristic with efficient diversification strategies for the class/teacher timetabling problem. Journal of Experimental Algorithmics, 2005, 10: 2–9
https://doi.org/10.1145/1064546.1180621
|
| 7 |
G N Beligiannis, C N Moschopoulos, G P Kaperonis, S D Likothanassis. Applying evolutionary computation to the school timetabling problem: the Greek case. Computers & Operations Research, 2008, 35(4): 1265–1280
https://doi.org/10.1016/j.cor.2006.08.010
|
| 8 |
G N Beligiannis, C Moschopoulos, S D Likothanassis. A genetic algorithm approach to school timetabling. Journal of the Operational Research Society, 2009, 60(1): 23–42
https://doi.org/10.1057/palgrave.jors.2602525
|
| 9 |
D Zhang, Y Liu, R M’Hallah, S C H Leung. A simulated annealing with a new neighborhood structure based algorithm for high school timetabling problems. European Journal of Operational Research, 2010, 203(3): 550–558
https://doi.org/10.1016/j.ejor.2009.09.014
|
| 10 |
I V Katsaragakis, I X Tassopoulos, G N Beligiannis. A comparative study of modern heuristics on the school timetabling problem. Algorithms, 2015, 8(3): 723–742
https://doi.org/10.3390/a8030723
|
| 11 |
V I Skoullis, I X Tassopoulos, G N Beligiannis. Solving the high school timetabling problem using a hybrid cat swarm optimization based algorithm. Applied Soft Computing, 2017, 52: 277–289
https://doi.org/10.1016/j.asoc.2016.10.038
|
| 12 |
R Raghavjee, N Pillay. An informed genetic algorithm for the high school timetabling problem. In: Proceedings of the 2010 Annual Research Conference of the South African Institute of Computer Scientists and Information Technologists. 2010, 408–412
https://doi.org/10.1145/1899503.1899555
|
| 13 |
R Raghavjee, N Pillay. Evolving solutions to the school timetabling problem. In: Proceedings of World Congress on Nature & Biologically Inspired Computing. 2009, 1524–1527
https://doi.org/10.1109/NABIC.2009.5393667
|
| 14 |
R Raghavjee, N Pillay. A genetic algorithm selection perturbative hyperheuristic for solving the school timetabling problem. ORiON, 2015, 31(1): 39–60
https://doi.org/10.5784/31-1-158
|
| 15 |
A Cerdeira-Pena, L Carpente, A Farina, D Seco. New approaches for the school timetabling problem. In: Proceedings of the 7th Mexican International Conference on Artificial Intelligence. 2008, 261–267
https://doi.org/10.1109/MICAI.2008.19
|
| 16 |
O A Odeniyi, E O Omidiora, S O Olabiyisi, J O Aluko. Development of a modified simulated annealing to school timetabling problem. International Journal of Applied Information Systems, 2015, 8(1): 16–24
https://doi.org/10.5120/ijais14-451277
|
| 17 |
N Boland, B D Hughes, L T G Merlot, P J Stuckey. New integer linear programming approaches for course timetabling. Computers & Operations Research, 2008, 35(7): 2209–2233
https://doi.org/10.1016/j.cor.2006.10.016
|
| 18 |
J H Kingston. A tiling algorithm for high school timetabling. In: Proceedings of International Conference on the Practice and Theory of Automated Timetabling. 2004, 208–225
https://doi.org/10.1007/11593577_13
|
| 19 |
L Merlot. Techniques for academic timetabling. PhD Thesis, University of Melbourne, Australia, 2005
|
| 20 |
F G Ribeiro, L A N Lorena. A constructive evolutionary approach to school timetabling. In: Proceedings of Workshops on Applications of Evolutionary Computation. 2001, 130–139
https://doi.org/10.1007/3-540-45365-2_14
|
| 21 |
R J R Willemen. School Timetable Construction: Algorithms and Complexity. Eindhoven: Technische Universiteit Eindhoven, 2002
|
| 22 |
G S Bello, M C Rangel, M C S Boeres. An approach for the class/teacher timetabling problem using graph coloring. In: Proceedings of the International Conference on the Practice and Theory of Automated Timetabling. 2008
|
| 23 |
A V Moura, R A Scaraficci. A GRASP strategy for a more constrained school timetabling problem. International Journal of Operational Research, 2010, 7(2): 152–170
https://doi.org/10.1504/IJOR.2010.030801
|
| 24 |
H G Santos, E Uchoa, L S Ochi, N Maculan. Strong bounds with cut and column generation for class-teacher timetabling. Annals of Operations Research, 2012, 194(1): 399–412
https://doi.org/10.1007/s10479-010-0709-y
|
| 25 |
S S Brito, G H G Fonseca, T A M Toffolo, H G Santos, M J F Souza. A SA-VNS approach for the high school timetabling problem. Electronic Notes in Discrete Mathematics, 2012, 39: 169–176
https://doi.org/10.1016/j.endm.2012.10.023
|
| 26 |
G Lach, M E Lübbecke. Curriculum based course timetabling: new solutions to Udine benchmark instances. Annals of Operations Research, 2012, 194(1): 255–272
https://doi.org/10.1007/s10479-010-0700-7
|
| 27 |
M Sørensen, F H W Dahms. A two-stage decomposition of high school timetabling applied to cases in Denmark. Computers & Operations Research, 2014, 43: 36–49
https://doi.org/10.1016/j.cor.2013.08.025
|
| 28 |
T Birbas, S Daskalaki, E Housos. Timetabling for Greek high schools. Journal of the Operational Research Society, 1997, 48(12): 1191–1200
https://doi.org/10.1038/sj.jors.2600480
|
| 29 |
C Valouxis, E Housos. Constraint programming approach for school timetabling. Computers & Operations Research, 2003, 30(10): 1555–1572
https://doi.org/10.1016/S0305-0548(02)00083-7
|
| 30 |
K Papoutsis, C Valouxis, E Housos. A column generation approach for the timetabling problem of Greek high schools. Journal of the Operational Research Society, 2003, 54(3): 230–238
https://doi.org/10.1057/palgrave.jors.2601495
|
| 31 |
C N Moschopoulos, C E Alexakos, C Dosi, G N Beligiannis, S D Likothanassis. A user-friendly evolutionary tool for high-school timetabling. Tools and Applications with Artificial Intelligence, 2009, 166: 149–162
https://doi.org/10.1007/978-3-540-88069-1_12
|
| 32 |
T Birbas, S Daskalaki, E Housos. School timetabling for quality student and teacher schedules. Journal of Scheduling, 2009, 12(2): 177–197
https://doi.org/10.1007/s10951-008-0088-2
|
| 33 |
C Valouxis, C Gogos, P Alefragis, E Housos. Decomposing the high school timetable problem. In: Proceedings of International Conference on the Practice and Theory of Automated Timetabling. 2012, 29–31
|
| 34 |
A Colorni, M Dorigo, V Maniezzo. Metaheuristics for high school timetabling. Computational Optimization and Applications, 1998, 9(3): 275–298
https://doi.org/10.1023/A:1018354324992
|
| 35 |
A Schaerf. Local search techniques for large high school timetabling problems. IEEE Transactions on Systems, Man, and Cybernetics-Part A: Systems and Humans, 1999, 29(4): 368–377
https://doi.org/10.1109/3468.769755
|
| 36 |
P Avella, B D’Auria, S Salerno, I Vasil’ev. A computational study of local search algorithms for Italian high-school timetabling. Journal of Heuristics, 2007, 13(6): 543–556
https://doi.org/10.1007/s10732-007-9025-3
|
| 37 |
C Fernandes, J P Caldeira, F Melicio, A Rosa. High school weekly timetabling by evolutionary algorithms. In: Proceedings of the ACM Symposium on Applied Computing. 1999, 344–350
https://doi.org/10.1145/298151.298379
|
| 38 |
F Melício, J P Calderia, A Rosa. THOR: a tool for school timetabling. In: Proceedings of International Conference on the Practice and Teaching of Automated Timetabling. 2006, 532–535
|
| 39 |
R Alvarez-Valdés, F Parreño, J M Tamarit. A tabu search algorithm for assigning teachers to courses. Top, 2002, 10(2): 239–259
https://doi.org/10.1007/BF02579018
|
| 40 |
K Nurmi, J Kyngas. A framework for school timetabling problem. In: Proceedings of the 3rd Multidisciplinary International Scheduling Conference: Theory and Applications. 2007, 386–393
|
| 41 |
G F Post, H W A Ruizenaar, G Post, H Ruizenaar. Clusterschemes in Dutch secondary schools. Department of Applied Mathematics, University of Twente, The Netherlands, 2004
|
| 42 |
H P De, R Landman, G Post, H Ruizenaar. A case study for timetabling in a Dutch secondary school. In: Proceedings of International Conference on the Practice and Theory of Automated Timetabling. 2006, 267–279
https://doi.org/10.1007/978-3-540-77345-0_17
|
| 43 |
G Post, S Ahmadi, F Geertsema. Cyclic transfers in school timetabling. OR Spectrum, 2012, 34(1): 133–154
https://doi.org/10.1007/s00291-010-0227-y
|
| 44 |
J Hartog. Timetabling on dutch high schools. PhD Thesis, The Netherland: Technische Universiteit Delft, 2007
|
| 45 |
M Bufé, T Fischer, H Gubbels, C Häcker, O Hasprich, C Scheibel, K Weicker, N Weicker, M Wenig, C Wolfangel. Automated solution of a highly constrained school timetabling problem-preliminary results. In: Proceedings ofWorkshops on Applications of Evolutionary Computation. 2001, 431–440
https://doi.org/10.1007/3-540-45365-2_45
|
| 46 |
P Wilke, M Gröbner, N Oster. A hybrid genetic algorithm for school timetabling. In: Proceedings of Australian Joint Conference on Artificial Intelligence. 2002, 455–464
https://doi.org/10.1007/3-540-36187-1_40
|
| 47 |
F Jacobsen, A Bortfeldt, H Gehring. Timetabling at German secondary schools: tabu search versus constraint programming. In: Proceedings of International Conference on the Practice and Theory of Automated Timetabling. 2006, 439–442
|
| 48 |
M Löhnertz. A timetabling system for the German gymnasium. In: Proceedings of International Conference on the Practice and Theory of Automated Timetabling. 2002
|
| 49 |
M Marte. Models and algorithms for school timetabling–a constraintprogramming approach. Dissertation, Ludwig-Maximilians-Universitat Munchen, 2002
|
| 50 |
J Wood, D Whitaker. Student centred school timetabling. Journal of the Operational Research Society, 1998, 49(11): 1146–1152
https://doi.org/10.1038/sj.jors.2600628
|
| 51 |
P Wilke, J Ostler. Solving the school time tabling problem using tabu search, simulated annealing, genetic and branch & bound algorithms. In: Proceedings of the 7th International Conference on the Practice and Theory of Automated Timetabling. 2008, 3–6
|
| 52 |
P Wilke, H Killer. Comparison of algorithms solving school and course time tabling problems using the erlangen advanced time tabling system (EATTS). In: Proceedings of the 8th International Conference on the Practice and Theory of Automated Timetabling. 2010, 427–439
|
| 53 |
C Paper, M K Shambour, A T Khader, E Ozcan. A two stage approach for high school timetabling. In: Proceedings of International Conference on Neural Information Processing. 2013, 66–73
https://doi.org/10.1007/978-3-642-42054-2_9
|
| 54 |
G H G Fonseca, H G Santos, T Â M Toffolo, S S Brito, M J F Souza. GOAL solver: a hybrid local search based solver for high school timetabling. Annals of Operations Research, 2016, 239(1): 77–97
https://doi.org/10.1007/s10479-014-1685-4
|
| 55 |
G H G Fonseca, H G Santos. Variable neighborhood search based algorithms for high school timetabling. Computers & Operations Research, 2014, 52: 203–208
https://doi.org/10.1016/j.cor.2013.11.012
|
| 56 |
G H G Fonseca, H G Santos, E G Carrano. Late acceptance hill-climbing for high school timetabling. Journal of Scheduling, 2016, 19(4): 453–465
https://doi.org/10.1007/s10951-015-0458-5
|
| 57 |
S Kristiansen, M Sørensen, T R Stidsen. Integer programming for the generalized high school timetabling problem. Journal of Scheduling, 2015, 18(4): 377–392
https://doi.org/10.1007/s10951-014-0405-x
|
| 58 |
G Post, J H Kingston, S Ahmadi, S Daskalaki, C Gogos, J Kyngas, C Nurmi, N Musliu, N Pillay, H Santos, A Schaerf. XHSTT: an XML archive for high school timetabling problems in different countries. Annals of Operations Research, 2014, 218(1): 295–301
https://doi.org/10.1007/s10479-011-1012-2
|
| 59 |
G H G Fonseca, H G Santos, E G Carrano. Integrating matheuristics and metaheuristics for timetabling. Computers & Operations Research, 2016, 74: 108–117
https://doi.org/10.1016/j.cor.2016.04.016
|
| 60 |
G H G Fonseca, H G Santos, E G Carrano, T J R Stidsen. Integer programming techniques for educational timetabling. European Journal of Operational Research, 2017, 262(1): 28–39
https://doi.org/10.1016/j.ejor.2017.03.020
|
| 61 |
E K Burke, G Kendall, M Misir, E Özcan. A study of simulated annealing hyper-heuristics. In: Proceedings of the International Conference on the Practice and Theory of Automated Timetabling. 2008
|
| 62 |
E K Burke, G Kendall, M Misir, E Özcan. Monte carlo hyper-heuristics for examination timetabling. Annals of Operations Research, 2012, 196(1): 73–90
https://doi.org/10.1007/s10479-010-0782-2
|
| 63 |
R Bai, J Blazewicz, E K Burke, G Kendall, B McCollum. A simulated annealing hyper-heuristic methodology for flexible decision support. 4OR: A Quarterly Journal of Operations Research, 2012, 10(1): 43–66
https://doi.org/10.1007/s10288-011-0182-8
|
| 64 |
M Chiarandini, M Birattari, K Socha, O Rossi-Doria. An effective hybrid algorithm for university course timetabling. Journal of Scheduling, 2006, 9(5): 403–432
https://doi.org/10.1007/s10951-006-8495-8
|
| 65 |
W G Jackson, E Özcan, R I John. Move acceptance in local search metaheuristics for cross-domain search. Expert Systems with Applications, 2018, 109: 131–151
https://doi.org/10.1016/j.eswa.2018.05.006
|
|
Viewed |
|
|
|
Full text
|
|
|
|
|
Abstract
|
|
|
|
|
Cited |
|
|
|
|
| |
Shared |
|
|
|
|
| |
Discussed |
|
|
|
|
