View
105
Download
0
Category
Preview:
Citation preview
Uma Abordagem Heurística Construtiva para o Problema de Minimização de Pilhas Abertas
Marco Antonio M. CarvalhoNei Yoshihiro Soma
XII ONPCE MAR/2009
2
Introdução
Problema de seqüenciamento de padrões, correlato a problemas de corte e empacotamento.
Peças são produzidas e mantidas em pilhas de um mesmo tipo;
Quando a primeira peça é produzida, a respectiva pilhas é “aberta”;
Quando a última peça é produzida, a pilha é “fechada”;
Admite-se limitações quanto ao espaço físico para armazenamento de pilhas abertas.
Mestrado - ITA Dez/2008
Introdução
XII ONPCE Mar/2009
3
Exemplo – Ambiente de Produção
Padrão de Corte
Serra
Pilhas
Exemplo – Ambiente de ProduçãoIntrodução
XII ONPCE Mar/2009
4
Objetivo do Problema
O Problema de Minimização de Pilhas Abertas (MOSP) consiste em minimizar o
número de pilhas abertas simultaneamente por meio do seqüenciamento de padrões.
Mestrado - ITA Dez/2008
Objetivo do ProblemaIntrodução
XII ONPCE Mar/2009
5
Representação
Peças
Padrões
Mestrado - ITA Dez/2008
RepresentaçãoIntrodução
Descontinuidade
Pilha Aberta
Pilha Fechada
Spa = {P8, P3, P7, P2, P4, P6, P5, P1}
XII ONPCE Mar/2009
6
7
4
6
4
1
6
2
3
Grafos MOSP
67
84
3
65
2 8
5
2
GMOSP
Mestrado - ITA Dez/2008
Representação Grafos MOSP
• Outra maneira de se representar o problema é através de grafos MOSP [Yanasse, 1997].
Introdução
XII ONPCE Mar/2009
7
Método Proposto Abordagem Heurística Construtiva
XII ONPCE Mar/2009
Método PropostoIntrodução
3. Geração de Permutações Agrupamento de padrões em blocos;
4. Regra de Melhoria Antecipação do fechamento de pilhas.
1. Pré-processamento Remoção de padrões dominados;
2. Solução Inicial Yuen3 [Yuen, 1995]; De La Banda [Banda, 2007]; Heurística de Extensão-Rotação [Ashikaga, 2001]; ωh;
XII ONPCE Mar/2009
8
Pré-Processamento de Padrões
Mestrado - ITA Dez/2008
Pré-processamento de PadrõesMétodo Proposto
XII ONPCE Mar/2009
9
Em grafos MOSP, o tamanho dos cliques maximais aumenta rapidamente em função do tamanho dos padrões;
Resultados Sobre Cliques
Mestrado - ITA Dez/2008
Resultados sobre CliquesMétodos da Literatura
XII ONPCE Mar/2009
O grafo MOSP complementar é muito esparso e possui conjuntos independentes maximais muito grandes em relação ao número de vértices.
Busca-se o conjunto independente no grafo complementar a fim de obter-se o clique - eventualmente - maximal no grafo original;
A Heurística Gulosa por Vértice de Grau Mínimo [Johnson, 1973] possui um bom desempenho em grafos MOSP
10
ωh
Simplificação da Heurística de Extensão-Rotação [Ashikaga, 2001] Baseada apenas no clique; Seqüencia os vértices conjugados; Seqüencia os demais vértices em ordem não
crescente de grau no grafo MOSP original;
Mestrado - ITA Dez/2008
ωhMétodos da Literatura
Implementação nova Estrutura de dados diferente; Outros procedimentos diferentes
Heurística Gulosa por Vértice de Grau Mínimo.
XII ONPCE Mar/2009
11
ωh
76
51
2
4
3
Spe = {}
76
5 8
2
4
1
3
Spe = {6, 2, 5, 7, 8}
Mestrado - ITAMarco Antonio M. Carvalho Dez/2008
ωhMétodos da Literatura
76
5 8
2
4
1
3
Spe = {3, 6, 2, 5, 7, 8}
A seqüência de padrões correspondente é obtida percorrendo-se a seqüência de peças da direita para a esquerda, incluindo-se do fim para o início todos os padrões que contenham tais peças.
76
5 8
2
4
1
3
Spe = {3, 6, 2, 5, 7, 8, 4, 1}
12
Geração de Permutações Uma solução para o MOSP pode ser vista como
uma permutação Gerar n! permutações é impraticável em tempo
razoável;
Para usufruir este tipo de exploração, propõe-se segmentar a solução e gerar as permutações;
Mestrado - ITA Dez/2008
Geração de PermutaçõesMétodo Proposto
A solução inicial é dividida em blocos de padrões relacionados;
Blocos permutados são agrupados na melhor permutação gerada.
XII ONPCE Mar/2009
13
9 10 11 12 7 8
Bloco 8
Não são modificados
3 4 5 6 1 2
Bloco 9
9 10 11 12 7 8
Agrupamento de Padrões
Bloco 2Bloco 1 Bloco 3 Bloco 4 Bloco 5 Bloco 6
Permutação
3 4 5 6 1 2
Bloco 7
Não é modificadoPermutaçãoPermutação
Mestrado - ITA Dez/2008
Método Proposto Agrupamento de Padrões
7 8 9 10 11 121 2 3 4 5 6
XII ONPCE Mar/2009
O algoritmo de Trotter-Johnson ([Trotter, 1962],[Johnson, 1963]) gera permutações de troca mínima; Permutações geradas mais rapidamente e de forma mais simples.
14
Regra de Melhoria
Simula as pilhas abertas pelo seqüenciamento; Ao encontrar pilhas prestes a fechar, tenta
adiantar o padrão que a fecha.
Mestrado - ITA Dez/2008
Regra de MelhoriaMétodo Proposto
XII ONPCE Mar/2009
Experimentos Computacionais
Mestrado - ITA Dez/2008
Experimentos ComputacionaisMétodo Proposto
XII ONPCE Mar/2009
16
Instâncias geradas aleatoriamente
Experimentos Computacionais
Mestrado - ITA Dez/2008
Experimentos Computacionais
Matrizes binárias quadradas Tamanhos: 100x100 à 1000x1000; Densidades: 10% à 90%; 2000 instâncias diferentes para cada combinação
tamanho x densidade.
XII ONPCE Mar/2009
Métodos comparados Yuen3; Heurística de Extensão-Rotação (hER); De La Banda 5 (DLB5).
17
Comparação das Soluções Iniciais
Para problemas de tamanhos 100 e 200, e para densidade 10%, ωh e hER têm seus piores desempenhos;
Mestrado - ITA Dez/2008
Comparação das SoluçõesExperimentos Computacionais Solução Inicial
Em cada uma das demais condições, ωh obteve o melhor desempenho;
À medida em que o tamanho dos problemas aumenta, ωh se distancia mais dos outros métodos
XII ONPCE Mar/2009
18
Comparação das Soluções Iniciais
Mestrado - ITA Dez/2008
Comparação das SoluçõesExperimentos Computacionais Solução Inicial
XII ONPCE Mar/2009
19
Tempos de Execução
ωh e hER são as mais rápidas: 0,0063s e 0,0072s em média Alternância entre melhor desempenho; Yuen3 e DLB5 possuem 1,0368s e 2,0622s
respectivamente;
Mestrado - ITA Dez/2008
Tempos de ExecuçãoExperimentos Computacionais Solução Inicial
ωh e hER não ultrapassam 0,01s Yuen3 mantém-se abaixo de 3,5s e DLB5 atinge
6,7s;
XII ONPCE Mar/2009
20
Melhoria da Solução Inicial
Mestrado - ITA Dez/2008
Experimentos ComputacionaisMétodo Proposto
XII ONPCE Mar/2009
21
Melhoria da Solução Inicial
Mestrado - ITA Dez/2008
Experimentos Computacionais Tempos de ExecuçãoHeurística Construtiva Melhoria da Solução Inicial
A melhoria é alta e estável, pouco se modifica à medida em que o problema aumenta de tamanho;
À medida em que a densidade aumenta, a melhoria diminui Nas menores densidades a melhoria é extremamente alta, e supre a
deficiência de ωh.
Em média, as fases posteriores do método proposto reduzem o número de pilhas abertas em 4,38 pilhas;
XII ONPCE Mar/2009
22
Comparação das Soluções
Mestrado - ITA Dez/2008
Experimentos Computacionais Comparação das SoluçõesHeurística Construtiva Comparação das Soluções
XII ONPCE Mar/2009
23
O tempo de execução do método proposto é extremamente maior que o dos outros métodos O tempo médio de execução é de 38,02s; Para os maiores problemas ultrapassa-se 2min;
Tempos de Execução
Tempos de ExecuçãoExperimentos Computacionais Heurística Construtiva
O tempo de execução aumenta com o aumento do tamanho dos problemas;
À medida que a densidade aumenta, o tempo de execução diminui;
Tempo abaixo de métodos exatos Aceitável em contextos industriais.
XII ONPCE Mar/2009
Conclusões
Mestrado - ITA Dez/2008
ConclusõesMétodo Proposto
XII ONPCE Mar/2009
25
Conclusões
Mestrado - ITA Dez/2008
Conclusões
O método ωh dominou todos os métodos comparados e surge como alternativa competitiva para solução do MOSP;
O aprimoramento da solução inicial é muito significativo e robusto quanto ao tamanho do problema;
XII ONPCE Mar/2009
A deficiência de ωh em problemas pequenos e de baixa densidade é compensada pelas fases subsequentes do método proposto;
O tempo de execução do método proposto, embora maior que o dos outros métodos, ainda é menor que o de métodos exatos e não é proibitivo.
26
FIM
Mestrado - ITA Dez/2008
Fim
XII ONPCE Mar/2009
Recommended