Η εργασία πραγματέυεται τη δημιουργία βοηθητικών εργαλείων για την χρήση δεδομένων από αρχεία xml και την επεξεργασία τους με αλγορίθμους σμήνους για την εξαγωγή συμπερασμάτων. / The current post graduate thesis addresses the issue of school timetabling problem through the usage of PSO algorithms. In order to achieve greater efficiency complementary tool have been designed and developed.

A geração de quadros de horários escolares é um problema clássico de otimização que tem sido largamente estudado devido a sua importâncias prática e teórica. O problema consiste em alocar um conjunto de aulas entre professor-turma em períodos de tempo pré-determinados, satisfazendo diferentes tipos de requisitos. Devido a natureza combinatória do problema, a resolução de instâncias médias e grandes torna-se uma tarefa desafiadora. Quando recursos são escassos, mesmo uma solução factível pode ser difícil de ser encontrada. Várias técnicas tem sido propostas na literatura científica para resolver o problema de geração de quadros de horários escolares, no entanto, métodos robustos ainda não existem. Visto que o uso de métodos exatos, como por exemplo, técnicas de programação matemática, não podem ser utilizados na prática, para resolver instâncias grandes da realidade, meta-heurísticas e meta-heurísticas híbridas são usadas com frequência como abordagens de resolução. Nesta pequisa, são desenvolvidas técnicas que combinam programação matemática e heurísticas, denominadas mateheurísticas, para resolver de maneira eficiente e robusta algumas variações de problemas de geração de quadros de horários escolares. Embora neste trabalho sejam abordados problemas encontrados no contexto de instituições brasileiras, os métodos propostos também podem ser aplicados em problemas similares oriundo de outros países. / The school timetabling is a classic optimization problem that has been extensively studied due to its practical and theoretical importance. It consists in scheduling a set of class-teacher meetings in a prefixed period of time, satisfying requirements of different types. Given the combinatorial nature of this problem, solving medium and large instances of timetabling to optimality is a challenging task. When resources are tight, it is often difficult to find even a feasible solution. Several techniques have been developed in the scientific literature to tackle the high school timetabling problem, however, robust solvers do not exist yet. Since the use of exact methods, such as mathematical programming techniques, is considered impracticable to solve large real world instances, metaheuristics and hybrid metaheuristics are the most used solution approaches. In this research we develop techniques that combine mathematical programming and heuristics, so-called matheuristics, to solve efficiently and in a robust way some variants of the high school timetabling problem. Although we pay special attention to problems arising in Brazilian institutions, the proposed methods can also be applied to problems from different countries.

Todo início de período letivo, gestores de instituições de ensino se deparam com um típico problema: montar as grades horárias das turmas, segundo as demandas de aulas de suas disciplinas e considerando as restrições de disponibilidade horária de todos os envolvidos. Conhecido na literatura como School Timetabling Problem (STP), este típico problema de otimização combinatória é reconhecidamente complexo por conta do seu elevado número de variáveis e restrições. Devido à dependência das regras do sistema educacional de cada país, o STP pode ter inúmeras variantes, cada uma com o seu próprio conjunto de particularidades. Este trabalho se propõe a oferecer um modelo para o STP considerando o sistema educacional brasileiro, visando alocar não apenas professores, mas também determinando que disciplina cada professor deve ministrar e alocando os locais de aula. O modelo proposto, baseado na meta-heurística simulated annealing, foi concebido para que cada instituição de ensino usuária tenha liberdade para definir a penalidade de cada tipo possível de inconformidade ou restrição, de modo que o algoritmo empregado possa encontrar uma solução com o menor custo possível. / Every beginning of term, educational institution managers face a typical problem: planning the classes' timetable, according to their lesson demands for each subject, considering, furthermore, the schedule constrains of all actors. Known as school timetabling problem (STP), this typical combinatorial optimization problem is remarkably complex due to the high number of variables and constraints. Owing to the rules of each country's educational system, STP can have uncountable variants, each one with their own set of features. This dissertation searches to offer a model to STP considering the Brazilian Educational System, focusing on allocating not only the teachers but also determining which subject each teacher should teach and allocating classrooms, laboratories and the like. The propesed model, based on the metaheuristic simulated annealing, was conceived so that each educational institution using this model has the freedom to define which penalty will be applied to each possible kind of noncomformity and constraint, in order for the applied algorithm to find a solution at the lowest cost as possible.

