problema de alocação de salas e laboratorios no ifc sbs utilizando PLIM

Prévia do material em texto

Problema de Alocação de Salas e Laboratórios no IFC SBS utilizando Programação 
Inteira 
 
Problem Allocation of Rooms and Laboratories in IFC SBS using Integer 
Programming 
 
 
Autores: ​Bruno Alexandre Gomes de SOUZA​; Edgar Della GIUSTINA; Vitor Teles CORREIA; 
 
Identificação autores: IFC - São Bento do Sul Edital (015/2018);Engenharia de Controle e 
Automação;Orientador IFC-Campus São Bento do Sul;Orientador IFC-Campus São Bento do Sul; 
 
RESUMO 
 
Esse trabalho visa mostrar um formato novo para as acomodações de salas de 
aulas e laboratórios do IFC São Bento do Sul para melhorar a eficácia na utilização dos 
espaços com auxílio de modelagem matemática computacional. Até o momento os 
resultados encontrados são limitados para cada horário. 
 
Palavras-chave: Alocação de Salas; Programação Inteira; Otimização. 
 
 
 
ABSTRACT 
 
This paper aims to show a new format for the accommodation of IFC São Bento do Sul's 
classrooms and laboratories to improve the efficiency in the use of spaces with the aid of 
computational mathematical modeling. So far the results are limited for each time. 
 
Keywords: ​Room Allocation; Whole Programming; Optimization 
 
 
INTRODUÇÃO E JUSTIFICATIVA 
 
Na preparação para o próximo ano letivo as escolas sempre encaram o mesmo 
problema para montar o horário respeitando a distribuição das turmas considerando todas 
as limitações de salas de aulas, laboratórios, horários dos professores e particularidades 
dos estudantes (Wendt & Müller, 2017). Em alguns casos, essa questão é solucionada de 
forma manual, demorando bastante tempo para chegar numa solução e nem sempre se 
consegue a eficácia esperada. Em outros casos, são utilizados programas prontos que 
não contém todas as restrições necessárias para atender cada instituição (Sales, 2015). 
Esse problema também será enfrentado no IFC de São Bento do Sul, especialmente por 
ter aumentado a oferta de cursos e por seu espaço físico não ter crescido no mesmo 
passo. Este trabalho apresenta a metodologia utilizada, os resultados encontrados até o 
momento e os comentários com base nesses resultados. 
 
 
METODOLOGIA 
 
Para que uma solução ótima fosse encontrada, a técnica de modelagem PLIM foi 
utilizada para o desenvolvimento do modelo do problema de alocação, e tendo como base 
a forma de modelar o problema de alocação abordado por Hillier e Lieberman (2006), o 
seguinte modelo inicial foi obtido: 
inimizar Z Xm = ∑
14
i=1
∑
14
j=1
P ij ij 
Onde, é a função para ser minimizada,i é o número de espaços didáticosZ 
disponíveis (incluindo laboratórios e a quadra poliesportiva), j é as 9 turmas do ensino 
médio mais 5 turmas fantasmas, são os pontos de penalização definidos para cada P ij 
ambiente, e é a variável de decisão binária que está sujeita às seguintes condições​:X ij 
, asoasalasuporteaquelaturmanohoráriodef inidoX ij = 1 c 
, asoasalanãosuporteaatividadequeserádesenvolvidaX ij = 0 c 
Onde uma matriz cruzando as turmas reais e fantasmas com os ambientes 
disponíveis pode ser montada com i linhas e j colunas, as restrições do modelo se tornam 
as seguintes: 
comivariandode1até14Li = ∑
14
j=1
X ij = 1 
comjvariandode1até14C j = ∑
14
i=1
X ij = 1 
 
Em que são as colunas e as linhas das variáveis de decisão em uma matriz C j Li 
Espaços vs Turmas. 
 
RESULTADOS E DISCUSSÕES 
 
 
Um teste do modelo atual foi feito, em uma simulação em que existe 7 salas e 7 
laboratórios disponíveis e 9 turmas para ocupar este espaço. A matriz de penalizações 
ficou da seguinte forma: 
 
Tabela 1: Matriz de penalizações 
 
 
Nesta tabela percebemos algumas penalizações muito grandes, e elas tem o propósito de 
afastar as variáveis binárias daquelas possíveis alocações. Realizando o procedimento de 
Otimização através do solver, obtém-se: 
 
Tabela 2: Matriz de variáveis binárias 
 
 
Com a visualização destas matrizes é possível ver a capacidade de se otimizar a 
alocação das turmas no campus, tendo mais espaços livres. Na matriz binária, é possível 
identificar que vários espaços foram alocados para turmas virtuais, mostrando com o 
campus possui vários ambientes em estado ocioso. Em contrapartida, o resultado não se 
compara aos resultados encontrados por Sales (2015), Ou como Wendt e MÜLLER 
(2017), por alguns fatores, como tempo para o desenvolvimento da pesquisa e as 
limitações do método utilizado. O principal desafio será a tentativa de otimizar múltiplos 
horários de forma simultânea e realizar a implementação via Excel, de forma que do ponto 
de vista institucional, seja um projeto viável. 
 
 
CONSIDERAÇÕES FINAIS 
 
Fica claro que o modelo proposto já é capaz de otimizar a alocação dos espaços 
didáticos da instituição. Até o presente momento há uma limitação que possibilita a 
otimização apenas um horário da instituição por vez, e sendo necessária uma 
readequação de toda a matriz de penalizações, demonstra que mesmo ele sendo capaz 
de otimizar, demanda um trabalho que torna sua implementação a nível institucional 
inviável, dito isto, os próximos passos são a correção dessas falhas do modelo e sua 
validação e implementação. 
 
 
REFERÊNCIAS 
 
LIEBERMAN, G. J. Introdução à pesquisa operacional. 9. ed. Porto Alegre: AMGH, 2012. 
1028p. 
 
SALES, Elijeane dos Santos. ​Problema de Alocação de Salas e a otimização dos 
Espaços no centro de tecnologia da UFSM​. 2015. 119 p. Dissertação (Mestrado em 
Administração)- Universidade Federal de Santa Maria, Santa Maria, 2015. Disponível em: 
<https://repositorio.ufsm.br/bitstream/handle/1/4751/SALES%2c%20ELIJEANE%20DOS%
20SANTOS.pdf?sequence=1&isAllowed=y>. Acesso em: 26 set. 2018. 
 
WENDT, J. F. M.; MÜLLER, F. M. Solução do Problema de Alocação de salas utilizando 
um Modelo Matemático Multi-índice. In: SIMPÓSIO BRASILEIRO DE PESQUISA 
OPERACIONAL, 49., 2017, Blumenau. Anais... Blumenau: SBPO, 2011. p. 790-797.