Formulações e algoritmos para o problema de programação de horários em escolas

UNIVERSIDADE FEDERAL FLUMINENSE

Haroldo Gambini Santos

Formulações e Algoritmos para o Problema de
Programação de Horários em Escolas

´
NITEROI
2007

UNIVERSIDADE FEDERAL FLUMINENSE

Haroldo Gambini Santos

Formulações e Algoritmos para o Problema de
Programação de Horários em Escolas

Tese de Doutorado submetida ao Programa de P´s-Gradua¸˜o em Computa¸˜o da Unio ca ca versidade Federal Fluminense como requisito parcial para a obten¸˜o do t´ ca ıtulo de Doutor.
´
Area de concentra¸˜o: Otimiza¸˜o Combinaca ca t´ria e Inteligˆncia Artificial. o e

Orientador:

Luiz Satoru Ochi
Co-orientador:

Eduardo Uchoa

´
NITEROI
2007

Formula¸˜es e Algoritmos para o Problema de Programa¸˜o de Hor´rios co ca a em Escolas
Haroldo Gambini Santos

Tese de Doutorado submetida ao Programa de
P´s-Gradua¸˜o em Computa¸˜o da Universio ca ca dade Federal Fluminense como requisito parcial para a obten¸˜o do t´ ca ıtulo de Doutor.

Aprovada por:

Prof. D.Sc. Luiz Satoru Ochi / UFF (Presidente)

Prof. Ph.D. Abilio Pereira de Lucena Filho / UFRJ

Prof. D. Hab. Celso da Cruz Carneiro Ribeiro / UFF

Prof. D.Sc. Eduardo Uchoa / UFF

Prof. D.Sc. Marcone Jamilson Freitas Souza / UFOP

Prof. D. Hab. Nelson Maculan Filho / UFRJ

Prof. D.Sc. Simone de Lima Martins / UFF

Niter´i, 30 de Mar¸o de 2007. o c

Para Hique, respons´vel pelos “´timos globais” de felicidade da minha vida. a o
Haroldo Gambini Santos

Agradecimentos

Agrade¸o ` minha fam´ ca ılia: meus pais Neusa e Fl´vio e meu irm˜o Henrique, fontes a a de carinho e motiva¸˜o nessa jornada. Ao Henrique, por ter sido o melhor irm˜o que se ca a pode ter durante a abreviada e intensa passagem dele por esse mundo.
Ao professor Satoru, pela acolhida na UFF e pela orienta¸˜o desde o in´ desse trabaca ıcio lho, obrigado por acreditar em mim. Ao professor Uchoa, por aceitar a orienta¸˜o desse ca trabalho e por participar ativamente desta pesquisa.