Scholars in Operations Research have studied automated timetabling for the past sixty years, developing algorithms that assign students and teachers to courses and timeslots. In the Post-Enrollment Course Timetabling Problem (PECTP), we seek the optimal timetable that maximizes students getting enrolled in their requested courses. Given the complexity of the NP-complete PECTP, most high schools pre-assign teachers to each section of each course, and then build their Master Timetable. This action reduces the number of feasible timetables, since no teacher can be teaching two courses in the same timeslot, and most teachers are required to have a non-teaching timeslot every day. In this paper, we explain how we created the Master Timetable for a Canadian high school that intentionally does not pre-assign teachers to courses. Instead, each course has a set of possible teachers, and each teacher has a fixed number of courses they must be assigned. By providing flexible teacher assignments, this school increases the likelihood that all students get into the courses they select. Our final Master Timetable enrolls students in 99.8% of their requested courses (3557 out of 3565), which is just one shy of the provably-optimal upper bound.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

The Post-Enrollment Course Timetabling Problem with Flexible Teacher Assignments

  • Richard Hoshino,
  • Zilei Liu

摘要

Scholars in Operations Research have studied automated timetabling for the past sixty years, developing algorithms that assign students and teachers to courses and timeslots. In the Post-Enrollment Course Timetabling Problem (PECTP), we seek the optimal timetable that maximizes students getting enrolled in their requested courses. Given the complexity of the NP-complete PECTP, most high schools pre-assign teachers to each section of each course, and then build their Master Timetable. This action reduces the number of feasible timetables, since no teacher can be teaching two courses in the same timeslot, and most teachers are required to have a non-teaching timeslot every day. In this paper, we explain how we created the Master Timetable for a Canadian high school that intentionally does not pre-assign teachers to courses. Instead, each course has a set of possible teachers, and each teacher has a fixed number of courses they must be assigned. By providing flexible teacher assignments, this school increases the likelihood that all students get into the courses they select. Our final Master Timetable enrolls students in 99.8% of their requested courses (3557 out of 3565), which is just one shy of the provably-optimal upper bound.