Heuristic algorithms for educational timetabling problems

• Grant number: 15/10032-2
• Support Opportunities: Scholarships abroad - Research Internship - Doctorate
• Start date: January 20, 2016
• End date: December 19, 2016
• Field of knowledge: Engineering - Production Engineering - Operational Research
• Principal Investigator: Maristela Oliveira dos Santos
• Grantee: Landir Saviniec
• Supervisor: Alysson Machado Costa
• Host Institution: Instituto de Ciências Matemáticas e de Computação (ICMC). Universidade de São Paulo (USP). São Carlos , SP, Brazil
• Institution abroad: University of Melbourne, Australia
• Associated to the scholarship: 13/13563-3 - Heuristic methods for school timetabling problems, BP.DR

Abstract

This project addresses the Class-Teacher Timetabling Problem, which is a variant of the High School Timetabling Problem. The problem is NP-Hard and due to practical requirements, real problems generally have a large number of variables, making ineffective the applicability of exact methods. Therefore, heuristic methods are commonly employed to generate solutions. Despite the existence of benchmarks for testing and comparisons, few instances with optimal solutions or strong dual bounds are available. This makes it difficult to assess how close the solutions are from the global optima. In this project we will investigate heuristics and relaxation methods to generate solutions and dual bounds to the problem. This document provides an overview of our research. The text concludes with a research plan proposed to be developed in co-supervision of Professor Alysson M. Costa at The University of Melbourne - Australia. (AU)

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; 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)