Otimização de Processos
COQ 897
• Prof. Evaristo C. Biscaia Jr.
• Prof. Príamo A. Melo Jr.
Trabalho Final do Curso – 3º Período 2002
Utilização de Algoritmos Naturais
no Planejamento Seqüencial
da Produção em Plantas Seriais
Multiproduto Operando em Regime
de Batelada
Aluno: Alexandre Rodrigues Tôrres
Tópicos do Trabalho
• Introdução
• Descrição do Problema de Planejamento da
Produção
• Implementação e Testes dos Algoritmos de Busca da
Seqüência Ótima
• Emprego dos Algoritmos SA e ACO na solução de
Problemas de Programação da Produção
• Comparação com resultados da literatura
• Conclusões
Introdução
• Novas Tecnologias – Automação e
Informatização
• Produtos com alto valor agregado
• Plantas Químicas — ‘Química Fina’
• Problemas de PPCP
• Aplicativos para ERP’s
• Emprego de Algoritmos Naturais (SA e ACO)
Tópicos do Trabalho
• Introdução
• Descrição do Problema de Planejamento da
Produção
• Implementação e Testes dos Algoritmos de Busca da
Seqüência Ótima
• Emprego dos Algoritmos SA e ACO na solução de
Problemas de Programação da Produção
• Comparação com resultados da literatura
• Conclusões
Descrição do Problema de
Planejamento da Produção
• Programação da Produção
– ordens de fabricação – jobs
– recursos disponíveis – equipamentos
• Objetivo – menor make span
– sem estoques intermediários
– com estoques intermediários
• limitados
• ilimitados
Descrição do Problema de
Planejamento da Produção
• Formas de Avaliação dos PPP –
GRAVES(1981)
– geração de pedidos;
– complexidade do processo produtivo;
– critérios de programação.
Descrição do Problema de
Planejamento da Produção
• Geração de Pedidos
– reposição de estoques de produto acabado ou a
chamada produção empurrada (make to stock ou
closed shop)
– atendimento aos pedidos dos clientes, com a
reposição de estoques em sentido contrário ao
fluxo de produção ou produção puxada (make to
order ou open shop)
Descrição do Problema de
Planejamento da Produção
• Complexidade do Processos
– um estágio, um processador para cada ordem de
fabricação;
– um estágio, processadores paralelos;
– múltiplos estágios e mesma seqüência (flow shop ou
planta multiproduto);
– múltiplos estágios e várias seqüências (job shop ou
planta multiprocesso).
• multipropósito — multiproduto ou multiprocesso
Descrição do Problema de
Planejamento da Produção
• Critérios de Programação
– existência de estoques intermediários limitados ou
ilimitados
– possibilidades de formar seqüências e suas
influência nos tempos de preparação dos recursos
(setups dos equipamentos)
– existência de seqüências proibidas.
Descrição do Problema de
Planejamento da Produção
• Abordagem do PPP
– regras de prioridade;
– otimização combinatorial;
– análise de restrições
• Abordagem neste trabalho
– otimização combinatorial com o emprego de
algoritmos estocásticos de busca global
Tópicos do Trabalho
• Introdução
• Descrição do problema de planejamento da
produção
• Implementação e testes dos algoritmos de busca da
seqüência ótima
• Emprego dos algoritmos SA e ACO na solução de
problemas de programação da produção
• Comparação com resultados da literatura
• Conclusões
Implementação e Testes dos
Algoritmos de Busca da Seqüência
Ótima
• Algoritmos testados
– Recozimento Simulado (SA – Simulated
Annealing)
– Colônia de Formigas (ACO – Ant Colony
Optimization)
• Ambiente / Linguagem = MathCAD®
Implementação e Testes dos
Algoritmos de Busca da Seqüência
Ótima
• Características dos Algoritmos
SA – Recozimento Simulado
Entrada
(Requisitados)
Saída
(Resultados)
ACO – Colônia de Formigas
x – vetor inicial;
f – função objetivo;
T – ‘temperatura’ inicial;
 – fator de redução da ‘temperatura’;
