Optimization in timetabling in schools using a mathematical model, local search and Iterated Local Search procedures

Abstract This paper addresses the school timetabling problem, which consists of defining the date and time in which classes will be given by teachers in educational institutions. For this purpose, a tool that uses Operational Research (OR) techniques was developed, focused on generating and optimizing Elementary and High School timetables, taking into account teachers’ preferences for certain days or for sequenced (twinned) classes. Conductive to solving the problem, a Non Linear Binary Integer Programming mathematical model (NLBIP) and Local Search (LS) and Iterated Local Search (ILS) procedures were comparatively applied. A real problem with 14 timetables of public schools in the city of Araucária (in Paraná State, Brazil) was analyzed. The results indicate that the computational time required by the mathematical model is feasible for the problems in question. The ILS technique has the potential for testing larger scale problems, as it presents a dispersion of 3.5% to 7.7% relative to the optimal solution (obtained by the NLBIP) and a computational time that is 15 to 338 times faster.

摘要 本文针对学校排课问题展开研究，该问题的核心是明确教育机构内教师开展授课活动的日期与时段。为此，本文开发了一款运用运筹学（Operational Research, OR）技术的工具，旨在生成并优化小学与高中的排课方案，同时充分考量教师对特定授课日期或连堂课程的偏好。为求解该排课问题，本文对比应用了非线性二进制整数规划（Non Linear Binary Integer Programming, NLBIP）数学模型，以及局部搜索（Local Search, LS）、迭代局部搜索（Iterated Local Search, ILS）两种算法。本文分析了巴西巴拉那州阿拉里基亚市（Araucária）14所公立学校的真实排课问题实例。结果显示，该数学模型所需的计算时间针对所研究的问题具备可行性；迭代局部搜索算法具备处理更大规模问题的潜力：相较于非线性二进制整数规划模型得到的最优解，其解的相对偏差率为3.5%至7.7%，且计算速度较前者提升15至338倍。