Mathematical model and simulated annealing algorithm for Chinese high school timetabling problems under the new curricul
- PDF / 471,116 Bytes
- 11 Pages / 612.284 x 802.205 pts Page_size
- 30 Downloads / 212 Views
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 c Higher Education Press 2020
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 timetabling problem, simulated annealing, two-part representation
1
Introduction
The high school timetabling problem (HSTP) is one type of complex educational timetabling problem faced by academic institutions, especially by educational organizations in the world [1–3]. The purpose of HSTPs is to find weekly timetables for courses, teachers, students, and classrooms that satisfy a set of hard and soft constraints [1,2]. For instance, one teacher cannot be assigned to more than one class at the same timeslot is a hard constraint, while timeslots being assigned to a teacher should be uniformly distributed throughout the week is a soft constraint. A feasible timetable is the one that does not violate Received March 25, 2019; accepted December 12, 2019 E-mail: [email protected]
any hard constraint, while a good one is at first feasible and then should satisfy soft constraints as much as possible. HSTPs are highly constrained and proven to be NP-complete [2]. In 2014, the Chinese government launched a new curriculum innovation that advocates more flexible examination systems for the National College Entrance Examination of China. Among numbers of new educational systems since then, the “3+X” system has been widely implemented. In this new system, “3” represents three compulsory subjects and “X” represents the number of optional subject
Data Loading...
