quinta-feira, junho 08, 2006

 

Afectação quadrática (II)


Procedimento de melhoria (trocas de pares)

Para o exemplo anterior, designe-se o locais numericamente e os postos de trabalho alfabeticamente. Os seguintes fluxos ocorrem entre os postos de trabalho: A B (2), A C (8), A D (3), B C (4), B D (9), e C D (5). Suponha-se que se começa afectando arbitrariamente postos de trabalho A, B, C e D aos locais 1, 2, 3 e 4, respectivamente;. Então, as distâncias entre os postos de trabalho são A B (8), A C (10), A D (2), B C (4), B D (7) e C D (9). O custo total resultante deste layout inicial é obtido somando o produto do fluxo pela distância de cada par de postos de trabalho. Portanto o custo total da solução inicial é

2 (8) + 8 (10) + 3 (2) + 4 (4) + 9 (7) + 5 (9) = 226.

Dada uma solução inicial, considere-se agora trocar as localizações entre pares de postos de trabalho. Suponha-se que A troca com B. Localizando B no local 1 e A no local 2 as novas distâncias são A B (8), A C (4), A D (7), B C (10), B D (2), e C D (9). O novo custo total é

2 (8) + 8 (4) + 3 (7) + 4 (10) + 9 (2) + 5 (9) = 172.

Não se faz já a troca A B, apesar de ser possível um redução do custo total. Vai-se calcular o custo total de todos os pares de trocas e então faz-se a troca de que resulta a maior redução no custo total.

A seguir, considera-se o efeito de trocar A com C, mas ainda com base na solução inicial. Da colocação de C no local 1 e A no local 3, resultam as seguintes distâncias: A B (4), A C (10), A D (9), B C (8), B D (7), e C D (2). O novo custo total é

2 (4) + 8 (10) + 3(9) + 4 (8) + 9 ( 7) + 5 (2) = 220.

O procedimento continua, considerando as trocas de A e D, B e C, B e D, e C e D. Os resultados das trocas são dados na Tabela 1 para a solução inicial. Como se pode verificar, a melhor troca, é entre C e D; então, a troca é feita para se obter a primeira solução melhorada.


Tabela 1. Resultados das trocas de pares para a solução inicial

Distâncias

Trocas de pares

FluxosPares de
postos de trabalho
Solução
inicial
A BA CA DB CB DC D

2A B88471028
8A C1041098102
3A D27922810
4B C41084497
9B D7278974
5C D99210749

Custo total226172220230222227171



Seguidamente, considera-se o efeito no custo total de fazer troca de pares para a primeira solução melhorada. Os resultados das trocas são mostrados na Tabela 2. Como se pode ver, a maior redução no custo total ocorre quando os postos de trabalho C e D são trocados. Portanto, a troca é feita e obtém-se a segunda solução melhorada.


Tabela 2. Resultados das trocas de pares para a primeira solução melhorada

Distâncias

Trocas de pares

FluxosPares de
postos de trabalho
Solução
inicial
A BA CA DB CB DC D

2A B88742108
8A C2729822
3A D10491010810
4B C7287797
9B D41048944
5C D99102479

Custo total171227175220227167226



Normalmente, o processo continua sendo consideradas as trocas de pares para a segunda solução melhorada. A procura da melhor solução termina quando não há trocas que resultem numa redução do custo total ou o limite inferior é obtido. Neste caso, não há trocas que resultem numa redução do custo total.

Comments: Enviar um comentário

Links to this post:

Criar uma hiperligação



<< Home

This page is powered by Blogger. Isn't yours?