nx – número de ciclos em x;
nT – número de ciclos para ‘temperatura’.
n – dimensão do problema;
m – número de ‘formigas’;
N – número de ciclos para busca;
 – expoente de peso na probabilidade
relacionado à quantidade de ‘feromônio’;
 – expoente de peso na probabilidade
relacionado à ‘distância’;
 – fator de evaporação do ‘feromônio’;
T0 – quantidades iniciais de ‘feromônio’
Q – numerador de normalização da distância
total para acréscimo do ‘feromônio’;
D – matriz das ‘distâncias’ entre cada
dimensão da solução.
– valor da função objetivo no ponto ótimo;
– vetor x correspondente ao ponto ótimo
– valor da função objetivo no ponto ótimo;
– vetor x correspondente ao ponto ótimo
Implementação e Testes dos
Algoritmos de Busca da Seqüência
Ótima
• Problema Teste: Problema do Caixeiro
Viajante (PCV)
20 15
30 35
20 60
PC
45 75
55 50
85 55
80 25
55 30
• Solução do PCV proposto
Implementação e Testes dos
Algoritmos de Busca da Seqüência
Ótima
Soluç ão do PC V c om 8 c idades
90
55
85
80
75
70
60
TP1
i2
TP2
i2
50
40
35
30
20
10
10
20
30
40
TP1
50
60
 TP2