A geração de quadros de horários escolares é um problema clássico de otimização que tem sido largamente estudado devido a sua importâncias prática e teórica. O problema consiste em alocar um conjunto de aulas entre professor-turma em períodos de tempo pré-determinados, satisfazendo diferentes tipos de requisitos. Devido a natureza combinatória do problema, a resolução de instâncias médias e grandes torna-se uma tarefa desafiadora. Quando recursos são escassos, mesmo uma solução factível pode ser difícil de ser encontrada. Várias técnicas tem sido propostas na literatura científica para resolver o problema de geração de quadros de horários escolares, no entanto, métodos robustos ainda não existem. Visto que o uso de métodos exatos, como por exemplo, técnicas de programação matemática, não podem ser utilizados na prática, para resolver instâncias grandes da realidade, meta-heurísticas e meta-heurísticas híbridas são usadas com frequência como abordagens de resolução. Nesta pequisa, são desenvolvidas técnicas que combinam programação matemática e heurísticas, denominadas mateheurísticas, para resolver de maneira eficiente e robusta algumas variações de problemas de geração de quadros de horários escolares. Embora neste trabalho sejam abordados problemas encontrados no contexto de instituições brasileiras, os métodos propostos também podem ser aplicados em problemas similares oriundo de outros países. / The school timetabling is a classic optimization problem that has been extensively studied due to its practical and theoretical importance. It consists in scheduling a set of class-teacher meetings in a prefixed period of time, satisfying requirements of different types. Given the combinatorial nature of this problem, solving medium and large instances of timetabling to optimality is a challenging task. When resources are tight, it is often difficult to find even a feasible solution. Several techniques have been developed in the scientific literature to tackle the high school timetabling problem, however, robust solvers do not exist yet. Since the use of exact methods, such as mathematical programming techniques, is considered impracticable to solve large real world instances, metaheuristics and hybrid metaheuristics are the most used solution approaches. In this research we develop techniques that combine mathematical programming and heuristics, so-called matheuristics, to solve efficiently and in a robust way some variants of the high school timetabling problem. Although we pay special attention to problems arising in Brazilian institutions, the proposed methods can also be applied to problems from different countries.

A geração de quadros de horários escolares é um problema clássico de otimização que tem sido largamente estudado devido a sua importâncias prática e teórica. O problema consiste em alocar um conjunto de aulas entre professor-turma em períodos de tempo pré-determinados, satisfazendo diferentes tipos de requisitos. Devido a natureza combinatória do problema, a resolução de instâncias médias e grandes torna-se uma tarefa desafiadora. Quando recursos são escassos, mesmo uma solução factível pode ser difícil de ser encontrada. Várias técnicas tem sido propostas na literatura científica para resolver o problema de geração de quadros de horários escolares, no entanto, métodos robustos ainda não existem. Visto que o uso de métodos exatos, como por exemplo, técnicas de programação matemática, não podem ser utilizados na prática, para resolver instâncias grandes da realidade, meta-heurísticas e meta-heurísticas híbridas são usadas com frequência como abordagens de resolução. Nesta pequisa, são desenvolvidas técnicas que combinam programação matemática e heurísticas, denominadas mateheurísticas, para resolver de maneira eficiente e robusta algumas variações de problemas de geração de quadros de horários escolares. Embora neste trabalho sejam abordados problemas encontrados no contexto de instituições brasileiras, os métodos propostos também podem ser aplicados em problemas similares oriundo de outros países. / The school timetabling is a classic optimization problem that has been extensively studied due to its practical and theoretical importance. It consists in scheduling a set of class-teacher meetings in a prefixed period of time, satisfying requirements of different types. Given the combinatorial nature of this problem, solving medium and large instances of timetabling to optimality is a challenging task. When resources are tight, it is often difficult to find even a feasible solution. Several techniques have been developed in the scientific literature to tackle the high school timetabling problem, however, robust solvers do not exist yet. Since the use of exact methods, such as mathematical programming techniques, is considered impracticable to solve large real world instances, metaheuristics and hybrid metaheuristics are the most used solution approaches. In this research we develop techniques that combine mathematical programming and heuristics, so-called matheuristics, to solve efficiently and in a robust way some variants of the high school timetabling problem. Although we pay special attention to problems arising in Brazilian institutions, the proposed methods can also be applied to problems from different countries.

