Algorithms and heuristics for timetable scheduling problems

• Grant number: 11/10895-0
• Support Opportunities: Scholarships in Brazil - Scientific Initiation
• Effective date (Start): September 01, 2011
• Effective date (End): July 31, 2012
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Theory of Computation
• Principal Investigator: Eduardo Candido Xavier
• Grantee: Douglas Oliveira Santos
• Host Institution: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brazil

Abstract

In this project we are interested in the problem of allocating resources with timetable constraints, problems known in the literature as Timetable Scheduling problems. The problem is to allocate teachers, classrooms and time-schedules to satisfy a demand of given courses in a given period of time. We have to allocate teachers to courses and these ones to timetable and classrooms respecting many restrictions, such as that no teacher is allocated to different courses at the same time. Many versions of the Timetable Scheduling problem are NP-Hard. Our interest is to investigate efficient algorithms that give good practical solutions to this problem. Our objective is to study Timetable Scheduling problems and to implement a solution to one specific version of the problem. This solution might be used to allocate teachers and courses at the Instituto de Computação of UNICAMP. (AU)