i1
i1
70
80
90
Implementação e Testes dos
Algoritmos de Busca da Seqüência
Ótima
• Exemplos de Soluções do SA e ACO
p0
1
2 29 .76 9 1 1
5
6
0
8 2
4
7
0
7 7
3
0
6 8
0
5 6
8
0
4 5
2
0
3 4
5
0
2 3
4
S
A nn neal in gp
( 0 f  6 0 0 .80 2 00 2 0)
S
3
2
6
A CO 8  5  2 0 1  5  0 .5 1 0  1 00 D 
1
8
7
6
2 29 .76 9
A solução do PCV corresponde a um ciclo fechado ótimo portanto a solução
(5,4,3,2,1,8,7,6), obtida com o algoritmo ACO é idêntica a (1,8,7,6,5,4,3,2) obtida
pelo algoritmo SA.
Tópicos do Trabalho
• Introdução
• Descrição do problema de planejamento da
produção
• Implementação e testes dos algoritmos de busca da
seqüência ótima
• Emprego dos algoritmos SA e ACO na solução de
problemas de programação da produção
• Comparação com resultados da literatura
• Conclusões
Emprego dos algoritmos SA e
ACO na solução de PPP
• Estrutura de dados do PPP
• Entrada idêntica ao PCV
• Características do PPP:
– número de ordens de fabricação ou jobs (j);
– número de máquinas ou equipamentos (m);
– tempo de operação de cada job em cada
equipamento (top)
Emprego dos algoritmos SA e
ACO na solução de PPP
• Critérios de Programação Testados
– não existência de estoques intermediários (WIS –
without intermediate stocks);
– existência de estoques intermediários com
limitações (LIS – limited intermediate stocks);
– existência de estoques intermediários ilimitados
(UIS – unlimited intermediate stocks).
• Não foram testadas as influências dos tempos de
setup e a existência de seqüências proibidas
Emprego dos algoritmos SA e
ACO na solução de PPP
• PPP TESTE básico
–
–
–
–
8 ordens de produção
4 equipamentos
nível de complexidade: flow shop
critérios de programação: WIS, LIS e UIS
Emprego dos algoritmos SA e
ACO na solução de PPP
• Matriz de tempos de operação do PPP TESTE
4 3 2 1
12 3 4 4
1 2 3 4
t op
2 4 5 8
11 3 4 6
2 4 5 6
6 7 8 9
1 2 3 8
Emprego dos algoritmos SA e
ACO na solução de PPP
• Cenários verificados com o PPP TESTE
Cenários
Estoques Intermediários
Tipo
Função Objetivo
FS01
Sem
WIS
MS
FS02
Limitado (no equipamento)
LIS
MS
FS03
Limitado (no equipamento)
LIS
MS + EU
FS04
Limitado – único
(fora do equipamento)
LIS
MS
FS05
Limitado – único
(fora do equipamento)
LIS
MS + EU
FS07
Ilimitado
UIS
MS
MS = make span; EU = estoque utilizado
Emprego dos algoritmos SA e
ACO na solução de PPP
• Resultados com o SA e ACO
Cenário
s
FS01
MS
EU
Exemplo de Seqüência
59
0
(8,4,5,6,7,2,3,1)
FS02
53
27
(3,8,4,7,5,6,2,1)
FS03
57
11
(3,1,8,4,7,5,2,6)
FS04
52
24
(8,6,4,7,2,5,3,1)
FS05
55
11
(8,4,5,6,7,2,3,1)
FS07
52
31
(8,6,4,7,2,5,3,1)
Emprego dos algoritmos SA e
ACO na solução de PPP
• Gráfico de Gantt para o problema denominado Teste, sem estoques
intermediários, com a melhor solução obtida representando um make span
de 59 unidades de tempo (FS01).
Emprego dos algoritmos SA e
ACO na solução de PPP
• Gráfico de Gantt para o problema denominado Teste, com estoques
intermediários limitados, com a melhor solução obtida representando um
make span de 52 unidades de tempo e uma utilização total de estoque de
31 unidades de tempo(FS07).
Emprego dos algoritmos SA e
ACO na solução de PPP
• Análise dos Resultados do PPP TESTE
Emprego dos algoritmos SA e
ACO na solução de PPP
• Exemplo de evolução da solução, do problema Teste, em uma dada
execução da rotina do método Simulated Annealing (SA) no MathCAD
com os seguintes parâmetros:
AnnnealingG ( p0  FO  5 0.01 0.90 200 20)
HR
Ev oluç ão da Soluç ão - Problem a Tes te - SA
(F S07)
80
70
HR
is  1
60
52
50
40
0
500
1000
1500
2000
is
2500
3000
3500
4000
Emprego dos algoritmos SA e
ACO na solução de PPP
• Exemplo de evolução da solução, do problema Teste, em uma dada
execução da rotina do método Ant Colony Optimization (ACO) no
MathCAD com os seguintes parâmetros:
6
SACO ACO 8 5 200 1 2 0.6 10  100 Dop
Ev oluç ão da Soluç ão - ProblemaTest e - ACO (FS07)
65
60
SACO
9  is
55
52
50
0
20
40
60
80
100
is
120
140
160
180
200
Emprego dos algoritmos SA e
ACO na solução de PPP
• Testes com o SA:
– ‘Temperatura’ inicial
– Vizinhança
– Número de iterações
Emprego dos algoritmos SA e
ACO na solução de PPP
• Testes com o SA: ‘Temperatura’ inicial
– DAS et al. (1996)
T_i ni cialp
( 0)
fo r i  1  2 0
ri
FO( p 0)

rnd( 1 )
p 0 v iz( p 0  )
FO_ max max( r )
FO_ min mi n( r )
 FO FO_ max FO_ min
T0
 FO
