Estudo de caso de programação inteira para automação de grade de horários do departamento de estatística da Universidade Federal de Pernambuco

Resumo

A otimização de grade de horários é um problema de grande interesse e muitos algoritmos foram desenvolvidos nos últimos anos [1, 2, 3, 4], principalmente para o caso particular de cursos de graduação. Neste trabalho, descreve-se uma aplicação de otimização combinatória para a automação da grade de horários dos professores do departamento de estatística da Universidade Federal de Pernambuco. Considera-se o problema, semestral, de alocação de professores à disciplinas de acordo com suas preferências individuais e satisfazendo a uma série de restrições. As variáveis de decisão consideram os seguintes conjuntos (com respectivas dimensões): professor (40), a disciplina (50), o dia (5), o turno (3), o período (2) e a sala onde será ministrado o curso (15). O departamento oferece disciplinas de duas naturezas: internas e externas. As disciplinas internas são aquelas relacionadas ao curso de graduação e de responsabilidade do departamento, de modo que se tem flexibilidade na determinação de horários e salas. As disciplinas externas podem ser de dois tipos: as ministradas em outros cursos com horários predefinidos, sendo permitido apenas a escolha do professor; e as ministradas ao curso de graduação em estatística por outros departamentos, com horários pré-definidos e nos quais não se pode alocar outras disciplinas. A preferência dos professores por disciplina é estabelecida por meio de uma relação de preferência (ordinal) dos professores a partir de um questionário me que cada professor selecionará um subconjunto próprio das possíveis disciplinas, de cardinalidade predefinida e bem menor que o número total de disciplinas, e estabelecerá uma ordem neste subconjunto. A variável de decisão, x[i, j, k, l,m, n], binária, assumirá valor 1 se o professor i for alocado para a disciplina j no dia k, no turno l, no período m e na sala n; e valor zero caso contrário. Precisaremos das seguintes estruturas: . p[i, j]. (parâmetro) Utilidade ordinal do professor i em relação à disciplina j. Representa a preferência do professor para com as disciplinas. Note-se que ele precisa atribuir um valor diferente de zero apenas para um subconjunto próprio de disciplinas. . y[i, j]. (variável auxiliar). Variável binária que determina se o professor i será alocado na disciplina j. z[j, k]. (variável auxiliar). Variável binária que determina se a disciplina j será ministrada no dia k. Em relação aos professores, temos as seguintes características: (i) Professores que deverão ser alocados a uma única disciplina, devido à atividades em cargos administrativos, disciplinas na pós-graduação, ou outras questões previstas na legislação. (ii) Professores que deverão ser alocados em duas disciplinas (Limite inferior para professores com atividades de pesquisa ou de extensão). (iii) Professores substitutos de 20h e 40h. Em relação as restrições, pode-se citar como principais: . Número de disciplinas por professor; . Toda disciplina oferecida deve ser associada a um professor; . Não alocar professores em turnos extremos; . Não alocar disciplinas em turnos diferentes; . Toda disciplina ocupa dois períodos. . Distâncias entre aulas de dois ou três dias; . Disciplinas externas com horários fixos; . Respeitar horário utilizados por outras disciplinas; Finalmente, deve ser considerado no funcional objetivo características como (i) Maximizar a oferta de disciplinas aos alunos; (ii) Minimizar o número de dias de aula dos professores (ou maximizar, se o professor preferir aulas esparsas na semana); (iii) Maximizar as preferências por disciplinas dos professores.