Universidade de Aveiro: Programa Aveiro-Norte / Departamento de Matemática Yazaki Saltano de Portugal, C.E.A. Lda. Departamento de Matemática, Universidade

Universidade de Aveiro: Programa Aveiro-Norte / Departamento de MatemáticaYazaki Saltano de Portugal, C.E.A. Lda.

Departamento de Matemática, Universidade de Aveiro - 24 de Novembro de 2005

ApresentaçãoAndreia Melo

ColaboraçãoPedro Pinto, Miguel Miranda

Optimização daDiversidade e Distribuição de Configurações de Cablagens

Da Matemática à Tecnologia II

Yazaki - Fabricação de cablagens

Módulos opcionais

ou ou

Módulos obrigatórios

Combinações de módulos a produzir

Tecnicamente impossível !

Tecnicamente impossível !

Solução 1Solução 1 Produzir uma configuração que englobe todas as outrasProduzir uma configuração que englobe todas as outras

Todos os módulos seriam incluídos mesmo não sendo pedidos pelo cliente

Prejuízo elevado !Prejuízo elevado !

Solução 2 Solução 2 Produzir as configurações pretendidas pelos clientesProduzir as configurações pretendidas pelos clientes

A diversidade de encomendas é grande e não é possível produzir todas as encomendas em tempo útilA quantidade de cada configuração teria de ser prevista com antecedência

A Solução

Problema

Nº máximo de configuraçõesNº máximo de configurações

Nº mínimo de configuraçõesNº mínimo de configurações

Determinar o conjuntode configurações

a produzir

(Solução 1)

(Solução 2)

Produzir cablagens cujas configurações possuam mais módulos opcionais do que aqueles que vão ser usados

Implementar uma estratégia para minimizar a diversidade de configurações nas cablagens para automóvel optimizando o

respectivo custo

Objectivo do projectoObjectivo do projecto

Classificação dos Módulos

➢Obrigatórios:➢Módulos da diversidade mínima (obrigatórios)

➢ Opcionais:➢Módulos livres➢Módulos técnicos ➢Nome

➢Tipo (div. mínima, livre, técnico)➢Part number (referência)➢Custo➢% de utilização

Características:Características:

Diversidade Mínima

Árvore da Diversidade Mínima

A B C D E

Módulos pertencentes à diversidade mínima:

A

B

C

C

D

E

E

Configuração 1

Configuração 2Configuração 3

Partes fixas das cablagensque têm de ser produzidas

+

+

+ +

+

Módulos obrigatórios

Módulos opcionais

Adicionados às configurações obtidas da diversidade mínima

D EB ++

B C+

A C E++

M1

M2

Módulos opcionais:

M1 M2

M1

M2

M1 M2

M1

M2

M1 M2

M1

M2

Configurações possíveis:3 x 22 = 12

Módulos técnicos

Ex: tubo, conector, etc

Parte da cablagem comum a maisParte da cablagem comum a maisdo que um módulodo que um módulo

Definição de módulo técnico:Módulo a usar quando...

M3

M1

e (M2

ouM4

ou )TM3

=

TM3

M3

M1

M4

1111

0000

00110011

0

0

0

0

1

1

1

1

11

00000

1111

Restrições

Definição de uma restrição:

Definem Definem incompatibilidades entre incompatibilidades entre

módulosmódulos

D EB ++

B +

A C E++ M1 M2

M1

M2

M1 M2

M1

M2

M1 M2

M1

M2

A C E++A C E++A C E++

CB + CB + CB + C

D EB ++

D EB ++

D EB ++

B = 1 e C

M2

= 1 e

= 0

Arquitectura do sistema

Pré-processamentoPré-processamento

Construção das Construção das configurações possíveisconfigurações possíveis

Execução do algoritmo de Execução do algoritmo de optimização:optimização:

determinação do conjunto de configurações a

produzir

Outros componentes

(sistemas) Yazaki

Outros componentes

(sistemas) Yazaki

Web:Web: Interacção com o

utilizador

MySQL

PHP, HTML, Javascript

Base de Base de DadosDados

Interface Web

1.Gestão de utilizadores➢Perfis: administrador, ordinário, consultor

2.Criação e manutenção de datasets

➢Adição de módulos➢Criação da árvore da diversidade mínima➢Definição de módulos técnicos➢Definição de restrições

3.Execução do algoritmo de optimização

➢Definição dos parâmetros de optimização➢Escolha do algoritmo➢Visualização do progresso da execução4.Visualização de

resultados





utilizador



produzir

Outros componentes

(sistemas) Yazaki

Outros componentes

(sistemas) YazakiMySQL



Função do pré-processamento