l n( 0 .10)
T0
Emprego dos algoritmos SA e
ACO na solução de PPP
• Testes com o SA: Vizinhança
– viz — idêntica a utilizada no PCV, uma posição na
seqüência é sorteada randomicamente e trocada
com a posição seguinte;
– viz1 — são sorteadas duas posições
randomicamente e trocados os jobs um com o outro;
– viz2 — somente uma posição é sorteada
randomicamente, este job é deslocado para a última
posição da seqüência, enquanto os demais são
deslocados uma posição em cascata.
Emprego dos algoritmos SA e
ACO na solução de PPP
• Testes com o SA: Número de iterações
– nx
– nt
nx  nt  númerode iterações(tentativa
s)
com 8 jobs o número de combinações
é de 40.320 (possibilidades)
Emprego dos algoritmos SA e
ACO na solução de PPP
SA
viz
Parâmetros:T= 3;  = 0.9; nx= 300; nT= 20
viz1
MS* = 52 (100%)
MS* = 52 (25%)
20  300
8
 0.149
viz2
MS* = 52 (100%)
Emprego dos algoritmos SA e
ACO na solução de PPP
• Testes com o ACO:
– Matriz ‘distâncias’
– Número de iterações: número de ‘formigas’ x
número de ciclos
Emprego dos algoritmos SA e
ACO na solução de PPP
ACO
Parâmetros: N = 300;  = 1;  = 2;  = 0.6; T0 = 10-6; Q =100
5 ‘formigas’
10 ‘formigas’
15 ‘formigas’
MS* = 52 (6%)
5  300
8
 0.037
MS* = 52 (9%)
10  300
8
 0.074
MS* = 52 (8%)
15  300
8
 0.112
Emprego dos algoritmos SA e
ACO na solução de PPP
• Testes como o ACO: Matriz de ‘distâncias’
– MS de dois jobs isolados [ 2 8 ]  [ 8 2 ] (Seq. I)
– diferença de MS em uma determinada seqüência
de j jobs de dois determinados jobs (Seq. II)
Emprego dos algoritmos SA e
ACO na solução de PPP
• Exemplo da influência da matriz ‘distância’
Seqüência I
st 1
Seqüência I I
1
1
8
8
2
2
7
7
3
3
6
6
4
5
4
5
5
st 2
4
st 3
5
st 4
4
6
6
3
3
7
7
2
2
8
8
1
1
FO( st 1)  7 0
FO( st 2)  7 2
FO( st 3)  6 0
FO( st 4)  6 0
Tópicos do Trabalho
• Introdução
• Descrição do problema de planejamento da
produção
• Implementação e testes dos algoritmos de busca da
seqüência ótima
• Emprego dos algoritmos SA e ACO na solução de
problemas de programação da produção
• Comparação com resultados da literatura
• Conclusões
Comparação com resultados da
literatura
• Resultados de AHON et al. (2000)
– Problema Castier1
– Problema Castier2
Comparação com resultados da
literatura
• Problema Castier 1
– com 6 jobs distribuídos em 10 equipamentos
5
7 3 6 3 5 9 2 9 3
10 5 8 4 4 6 4 6 4 9
t op
1 10 6 6 6 10 1 7 3 10
9
6 3 2 7 10 7 2 4 1
5
6 1 9 2 8 2 1 3 1
9
5 9 5 9 9 5 5 2 8
Comparação com resultados da
literatura
1 0 1 2 6 7
• Problema Castier2
6 1 7 5 8 3
– com 12 jobs
distribuídos em 6
equipamentos
7 10 8 3 4 1
6 1 9 10 1 1
5 7 0 4 1 6
t op
5 9 8 1 4 3
3 2 2 7 4 4
3 4 7 3 8 8
7 5 5 4 1 6
9 8 6 4 9 5
3 9 8 8 6 9
8 2 6 0 3 5
Comparação com resultados da
literatura
• Desempenho do SA em AHON et al. (2000)
– Castier1 : MS mínimo = 88 unidades de tempo
em mais de 99% das execuções realizadas;
– Castier2 : MS mínimo = 86 unidades de tempo
em mais de 70% das execuções realizadas.
Comparação com resultados da
literatura
• Resultados para Castier1
– apresentou resultados ainda melhores que o
Problema Teste para os algoritmos SA e ACO.
Este fato já era esperado pois é um problema de
dimensão menor que o PPP TESTE, pois Castier1
tem 6! possibilidades enquanto o Problema Teste
tem 8!.
Comparação com resultados da
literatura
• Resultados para Castier2
– ... tem uma dimensão bem maior, constituindo-se
uma avaliação bastante adequada para este
trabalho. O número de combinações possíveis é
11880 vezes maior que o PPP TESTE.
Comparação com resultados da
literatura
• Resultados ótimos obtidos com os algoritmos
SA e ACO para o Problema Castier2
Cenários
MS
EU
Exemplo de Seqüência
FS01
108
0
(1,2,4,11,10,3,5,7,8,6,9,12)
FS07
86
105
(8,1,11,3,7,10,9,2,5,4,6,12)
Comparação com resultados da
literatura
• Testes com o cálculo do MS – Castier2
ig
1  6 00 0
S
 0)