Todo início de período letivo, gestores de instituições de ensino se deparam com um típico problema: montar as grades horárias das turmas, segundo as demandas de aulas de suas disciplinas e considerando as restrições de disponibilidade horária de todos os envolvidos. Conhecido na literatura como School Timetabling Problem (STP), este típico problema de otimização combinatória é reconhecidamente complexo por conta do seu elevado número de variáveis e restrições. Devido à dependência das regras do sistema educacional de cada país, o STP pode ter inúmeras variantes, cada uma com o seu próprio conjunto de particularidades. Este trabalho se propõe a oferecer um modelo para o STP considerando o sistema educacional brasileiro, visando alocar não apenas professores, mas também determinando que disciplina cada professor deve ministrar e alocando os locais de aula. O modelo proposto, baseado na meta-heurística simulated annealing, foi concebido para que cada instituição de ensino usuária tenha liberdade para definir a penalidade de cada tipo possível de inconformidade ou restrição, de modo que o algoritmo empregado possa encontrar uma solução com o menor custo possível. / Every beginning of term, educational institution managers face a typical problem: planning the classes' timetable, according to their lesson demands for each subject, considering, furthermore, the schedule constrains of all actors. Known as school timetabling problem (STP), this typical combinatorial optimization problem is remarkably complex due to the high number of variables and constraints. Owing to the rules of each country's educational system, STP can have uncountable variants, each one with their own set of features. This dissertation searches to offer a model to STP considering the Brazilian Educational System, focusing on allocating not only the teachers but also determining which subject each teacher should teach and allocating classrooms, laboratories and the like. The propesed model, based on the metaheuristic simulated annealing, was conceived so that each educational institution using this model has the freedom to define which penalty will be applied to each possible kind of noncomformity and constraint, in order for the applied algorithm to find a solution at the lowest cost as possible.

Todo início de período letivo, gestores de instituições de ensino se deparam com um típico problema: montar as grades horárias das turmas, segundo as demandas de aulas de suas disciplinas e considerando as restrições de disponibilidade horária de todos os envolvidos. Conhecido na literatura como School Timetabling Problem (STP), este típico problema de otimização combinatória é reconhecidamente complexo por conta do seu elevado número de variáveis e restrições. Devido à dependência das regras do sistema educacional de cada país, o STP pode ter inúmeras variantes, cada uma com o seu próprio conjunto de particularidades. Este trabalho se propõe a oferecer um modelo para o STP considerando o sistema educacional brasileiro, visando alocar não apenas professores, mas também determinando que disciplina cada professor deve ministrar e alocando os locais de aula. O modelo proposto, baseado na meta-heurística simulated annealing, foi concebido para que cada instituição de ensino usuária tenha liberdade para definir a penalidade de cada tipo possível de inconformidade ou restrição, de modo que o algoritmo empregado possa encontrar uma solução com o menor custo possível. / Every beginning of term, educational institution managers face a typical problem: planning the classes' timetable, according to their lesson demands for each subject, considering, furthermore, the schedule constrains of all actors. Known as school timetabling problem (STP), this typical combinatorial optimization problem is remarkably complex due to the high number of variables and constraints. Owing to the rules of each country's educational system, STP can have uncountable variants, each one with their own set of features. This dissertation searches to offer a model to STP considering the Brazilian Educational System, focusing on allocating not only the teachers but also determining which subject each teacher should teach and allocating classrooms, laboratories and the like. The propesed model, based on the metaheuristic simulated annealing, was conceived so that each educational institution using this model has the freedom to define which penalty will be applied to each possible kind of noncomformity and constraint, in order for the applied algorithm to find a solution at the lowest cost as possible.

