| Name: | Description: | Size: | Format: | |
|---|---|---|---|---|
| 7.84 MB | Adobe PDF |
Authors
Advisor(s)
Abstract(s)
No contexto da actividade de gestão das instituições de ensino, os problemas que envolvem o planeamento temporal de eventos, sejam estes as aulas relativas aos círculos dos cursos oferecidos ou os exames requeridos para a sua avaliação, originam normalmente problemas complexos e de difícil resolução, bem conhecidos no domínio da Investigação Operacional. É precisamente sobre um destes problemas, denominado por problema de elaboração de horários escolares, que incide o estudo desenvolvido nesta dissertação. O problema consiste no escalonamento semanal de um conjunto de aulas (afetações de professores a disciplinas e turmas previamente definidas), sujeito a um extenso conjunto de condicionalismos obrigatórios e facultativos. Num primeiro momento após a sua caracterização,são propostas formalizações matemáticas com variáveis binárias e estudada a sua complexidade computacional.Constatada a inerente dificuldade computacional associada ao problema descrito procede-se ao desenvolvimento de heurísticas adaptadas à efectiva resolução do problema. Para o efeito, no contexto das redes neuronais artificiais, após a definição de uma função de energia comum adaptada aoproblema em estudo, são propostos dois algoritmos. O primeiro é baseado em neurónios contínuos de Potts, enquanto que uma segunda versão recorre a neurónios discretos winner-takes-all. Alternativamente, no domínio dos algoritmos genéticos, são apresentadas duas abordagens distintas para a resolução do problema. A primeira baseia-se num algiritmo genético uni-objectivo enquanto que a segunda trata o problema numa perspectiva multi-objectivo. A implementação computacional, concretizada através da resolução de um conjunto de instâncias reais e hipotéticas, permitiu avaliar e comparar o desempenho dos algoritmos propostos. Em resultado deste estudo descreve-se uma aplicação informática desenvolvida com base nos algiritmos propostos, designada GAHOR, que permite a resolução prática de qualquer instância do problema.
Within the activity of teaching institution management,problems involving time-planning od events, be they lessons related to the curricula of courses available or the exams required to assess them, normally generate complex problems that are difficult to solve, and are wellknown in the area of Operational Research. It is precisely on one of these problems, known as the Class/Teacher Timetabling Problem (PEHE), that the study developed in this dissertation focuses. The problem consists in a weekly scheduling of a set of classes (assignements of teachers to subjects and pre-defined classes), subject to a broad set of hard and soft constraints. In a first phase following characterization of the issue, binary mathematical formalizations are proposed and the computational complexity is studied. Having recognized the computational difficulty inherent to the problem described, specially adapted heuristics are developed. To this end, within the context of artificial neural networks, after defining an energy function appropriate tothe problem in question, two algorithms are proposed. The first is based on Potts' continuous neurons, whereas the second version resorts to winner-takes-all discrete neurons. Alternatively, in the field of genetic algorithms, two distinct approaches to the problem are presented. The first one uses a uni-objective genetic algorithm, whereas a second considers the problem from a multiobjective stance. Computacional tests, achieved by solving a set real and hypothetical instances, enabled evaluation and comparison of the performance of all the algorithms proposed. As a result of this study a computer application (GAHOR) developed on the basis of the algorithms is described.
Within the activity of teaching institution management,problems involving time-planning od events, be they lessons related to the curricula of courses available or the exams required to assess them, normally generate complex problems that are difficult to solve, and are wellknown in the area of Operational Research. It is precisely on one of these problems, known as the Class/Teacher Timetabling Problem (PEHE), that the study developed in this dissertation focuses. The problem consists in a weekly scheduling of a set of classes (assignements of teachers to subjects and pre-defined classes), subject to a broad set of hard and soft constraints. In a first phase following characterization of the issue, binary mathematical formalizations are proposed and the computational complexity is studied. Having recognized the computational difficulty inherent to the problem described, specially adapted heuristics are developed. To this end, within the context of artificial neural networks, after defining an energy function appropriate tothe problem in question, two algorithms are proposed. The first is based on Potts' continuous neurons, whereas the second version resorts to winner-takes-all discrete neurons. Alternatively, in the field of genetic algorithms, two distinct approaches to the problem are presented. The first one uses a uni-objective genetic algorithm, whereas a second considers the problem from a multiobjective stance. Computacional tests, achieved by solving a set real and hypothetical instances, enabled evaluation and comparison of the performance of all the algorithms proposed. As a result of this study a computer application (GAHOR) developed on the basis of the algorithms is described.
Description
Doutoramento em Matemática
Keywords
Pedagogical Context
Citation
Carrasco, Marco Paulo dos Santos (2003)." O problema de elaboaração de horários escolares - estudo e resolução automatizada". Tese de Doutoramento. Universidade Técnica de Lisboa. Instituto Superior de Economia e Gestão.
Publisher
Instituto Superior de Economia e Gestão