Loading...
Publication
Geração de horários para instituições de ensino superior
| Name: | Description: | Size: | Format: | |
|---|---|---|---|---|
| 5.79 MB | Adobe PDF |
Authors
Advisor(s)
Abstract(s)
University Course Scheduling Problem (UCSP) is classified as an NP-Hard problem, which is a combinatorial optimization problem that requires effective methods to manage the high level of complexity in constraints, optimization of time and resources, and assure its practical applicability to higher educational institutions. In an attempt to solve the UCSP, this document analyzes a wide array of methodologies, including Genetic Algorithm (GA), Particle Swarm Optimization (PSO), and Local Search (LS), among others. Strong emphasis is made on the aptitude and limitations of each approach, further to adaptability to specific scheduling scenarios. This work addresses the key research questions so that relevant insights, valuable for enhanced understanding, could be extracted to drive further improvement in automated scheduling systems. Based on the findings, a solution was designed and developed with a modular architecture, implementing GA and PSO, along with a dedicated
correction module, which uses LS to explore nearby solutions and reduce constraint violations. Generated schedules were evaluated through fitness functions, identifying conflicts in resource assignments and penalizing them accordingly, which allowed comparisons with other schedules, including manually created ones, based on implemented criteria. This solution was then experimented with a real-world scenario, using data from the Bachelor’s Degree in Informatics Engineering at ISEP. The results compare various configurations and strategies,
for each algorithm, demonstrating the effectiveness of the proposed solution in generating feasible and optimized schedules, highlighting its potential for practical deployment and future research in automated university course scheduling.
O Problema de Escalonamento de Cursos Universitários (UCSP) é classificado como um problema NP-Hard, sendo um problema de otimização combinatória que requer métodos eficazes para gerir o elevado nível de complexidade das restrições, otimizar o tempo e os recursos, e garantir a sua aplicabilidade prática em instituições de ensino superior. Na tentativa de resolver o UCSP, este documento analisa uma vasta gama de metodologias, incluindo Algoritmos Genéticos (GA), Otimização por Enxame de Partículas (PSO) e Pesquisa Local (LS), entre outras. É dada especial ênfase à aptidão e limitações de cada abordagem, bem como à adaptabilidade a cenários específicos da criação de horários. Este trabalho aborda as principais questões de investigação, de modo a extrair informações relevantes e valiosas para uma melhor compreensão, promovendo melhorias nos sistemas automatizados de agendamento. Com base nos resultados, foi concebida e desenvolvida uma solução com arquitetura modular, implementando GA e PSO, juntamente com um módulo de correção dedicado, que utiliza LS para explorar soluções próximas e reduzir violações de restrições. Os horários gerados foram avaliados através de funções de fitness, identificando conflitos na atribuição de recursos e penalizando-os adequadamente, o que permitiu comparações com outros horários, incluindo os criados manualmente, com base nos critérios implementados. Esta solução foi então experimentada num cenário real, utilizando dados da Licenciatura em Engenharia Informática do ISEP. Os resultados comparam várias configurações e estratégias para cada algoritmo, demonstrando a eficácia da solução proposta na geração de horários viáveis e otimizados, destacando o seu potencial para implementação prática e investigação futura em sistemas automatizados de agendamento universitário.
O Problema de Escalonamento de Cursos Universitários (UCSP) é classificado como um problema NP-Hard, sendo um problema de otimização combinatória que requer métodos eficazes para gerir o elevado nível de complexidade das restrições, otimizar o tempo e os recursos, e garantir a sua aplicabilidade prática em instituições de ensino superior. Na tentativa de resolver o UCSP, este documento analisa uma vasta gama de metodologias, incluindo Algoritmos Genéticos (GA), Otimização por Enxame de Partículas (PSO) e Pesquisa Local (LS), entre outras. É dada especial ênfase à aptidão e limitações de cada abordagem, bem como à adaptabilidade a cenários específicos da criação de horários. Este trabalho aborda as principais questões de investigação, de modo a extrair informações relevantes e valiosas para uma melhor compreensão, promovendo melhorias nos sistemas automatizados de agendamento. Com base nos resultados, foi concebida e desenvolvida uma solução com arquitetura modular, implementando GA e PSO, juntamente com um módulo de correção dedicado, que utiliza LS para explorar soluções próximas e reduzir violações de restrições. Os horários gerados foram avaliados através de funções de fitness, identificando conflitos na atribuição de recursos e penalizando-os adequadamente, o que permitiu comparações com outros horários, incluindo os criados manualmente, com base nos critérios implementados. Esta solução foi então experimentada num cenário real, utilizando dados da Licenciatura em Engenharia Informática do ISEP. Os resultados comparam várias configurações e estratégias para cada algoritmo, demonstrando a eficácia da solução proposta na geração de horários viáveis e otimizados, destacando o seu potencial para implementação prática e investigação futura em sistemas automatizados de agendamento universitário.
Description
Keywords
University Course Scheduling Problem (UCSP) Combinatorial Optimization NP-Hard Problems Genetic Algorithms (GA) Particle Swarm Optimization (PSO) Local Search (LS) Automated Scheduling Systems