Methodology for relevant characteristics definition, classification and appropriate algorithm selection of time tabling problems

• Grant number: 15/08967-3
• Support Opportunities: Research Grants - Innovative Research in Small Business - PIPE
• Start date: August 01, 2016
• End date: April 30, 2017
• Field of knowledge: Engineering - Production Engineering - Operational Research
• Principal Investigator: Rodrigo Carareto
• Grantee: Rodrigo Carareto
• Company: Brunoro e Orsatti Pesquisa e Desenvolvimento Ltda
• City: São Paulo
• Pesquisadores principais: Guilherme Barroso Mainieri
• Associated scholarship(s): 16/09334-7 - Methodology for relevant characteristics definition, classification and appropriate algorithm selection of time tabling problems, BP.PIPE

Abstract

Many Brazilian educational institutions looking for solutions to develop and manage the teachers' classes allocation in order to replace a process that is performed manually, spending excessive hours of human resources and can even generate additional costs on behalf of teacher hours with classes vacancies. Furthermore, it is not always possible to manually ensure an uniform distribution of the same class or subject (scientific disciplines, for example) to a class. There are software products dedicated to solving this type of problem (timetabling problem), a case of resource allocation problem with constraints (physical space, time and people). Generally these products already use broadcasted algorithms in the literature. However, by focusing on specific cases, and because the Brazilian schools have different characteristics that impact the possibility of solving the problem, these algorithms do not always show individually suitable for particular situations. Although you can resolve these situations making use of such products, they often become unviable. For example, when a school has two physical units that share some teachers, it is possible to consider each unit as a separate issue where, for teachers shared by the units, the user manually divides these availabilities to allocate concurrent classes for teachers of the same teacher. However, testing all possibilities in order to optimized solution becomes a counterproductive work. Furthermore, when there are many shared teachers, this task proves to be impossible. In addition, one of the main objectives of these products is in fact to automate the scale development process (minimizing the user's work), this strategy proves contrary to this main goal. Thus, from a scientific point of view, the challenges of this research project are to develop a methodology that: 1) identifying the relevant characteristics for the development of problem of scale; 2) fosters the identification of the type of problem to be solved according the characteristics of the institution and consequently; 3) establish the choice of the most suitable algorithm (or combination of algorithms for each stage of the problem) and accompanying parameters. (AU)