Aplicações de Otimização
em Processos Industriais
Maria Cristina N. Gramani
[email protected]
Departamento de Engenharia de Produção
Escola de Engenharia
Universidade Presbiteriana Mackenzie
IV Encontro de Iniciação Científica – VII Mostra de Pós-Graduação - Universidade Presbiteriana Mackenzie
Organização
Introdução à Otimização;
Tomada de Decisão
O Processo de Otimização
Níveis de Decisão;
Problemas Práticos envolvendo Otimização;
A Filosofia Just in Time;
Processo de Modelagem – Abordagens de
Resolução;
Estudos de Caso.
Maria Cristina N. Gramani – Departamento de Engenharia de Produção – Escola de Engenharia – Universidade Presbiteriana Mackenzie
IV Encontro de Iniciação Científica – VII Mostra de Pós-Graduação - Universidade Presbiteriana Mackenzie
Introdução à Otimização
OTIMIZAR:
obter o melhor resultado de;
planejar ou desenvolver com o máximo de eficiência
(especialmente uma atividade econômica).
A Otimização é uma área de estudos que utiliza computadores,
estatística e matemática (modelagem matemática).
Áreas de Atuação: Manufatura, Serviços, Finanças, entre
outros.
Maria Cristina N. Gramani – Departamento de Engenharia de Produção – Escola de Engenharia – Universidade Presbiteriana Mackenzie
IV Encontro de Iniciação Científica – VII Mostra de Pós-Graduação - Universidade Presbiteriana Mackenzie
Objetivos da Otimização
Converter dados em informações significativas
Transformar dados brutos
em informações gerenciais que
podem ser utilizadas no processo
de tomada de decisão.
Apoiar o processo de Tomada de Decisão
Criar sistemas computacionais úteis para os usuários
Maria Cristina N. Gramani – Departamento de Engenharia de Produção – Escola de Engenharia – Universidade Presbiteriana Mackenzie
IV Encontro de Iniciação Científica – VII Mostra de Pós-Graduação - Universidade Presbiteriana Mackenzie
Tomada de Decisão
O que é?
Processo de identificar um problema ou uma oportunidade e
selecionar uma linha de ação para resolvê-lo.
Quando?
Um problema ocorre no momento em que o estado atual de
uma situação é diferente do estado desejado;
Uma oportunidade ocorre quando as circunstâncias
oferecem a chance da organização ultrapassar seus
objetivos e/ou metas.
Maria Cristina N. Gramani – Departamento de Engenharia de Produção – Escola de Engenharia – Universidade Presbiteriana Mackenzie
IV Encontro de Iniciação Científica – VII Mostra de Pós-Graduação - Universidade Presbiteriana Mackenzie
Níveis de Decisão
• Metas
ESTRATÉGICO
• Objetivos
TÁTICO
Otimização
OPERACIONAL
Maria Cristina N. Gramani – Departamento de Engenharia de Produção – Escola de Engenharia – Universidade Presbiteriana Mackenzie
IV Encontro de Iniciação Científica – VII Mostra de Pós-Graduação - Universidade Presbiteriana Mackenzie
Aplicações Práticas –
Problema de Empacotamento
Arrumar a melhor maneira de agrupar um conjunto de itens
de modo que o espaço total necessário para guardá-los seja
minimizado. Em certos casos, o espaço disponível para o
armazenamento é predeterminado e o objetivo é guardar o
maior número de itens possível.
Maria Cristina N. Gramani – Departamento de Engenharia de Produção – Escola de Engenharia – Universidade Presbiteriana Mackenzie
IV Encontro de Iniciação Científica – VII Mostra de Pós-Graduação - Universidade Presbiteriana Mackenzie
Exemplo: Companhia de Mudanças
Uma companhia de mudanças deseja
encontrar a melhor maneira de arrumar as
caixas dentro dos seus caminhões de modo
a realizar a mudança com um número
mínimo de viagens.
Maria Cristina N. Gramani – Departamento de Engenharia de Produção – Escola de Engenharia – Universidade Presbiteriana Mackenzie
IV Encontro de Iniciação Científica – VII Mostra de Pós-Graduação - Universidade Presbiteriana Mackenzie
Escalonamento de Mão de Obra
Dado um conjunto de tarefas a realizar e um
conjunto de funcionários. Um empresário deseja
encontrar a melhor maneira de alocar seus
funcionários às tarefas de forma que todas as tarefas
sejam cumpridas e os gastos com mão de obra sejam
minimizados. Além disso, levando também em
consideração restrições trabalhistas e restrições
operacionais da empresa que afetam a forma que a
alocação pode ser realizada.
Maria Cristina N. Gramani – Departamento de Engenharia de Produção – Escola de Engenharia – Universidade Presbiteriana Mackenzie
IV Encontro de Iniciação Científica – VII Mostra de Pós-Graduação - Universidade Presbiteriana Mackenzie
Exemplo: Companhia Aérea
Em uma companhia aérea. É preciso decidir quais
viagens serão destinadas a quais pilotos e
ainda obedecer a regras do tipo:
1.
Um piloto não pode trabalhar mais de 8 horas
seguidas sem descanso;
2.
A cada três dias seguidos de trabalho todo
piloto deve ter um dia de descanso, entre
outros.
Maria Cristina N. Gramani – Departamento de Engenharia de Produção – Escola de Engenharia – Universidade Presbiteriana Mackenzie
IV Encontro de Iniciação Científica – VII Mostra de Pós-Graduação - Universidade Presbiteriana Mackenzie
Escalonamento de Tarefas
Em certas fábricas, um produto final é produzido a partir
da execução de pequenas tarefas. Estas tarefas possuem
regras de precedência entre si e particularidades que
exigem um ou outro tipo de máquina para sua execução.
Com isso, dado um conjunto de itens a produzir, deseja-se
descobrir, para cada máquina da fábrica, a ordem em que
as tarefas devem ser processadas de forma a minimizar o
tempo de produção.
Maria Cristina N. Gramani – Departamento de Engenharia de Produção – Escola de Engenharia – Universidade Presbiteriana Mackenzie
IV Encontro de Iniciação Científica – VII Mostra de Pós-Graduação - Universidade Presbiteriana Mackenzie
Exemplo: Sequenciamento de Padrões de
Estoque - Minimização de Pilhas Abertas
Padrão 1:
Padrão 2:
Padrão 1 -> Padrão 2:
Padrão 2 -> Padrão 1:
Maria Cristina N. Gramani – Departamento de Engenharia de Produção – Escola de Engenharia – Universidade Presbiteriana Mackenzie
IV Encontro de Iniciação Científica – VII Mostra de Pós-Graduação - Universidade Presbiteriana Mackenzie
Localização de Facilidades
Dado um conjunto de clientes que precisam ser
atendidos e um conjunto de possíveis locais para
instalação de facilidades, deseja-se determinar quais os
melhores locais para a instalação das facilidades de
forma que todos os clientes sejam atendidos nos prazos
predeterminados e a um custo mínimo.
Maria Cristina N. Gramani – Departamento de Engenharia de Produção – Escola de Engenharia – Universidade Presbiteriana Mackenzie
IV Encontro de Iniciação Científica – VII Mostra de Pós-Graduação - Universidade Presbiteriana Mackenzie
Exemplo: Instalação de Pronto-Socorros
A instalação de pronto-socorros
nas comunidades circunvizinhas
de uma grande área
metropolitana. O objetivo é não
ter paciente demorando mais que
10 minutos para chegar de sua
casa até uma sala de
emergência.
Maria Cristina N. Gramani – Departamento de Engenharia de Produção – Escola de Engenharia – Universidade Presbiteriana Mackenzie
IV Encontro de Iniciação Científica – VII Mostra de Pós-Graduação - Universidade Presbiteriana Mackenzie
Distribuição de Bens de Consumo
Dado um conjunto de fregueses que precisam receber
suas mercadorias, a fábrica deve decidir a quantidade
de carga a ser alocada em cada caminhão e quais
caminhões irão atender quais clientes. Para isso, devese levar em consideração otimizar as rotas dos
veículos.
Maria Cristina N. Gramani – Departamento de Engenharia de Produção – Escola de Engenharia – Universidade Presbiteriana Mackenzie
IV Encontro de Iniciação Científica – VII Mostra de Pós-Graduação - Universidade Presbiteriana Mackenzie
Exemplo: Abastecimento de
Supermercados
Um exemplo consiste no caso de abastecimento de
supermercados por uma fábrica de bebidas.
Maria Cristina N. Gramani – Departamento de Engenharia de Produção – Escola de Engenharia – Universidade Presbiteriana Mackenzie
IV Encontro de Iniciação Científica – VII Mostra de Pós-Graduação - Universidade Presbiteriana Mackenzie
Determinação de Saldos de Caixa
Problema: Encontrar o valor ótimo de conversão de títulos negociáveis em caixa.
Custos envolvidos:
•Custos de conversão: CPMF, IOF, ...
•Custos de Oportunidade: representa os juros que se deixa de
ganhar durante o período de tempo em que os fundos são
mantidos no caixa ao invés de estarem aplicados.
Obviamente:
•Níveis de caixa altos lucratividade menor;
•Níveis de caixa muito baixos risco de insolvência.
Maria Cristina N. Gramani – Departamento de Engenharia de Produção – Escola de Engenharia – Universidade Presbiteriana Mackenzie
IV Encontro de Iniciação Científica – VII Mostra de Pós-Graduação - Universidade Presbiteriana Mackenzie
Planejamento de Produção
Dado um horizonte de demanda por produtos, um
fabricante de determinado item de consumo precisa
decidir quanto deve produzir por mês de forma
atender toda a demanda e ainda minimizar os custos.
Limite de estocagem e um preço por quantidade de
produto estocado;
Data de validade dos produtos;
Atraso na entrega de mercadoria gera ônus.
Maria Cristina N. Gramani – Departamento de Engenharia de Produção – Escola de Engenharia – Universidade Presbiteriana Mackenzie
IV Encontro de Iniciação Científica – VII Mostra de Pós-Graduação - Universidade Presbiteriana Mackenzie
Desejo de uma empresa
Filosofia Just in Time !
Maria Cristina N. Gramani – Departamento de Engenharia de Produção – Escola de Engenharia – Universidade Presbiteriana Mackenzie
IV Encontro de Iniciação Científica – VII Mostra de Pós-Graduação - Universidade Presbiteriana Mackenzie
Just in Time - JIT
O JIT é um método de administração industrial japonês desenvolvido nos
anos 70, adotado primeiramente nas plantas industriais da Toyota por
Taiichi Ohno, o Pai do JIT.
O JIT tem como princípio eliminar fontes de fabricação de desperdícios,
adquirindo a quantidade certa de matérias-primas e produzindo a
quantidade certa de produtos no lugar certo no momento certo.
Mais uma filosofia do que uma técnica, ele se baseia na simples idéia de
que, sempre que possível, nenhuma atividade deve acontecer num sistema,
enquanto não houver necessidade dela. Desta forma, nenhum componente
deve ser pedido enquanto não houver necessidade.
Maria Cristina N. Gramani – Departamento de Engenharia de Produção – Escola de Engenharia – Universidade Presbiteriana Mackenzie
IV Encontro de Iniciação Científica – VII Mostra de Pós-Graduação - Universidade Presbiteriana Mackenzie
Just in Time - JIT
Os defensores do JIT tendem a colocar um peso maior no
custo de carregar estoques.
estoques
são
um
recurso
Em sua perspectiva, os
utilizado
para
esconder
ineficiências nos sistemas de produção e distribuição.
Usando a famosa analogia do lago, os defensores do JIT
argumentam que ao se baixar o nível de água (estoques),
as pedras aparecem, (problemas ou deficiências em
qualidade, fornecedores não-confiáveis, gargalos, demanda
volátil, previsões imprecisas, etc.).
Maria Cristina N. Gramani – Departamento de Engenharia de Produção – Escola de Engenharia – Universidade Presbiteriana Mackenzie
IV Encontro de Iniciação Científica – VII Mostra de Pós-Graduação - Universidade Presbiteriana Mackenzie
Limitações do JIT
Requer flexibilidade do sistema produtivo, no que se refere à
variedade dos produtos oferecidos ao mercado e à variação da
procura a curto prazo.
Caso a procura seja muito instável, há a necessidade de manutenção
de estoques de produtos acabados a um nível tal que permita que a
procura efetivamente sentida pelo sistema produtivo tenha certa
estabilidade.
Também a redução do estoque pode aumentar o risco de interrupção
da produção em função de problemas de gestão de mão-de-obra,
como, por exemplo, greves tanto na fábrica como nos fornecedores.
Maria Cristina N. Gramani – Departamento de Engenharia de Produção – Escola de Engenharia – Universidade Presbiteriana Mackenzie
IV Encontro de Iniciação Científica – VII Mostra de Pós-Graduação - Universidade Presbiteriana Mackenzie
Lote Econômico de Compra - LEC
O LEC é uma técnica que consiste em encontrar um
tamanho de lote que minimize os custos de processar o
pedido
(transporte,
avaliação
de
crédito,
setup
equipamentos, etc.) e os custos de carregar estoques.
Custo total =
Custo de armazenagem + custo do pedido
Custos
Custo de
armazenagem
Custo do pedido
LEC
Quantidade
Maria Cristina N. Gramani – Departamento de Engenharia de Produção – Escola de Engenharia – Universidade Presbiteriana Mackenzie
de
IV Encontro de Iniciação Científica – VII Mostra de Pós-Graduação - Universidade Presbiteriana Mackenzie
Processo de Modelagem
AMBIENTE/
REALIDADE
MODELAGEM
FERRAMENTAS
Contexto onde uma determinada situação gera a
necessidade de análise e tomada de decisão.
Maria Cristina N. Gramani – Departamento de Engenharia de Produção – Escola de Engenharia – Universidade Presbiteriana Mackenzie
IV Encontro de Iniciação Científica – VII Mostra de Pós-Graduação - Universidade Presbiteriana Mackenzie
Processo de Modelagem
AMBIENTE/
REALIDADE
MODELAGEM
FERRAMENTAS
Uma representação simplificada
ou abstração da realidade.
MAQUETES – MODELOS ANÁLOGOS –
MODELOS MATEMÁTICOS
Maria Cristina N. Gramani – Departamento de Engenharia de Produção – Escola de Engenharia – Universidade Presbiteriana Mackenzie
IV Encontro de Iniciação Científica – VII Mostra de Pós-Graduação - Universidade Presbiteriana Mackenzie
Processo de Modelagem
AMBIENTE/
REALIDADE
MODELAGEM
FERRAMENTAS
Pesquisa operacional:
Programação Linear e Não Linear, Inteira
Algoritmos Genéticos
Inteligência Artificial
Maria Cristina N. Gramani – Departamento de Engenharia de Produção – Escola de Engenharia – Universidade Presbiteriana Mackenzie
IV Encontro de Iniciação Científica – VII Mostra de Pós-Graduação - Universidade Presbiteriana Mackenzie
AMBIENTE/
REALIDADE
• João Jr. é gerente de logística de uma fábrica de
refrigerantes. A fábrica possui 2 depósitos localizados de
forma a atender a demanda em 3 centros consumidores.
• João Jr. precisa decidir “como” escoar os refrigerantes
estocados nos depósitos para os centros com o
Mínimo Custo.
Maria Cristina N. Gramani – Departamento de Engenharia de Produção – Escola de Engenharia – Universidade Presbiteriana Mackenzie
IV Encontro de Iniciação Científica – VII Mostra de Pós-Graduação - Universidade Presbiteriana Mackenzie
MODELAGEM
Depósito
Centro
Consumidor
1
1
1. Alcançar o menor
custo de transporte;
2. Satisfazer exatamente
as quantidades
2
2
demandas;
3. Não exceder a
3
capacidade dos
depósitos.
Maria Cristina N. Gramani – Departamento de Engenharia de Produção – Escola de Engenharia – Universidade Presbiteriana Mackenzie
IV Encontro de Iniciação Científica – VII Mostra de Pós-Graduação - Universidade Presbiteriana Mackenzie
FERRAMENTAS
Após a construção de um modelo matemático, podemos analisálo através de métodos computacionais (algoritmos), tentando
encontrar a melhor solução.
PESQUISA OPERACIONAL: Resolução de problemas de
otimização (não apenas industriais), através de :
MODELOS MATEMÁTICOS + MÉTODOS COMPUTACIONAIS
Pode ocorrer alterações como:
aumento de centros e depósitos
alteração do custo
Maria Cristina N. Gramani – Departamento de Engenharia de Produção – Escola de Engenharia – Universidade Presbiteriana Mackenzie
IV Encontro de Iniciação Científica – VII Mostra de Pós-Graduação - Universidade Presbiteriana Mackenzie
Estudo de Caso 1
Problema de Distribuição
Uma empresa fabricante de bicicletas possui duas fábricas localizadas em Campinas e em
Volta Redonda. A produção da empresa deve ser entregue aos Centros de Distribuição
localizados em Osasco, Natal, S.J. dos Campos e Curitiba, e estes devem abastecer a
demanda de BH, RJ, SP, Salvador e Fortaleza. Custos: frete! QUESTÃO!
Produção
CD
Demanda
10.000
Belo Horizonte
Osasco
30.000
Rio de Janeiro
Campinas
15.000
Natal
São Paulo
S.J.Campos
Salvador
25.000
10.000
15.000
Volta Redonda
Curitiba
Fortaleza
5.000
Maria Cristina N. Gramani – Departamento de Engenharia de Produção – Escola de Engenharia – Universidade Presbiteriana Mackenzie
IV Encontro de Iniciação Científica – VII Mostra de Pós-Graduação - Universidade Presbiteriana Mackenzie
Estudo de Caso 1
Utilizando o Solver do Excel
Produção 1
Produção 2
CD 1
CD 2
CD 3
CD 4
Demanda 1
Demanda 2
Demanda 3
Demanda 4
Demanda 5
F11
F12
F13
F14
F21
F22
F23
F24
f11
f12
f13
f14
f15
f21
f22
f23
10,000 5,000 15,000
0
0
0
25,000
0
0
0
10,000
0
0
0
0
0
8,105,250 24.00 200.00 28.00 48.00 45.66 322.47 39.34 80.46 76.70 66.70 25.00 250.00 291.70 395.84 423.58 529.16
30,000
1
1
1
1
25,000
1
1
1
1
0
1
1
-1
-1
-1
-1
-1
0
1
1
-1
-1
-1
0
1
1
0
1
1
10,000
1
1
15,000
1
1
10,000
1
1
15,000
1
5,000
1
Maria Cristina N. Gramani – Departamento de Engenharia de Produção – Escola de Engenharia – Universidade Presbiteriana Mackenzie
IV Encontro de Iniciação Científica – VII Mostra de Pós-Graduação - Universidade Presbiteriana Mackenzie
Estudo de Caso 1
Solução
Produção
Demanda
CD
10.000
Belo Horizonte
10.000
Osasco
10.000
30.000
Campinas
15.000
5.000
Natal
10.000
10.000
São Paulo
15.000
S.J.Campos
15.000
15.000
Salvador
25.000
25.000
15.000
Rio de Janeiro
5.000
Volta Redonda
Curitiba
5.000
Fortaleza
Maria Cristina N. Gramani – Departamento de Engenharia de Produção – Escola de Engenharia – Universidade Presbiteriana Mackenzie
IV Encontro de Iniciação Científica – VII Mostra de Pós-Graduação - Universidade Presbiteriana Mackenzie
Estudo de Caso 2
Problema de Localização
O MetroHealth Hospital gostaria de posicionar um serviço de emergência nas comunidades
circunvizinhas da grande área metropolitana na qual atua. O objetivo é não ter paciente
demorando mais que 10 minutos para chegar até uma sala de emergência. Os tempos
estimados para um paciente dirigir em minutos para localizações potenciais são :
da vizinhança
A
B
C
D
E
F
Para locais potenciais de sala de emergência
1
2
3
4
5
0
5
15
25
25
5
0
20
30
15
15
20
0
10
25
25
30
10
0
10
25
15
25
10
0
15
5
15
20
9
6
15
5
15
20
9
0
Qual o número mínimo de salas de emergência e onde elas devem estar localizadas?
Maria Cristina N. Gramani – Departamento de Engenharia de Produção – Escola de Engenharia – Universidade Presbiteriana Mackenzie
IV Encontro de Iniciação Científica – VII Mostra de Pós-Graduação - Universidade Presbiteriana Mackenzie
Estudo de Caso 2
Solução
da vizinhança
A
B
C
D
E
F
Para locais potenciais de sala de emergência
1
2
3
4
5
6
0
5
15
25
25
15
5
0
20
30
15
5
15
20
0
10
25
15
25
30
10
0
10
20
25
15
25
10
0
9
15
5
15
20
9
0
1º Passo: Observar quais são os locais de sala de emergência que estão dentro do tempo
de deslocamento de 10 minutos.
Local
potencial
1
2
3
4
5
6
Vizinhança
A,B
A, B, F
C, D
C, D, E
D, E, F
B, E, F
Restrições:
x1+x2
1 (restrição do local 1)
x1+x2+
x6 1 (restrição do local 2)
1 (restrição do local 3)
x3+x4
x3+x4+x5
1 (restrição do local 4)
x4+x5+x6 1 (restrição do local 5)
x2+
x5+x6 1 (restrição do local 6)
Todos os x’s 0 ou 1.
Objetivo: Min x1+x2+x3+x4+x5+x6
Solução: utilizando um solver encontramos x2=1 e x4=1,
significando que as salas de emergência devem ser colocadas nas localizações 2 e 4.
Maria Cristina N. Gramani – Departamento de Engenharia de Produção – Escola de Engenharia – Universidade Presbiteriana Mackenzie
IV Encontro de Iniciação Científica – VII Mostra de Pós-Graduação - Universidade Presbiteriana Mackenzie
PERGUNTAS ???
Maria Cristina N. Gramani – Departamento de Engenharia de Produção – Escola de Engenharia – Universidade Presbiteriana Mackenzie