Introdução
Diversos problemas práticos recorrentes na indústria, empresas de prestação de serviços e poder público envolvem a busca pela melhor maneira de se distribuir recursos operacionais em uma grade horária. Grupos de professores, médicos, enfermeiras, policiais, entre outros, devem coordenar seu trabalho em horários pré-estabelecidos e periódicos, de maneira a minimizar o número de "janelas" (i.e. horários vagos, onde há subutilização dos recursos).
Problemas como estes podem ser modelados satisfatoriamente usando ZOIP (Zero-one integer programming), ou programação inteira com variáveis booleanas (campo de estudo que pertence portanto à Programação Linear Inteira).
Objetivos
O objetivo principal deste trabalho foi estudar e apresentar as formulações, aplicações, algoritmos conhecidos e seus fatores limitantes, para a modelagem descrita acima, a partir de [1], referência principal para este trabalho.
Também foi construído um protótipo a partir dos modelos estudados, visando resolver a instância do problema relacionada à alocação de salas de aula para professores.
Atividades realizadas
- Estudo da modelagem teórica "Horótimo", desenvolvida pelo prof. Ricieri, que visa elaborar uma grade horária para escolas [2];
- Documentação do trabalho em blog pessoal na rede social da USP, Stoa [3];
- Obtenção de uma licença de estudante para o ambiente Lingo [4];
- Modelagem do problema descrito acima, em Lingo e por fim em Mathprog, idioma do solver GLPK [5];
- Leitura da bibliografia.
Estrutura da monografia
A monografia foi elaborada e organizada conforme as regras da disciplina, listadas em [6].
Referências
- [1] Bertsimas & Tsitsiklis, Introduction to Linear Optimization, Athena Scientific, 1997.
- [2] Curso Prandiano. Disponível em: http://www.prandiano.com.br
- [3] Blog pessoal na rede STOA/USP. Disponível em http://noo.stoa.usp.br/lion/blog
- [4] Lingo Optimization Modeling Software. Disponível em: http://www.lindo.com/index.php?option=com_content&view=article&id=2&Itemid=10.
- [5] Andrew Makhorin. Glpk (gnu linear programming kit). Disponível em http://www.gnu.org/s/glpk/
- [6] Roteiro para preparação de monografias. Disponível em: http://www.ime.usp.br/~cef/mac499-11/rot-monografias.html
