Uma Abordagem Heurística Construtiva para o Problema de Minimização de Pilhas Abertas Marco Antonio M. Carvalho Nei Yoshihiro Soma XII ONPCE MAR/2009

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.


Objetivo do ProblemaIntrodução

XII ONPCE Mar/2009

5

Representação

Peças

Padrões


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


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


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


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;


ω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;


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


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.


Regra de MelhoriaMétodo Proposto

XII ONPCE Mar/2009

Experimentos Computacionais


Experimentos ComputacionaisMétodo Proposto

XII ONPCE Mar/2009

16

Instâncias geradas aleatoriamente




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;


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


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;


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


Experimentos ComputacionaisMétodo Proposto

XII ONPCE Mar/2009

21

Melhoria da Solução Inicial


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


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


ConclusõesMétodo Proposto

XII ONPCE Mar/2009

25

Conclusões


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


Fim

XII ONPCE Mar/2009

Documents

Uma Abordagem Heurística Construtiva para o Problema de Minimização de Pilhas Abertas Marco Antonio M. Carvalho Nei Yoshihiro Soma XII ONPCE MAR/2009