Heuristic methods for school timetabling problems

• Grant number: 13/13563-3
• Support Opportunities: Scholarships in Brazil - Doctorate
• Start date: November 01, 2013
• End date: October 07, 2017
• Field of knowledge: Engineering - Production Engineering - Operational Research
• Principal Investigator: Maristela Oliveira dos Santos
• Grantee: Landir Saviniec
• Host Institution: Instituto de Ciências Matemáticas e de Computação (ICMC). Universidade de São Paulo (USP). São Carlos , SP, Brazil
• Associated scholarship(s): 15/10032-2 - Heuristic algorithms for educational timetabling problems, BE.EP.DR

Abstract

This project aims to develop efficient and effective heuristic algorithms to solve school timetabling problems, since the applicability of exact algorithms for this purpose is limited. Initially, we intend to address the high school timetabling problem due to its theoretical and practical importance. In a previous project we developed, for this problem, two new graph-based large scale neighborhood operators for local search algorithms. We also built a dataset with 102 instances. Six algorithms based on ILS (Iterated Local Search) and three based on VNS (Variable Neighborhood Search) incorporating the operators developed have been implemented and tested in the proposed dataset and in a second dataset from literature. The results obtained were consistent with those obtained by state-of-the-art methods. In this project, our objective is to extend the methods developed, in order to increase the effectiveness, flexibility and efficiency of these approaches. In particular, we intend to study large scale neighborhood operators based on integer programming models. Such operators will be combined with local search metaheuristics to develop new algorithms to solve the problem. We also intend to incorporate new case studies (instances) in the existing dataset, making it, an even more representative compilation of real-world situations.

Scientific publications

(References retrieved automatically from Web of Science and SciELO through information on FAPESP grants and their corresponding numbers as mentioned in the publications by the authors)

SAYINIEC, LANDIR; SANTOS, MARISTELA O.; COSTA, ALYSSON M.. Parallel local search algorithms for high school timetabling problems. European Journal of Operational Research, v. 265, n. 1, p. 81-98, FEB 16 2018. (15/10032-2, 13/13563-3)

SAVINIEC, LANDIR; CONSTANTINO, ADEMIR APARECIDO. Effective local search algorithms for high school timetabling problems. APPLIED SOFT COMPUTING, v. 60, p. 363-373, NOV 2017. (13/13563-3)

SAVINIEC, LANDIR; SANTOS, MARISTELA O.; COSTA, ALYSSON M.; DOS SANTOS, LANA M. R.. Pattern-based models and a cooperative parallel metaheuristic for high school timetabling problems. European Journal of Operational Research, v. 280, n. 3, p. 1064-1081, FEB 1 2019. (15/10032-2, 13/13563-3)

Academic Publications

(References retrieved automatically from State of São Paulo Research Institutions)

SAVINIEC, Landir. Models and algorithms for high school timetabling problems. 2017. Doctoral Thesis - Universidade de São Paulo (USP). Instituto de Ciências Matemáticas e de Computação (ICMC/SB) São Carlos.