Algoritmo de Algoritmo de optimizaçãooptimização

Interface WebInterface Web

Dados de saída/erros

Dados de entrada

Solução

Conjunto deconfiguraçõ

es

Dimensão dos dados

Armazenamento:Armazenamento:

Codificação dos módulos livres: 64 bits64 bitsCodificação dos módulos técnicos: 32 bits32 bitsNº máximo de linhas da diversidade mínima: ~ 100~ 100

Nº máximo de configurações:

= 64 x 1029 = ~ 1030

1 configuração = 5 bytes

10105151 GBytesGBytes

!!

Dimensão dos dados

Uma árvore =

(1,1). . . . . . . . . . . . (1,49000).

.

.

.

. . . . . . . . . . . . . .

.

.

.

.

(49000,49000)

= 4.8 GBytes

~4.8 GBytes x 10 árvores = ~48 GBytes de espaço de disco necessário

~1.200 milhões de elementos na matriz triangular superior

Resultado do algoritmo SSF

Diferenças mínimas de give-away!

1.000.000 € x 1 % = 10.000 €

Algoritmos genéticos



utilizador



Outros componentes

(sistemas) Yazaki

Outros componentes

(sistemas) YazakiMySQL





produzir

Modelação matemática

Grafos dirigidos, acíclicos, pesados e desconexos

Teoria de grafosTeoria de grafos

Algoritmo de Optimização

4 configurações mínimas4 configurações mínimas

KKminmin = 4 = 4

KKmaxmax = 7 = 7

Encontrar 3 configuraçõesEncontrar 3 configuraçõesde forma a minimizar os custosde forma a minimizar os custos

Estratégia de Optimização

Algoritmo GreedyAlgoritmo Greedy

- Em cada iteração determina uma nova configuração que deve ser produzida- Termina quando for atingido o Kmax

Exemplo10 configurações possíveis10 configurações possíveisKKminmin = 2 = 2

KKmaxmax = 4 = 4

1

25

43 6

6

3

1

58

5

32

4

7

8

9

10

102

23

1

Exemplo

1

25

43 6

6

3

1

58

5

32

4

K = 3:K = 3: Custo = 13Custo = 13Poupança = 15Poupança = 15

1

25

4

3

63

1

5

4

1

25

43 65

85

4

Custo = 22Custo = 22Poupança = 6Poupança = 6

1

25

4

3

66

5 3

2


6

1

25

43

6

58

5

4

Custo = Custo = 2828

1

25

43 6

6

3

1

58

5

32

4


1

25

43

66

5 5

4

1

2 5

436

6

5 85



1

25

43 6

6

58

5

4

Exemplo



7

8

9

10

102

23

1

7

8

9

10

102

3


7

8

9

10

2

3

7

8

9

10

2

1

7

8

9

10

102


Exemplo

Solução para K = 3:Solução para K = 3:

7

8

9

10

102

23

1

1

25

4

3

63

15

4

Custo total para K = 2: Custo total para K = 2: 28 + 15 = 4328 + 15 = 43

Custo = Custo = 44

Custo = Custo = 99


Custo total para K = 3: Custo total para K = 3: 4 + 9 + 15 = 284 + 9 + 15 = 28

Exemplo

1

25

43 6

6

3

1

58

5

32

4


1

25

4

3

615

4


Custo = 12Custo = 12Poupança = 1Poupança = 1Custo = Custo =

1313

1

25

43

63

1

5

4

1

25

43

63

1

2

1

2 5 4

3

635

4

1

25 4

3

63

15


Exemplo

Solução para K = 4:Solução para K = 4:

1

25

4

3

63

15

4

Custo total para K = 2: Custo total para K = 2: 28 + 15 = 4328 + 15 = 43

Custo = Custo = 44

Custo = Custo = 99


7

8

9

10

2

1

Custo = Custo = 33


Exemplo

Resultados

4,369220:43:7s +39ms

4,2198:37:53s +3ms

6012491520Dataset01

8,15770:0:41s +440ms

7,94960:1:19s +120ms

601832832Dataset13

3,32370:0:2s +300ms

3,32240:0:3s +500ms

60322048Dataset07

1,67630:0:1s +591ms

1,67510:0:3s +900ms

6061536Dataset15

Give-away

Tempo global

Give-away

Tempo global

Kmax

KminUniverso após

restrições

Nome do

dataset

SSF + Alg. Genético

GreedyDescrição do problema

Sítio do Projecto

http://ceoc.mat.ua.pt/~yazaki

Documents

Universidade de Aveiro: Programa Aveiro-Norte / Departamento de Matemática Yazaki Saltano de Portugal, C.E.A. Lda. Departamento de Matemática, Universidade