main

Relat´orio Final de Pesquisa Operacional
Caio Henrique Giolo Antunes - 2012.1.08.010
19 de junho de 2015

ii

Chapter 1
Gera¸
c˜ ao de Hor´ arios Escolares
O objetivo deste trabalho pr´ atico ´ e resolver o problema da gera¸c˜ ao de hor´ arios escolares que ´ e uma tarefa humanamente dif´ıcil e demorada que se agrava ainda mais com o aumento de complexidade do problema (Muitas turmas, muitos professores, muitas restri¸c˜ oes). Nesse sentido, esse problema pode ser modelado como um problema linear, e como todos os problemas lineares, pode ser resolvido utilizando modelos matem´ aticos que ao serem codificados com algoritmos como o SIMPLEX, ou no caso a implementa¸c˜ ao da
IBM (CPLEX) apresenta de forma relativamente r´ apida e exata uma solu¸c˜ ao para o problema, caso ela exista.

1. Instancia:
A instancia utilizada para implementa¸c˜ao deste trabalho utiliza como parˆametros:
- Numero de professores [P]: 27
- Numero de turmas [T]: 15
- Numero de hor´arios [H]: 6
- Quantidade de dias [D]: 5

2. Restri¸c˜ oes: As restri¸c˜oes para esse problemas s˜ao:
- Todas as necessidades de aulas da turma devem ser respeitadas;
- Um professor n˜ao pode estar em dois lugares ao mesmo tempo;
- Uma turma n˜ao pode ter mais de duas aulas com o mesmo professor no mesmo dia;
- As indisponibilidades dos professores devem ser respeitadas;
1

2

˜ DE HORARIOS
´
CHAPTER 1. GERAC
¸ AO
ESCOLARES

- Dois professores n˜ao podem ocupar o mesmo hor´ario para uma mesma turma; E finalmente, a fun¸c˜ao objetivo:
Maximizar o n´ umero de aulas dadas (preencher todos os hor´arios).

3. Modelagem:
Para modelar esse problema, ´e necess´ario a utiliza¸c˜ao de apenas uma vari´avel de decis˜ao que, neste trabalho, ´e representada com o uso de uma matriz de quatro dimens˜oes: X[D][H][T][P].
As indisponibilidades dos professores, em dado dia e hor´ario, ´e representada na matriz tridimensional I[D][H][P], onde ´e setado o valor ”1” quando o professor for indispon´ıvel. J´a as necessidades de cada turma