engenheiro

4 ESTUDO DE CASO

A área de concentração deste trabalho é o Problema de Alocação de Salas (PAS). Este problema é tratado como parte integrante do Problema de Programação de Cursos Universitários (course timetabling), pertencendo assim a categoria de Problemas de Programação de Horários (PPH). A conhecida dificuldade desses problemas já é uma grande motivação para este trabalho. O PAS é um Problema de Otimização Combinatória bastante estudado. Ele é um problema NP-Difícil, inviabilizando sua solução manual e impossibilitando sua resolução por métodos de programação matemática (métodos exatos) para grandes instâncias. Uma vez que não é possível encontrar a solução ótima do PAS em tempo razoável para grandes instâncias, esse problema é normalmente tratado através de técnicas heurísticas e/ou algoritmos aproximativos, que apesar de não garantirem encontrar a solução ótima do problema, são capazes de retornar uma solução de qualidade em um tempo adequado para as necessidades da aplicação. Ressalta-se que dentre as heurísticas, merecem especial atenção as chamadas meta-heurísticas, que surgiram como uma alternativa para amenizar a dificuldade que os métodos heurísticos tem de escapar dos chamados ótimos locais. Sem essa dificuldade, as metaheurísticas podem partir em busca de regiões mais promissoras no espaço de soluções viáveis.

4.1 Problema de Alocação de Salas

O Problema de Alocação de Salas pode ser tratado como um Problema de Programação de Horários, mais precisamente como um Problema de Programação de Cursos Universitário (Course Timetabling), ou como um problema derivado deste (Classroom Assigment). Para a última situação, considera-se que as aulas dos cursos universitários já têm seus horários de início e de término definidos. O problema resume-se então na alocação das aulas às salas respeitando os horários destas aulas e outras restrições.

4.2 Modelagem do Problema

Para a representação de uma alocação (solução) do problema é