Co mpara( 6 00 0p
130
86
120
S
ig  2
S
ig  1
110
100
90
80
85
90
95
100
110
105
S
115
120
125
130
ig  1
Gráfico dos resultados da busca aleatória para a solução ótima (mínimo) do Problema
Castier2 Cenário FS07 com 20*300 = 6000 tentativas (Sig,1 = FO deste trabalho, Sig,2 =
FO de AHON et al. (2000)).
Comparação com resultados da
literatura
• Testes com o cálculo do MS – PPP Teste
ig
1  6 00
S
Co mpara( 6 00 p 0)
80
52
70
S
ig  2
S
ig  1
60
50
50
55
60
65
S
70
75
80
ig  1
Gráfico dos resultados da busca aleatória para a solução ótima (mínimo) do Problema
Teste Cenário FS07 com 20*30 = 600 tentativas (Sig,1 = FO deste trabalho, Sig,2 = FO de
AHON et al. (2000))
Comparação com resultados da
literatura
• Resultados para Castier2
SA
viz
Parâmetros:T= 5;  = 0.9; nx= 300; nT= 20
viz1
MS* = 86 (3%)
MS* = 86 (1%)
viz2
MS* = 86 (3%)
Comparação com resultados da
literatura
• Resultados para Castier2
nx = 300
SA
Parâmetros:T= 3;  = 0.9; nT= 20- viz
nx = 500
nx = 1000
MS* = 86 (7%)
MS* = 86 (7%)
MS* = 86 (14%)
Comparação com resultados da
literatura
• Resultados para Castier2
ACO
Parâmetros: N = 200;  = 1;  = 2;  = 0.6; T0 = 10-6; Q =100
8 ‘formigas’
16 ‘formigas’
32 ‘formigas’
MS* = 90 (1%)
MS* = 90 (1%)
MS* = 89 (1%)
Comparação com resultados da
literatura
Tópicos do Trabalho
• Introdução
• Descrição do problema de planejamento da
produção
• Implementação e testes dos algoritmos de busca da
seqüência ótima
• Emprego dos algoritmos SA e ACO na solução de
problemas de programação da produção
• Comparação com resultados da literatura
• Conclusões
Conclusões
• o ambiente MathCAD é promissor na solução de PPP;
• em todos os testes realizados o algoritmo SA; mostrou-se, em
condições de comparação, com desempenho superior ao ACO;
– a simplicidade da estrutura de funcionamento do método SA é uma
vantagem inexorável sobre o ACO;
– a dependência do método ACO em relação à forma construção da matriz
de ‘distâncias’ é muito elevada;
• as limitações impostas pelo ambiente MathCAD traduziram-se
num tempo de execução elevado;
• A estrutura de definição da vizinhança é um fator
preponderante para o sucesso na busca da solução para o
método SA
Conclusões
• a estrutura de construção da matriz de ‘distâncias’, decide o
desempenho do método ACO;
• a definição da ‘temperatura’ inicial com o algoritmo de DAS
et al. (1990), é muito mais eficiente que qualquer outra forma
de definir o parâmetro