High school timetabling problems consist in assigning meetings between classes and teachers, with the goal of minimizing the violation of specific soft requisites. This category of problems has been extensively studied since the 1950s, mostly via mixed-integer programming and metaheuristic techniques. However, the computation of optimal or near-optimal solutions using mixed-integer programs or metaheuristics is still a challenge for most practical problems. In this thesis, we investigate new mixed-integer programming formulations, column generation approaches and parallel metaheuristic based algorithms to compute lower bounds and solutions for high school timetabling problems. Extensive computational experiments conducted with real-world instances demonstrate that our best formulations are competitive with best-known formulations, while our parallel algorithms present superior performance than the state-of-the-art methods. / Problemas de horários escolares consistem em alocar encontros entre turmas e professores, com objetivo de minimizar violações a requisitos qualitativos específicos. Esta categoria de problemas tem sido largamente estudada desde 1950, particularmente via técnicas de programação linear inteira mista e metaheurísticas. Entretanto, a computação de soluções ótimas ou quase ótimas usando programas inteiro-mistos ou metaheurísticas ainda é um desafio na maioria dos problemas práticos. Nesta tese, nós investigamos novas formulações inteiro-mistas, decomposições por geração de colunas e algoritmos baseados em metaheurísticas paralelas para computar limitantes inferiores e soluções para problemas de horários escolares. Extensivos experimentos computacionais conduzidos com instâncias reais demonstram que nossas melhores formulações são competitivas com as melhores formulações existentes, enquanto nossos algoritmos paralelos são superiores em performance computacional quando comparados com métodos que são estado-da-arte.

High school timetabling problems consist in assigning meetings between classes and teachers, with the goal of minimizing the violation of specific soft requisites. This category of problems has been extensively studied since the 1950s, mostly via mixed-integer programming and metaheuristic techniques. However, the computation of optimal or near-optimal solutions using mixed-integer programs or metaheuristics is still a challenge for most practical problems. In this thesis, we investigate new mixed-integer programming formulations, column generation approaches and parallel metaheuristic based algorithms to compute lower bounds and solutions for high school timetabling problems. Extensive computational experiments conducted with real-world instances demonstrate that our best formulations are competitive with best-known formulations, while our parallel algorithms present superior performance than the state-of-the-art methods. / Problemas de horários escolares consistem em alocar encontros entre turmas e professores, com objetivo de minimizar violações a requisitos qualitativos específicos. Esta categoria de problemas tem sido largamente estudada desde 1950, particularmente via técnicas de programação linear inteira mista e metaheurísticas. Entretanto, a computação de soluções ótimas ou quase ótimas usando programas inteiro-mistos ou metaheurísticas ainda é um desafio na maioria dos problemas práticos. Nesta tese, nós investigamos novas formulações inteiro-mistas, decomposições por geração de colunas e algoritmos baseados em metaheurísticas paralelas para computar limitantes inferiores e soluções para problemas de horários escolares. Extensivos experimentos computacionais conduzidos com instâncias reais demonstram que nossas melhores formulações são competitivas com as melhores formulações existentes, enquanto nossos algoritmos paralelos são superiores em performance computacional quando comparados com métodos que são estado-da-arte.

This thesis devote itself to use of information system for school agenda administration. Schools are forced to administer big amounts of informations, not only referred to their students. Broad issue is very extensive and disparate, so the most common types of data and demands on school information system operation are stated. The system for automatic generation of timetables is part of the school information system. At the first, basic conceptions of scheduling scope are defined and tied together with them are methods and algorithms for timetable creation problem solving. School timetabling is problem of scheduling lessons with certain limitative conditions. Further, thesis is engaged in design of school information system, data organization in such system and solving of system design problems. Designed information system accentuates on easy expandability and wide range of usage possibilities. Also suggested algorithm for solving of defined school timetabling is stated in this part of thesis.