Logística 2006

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
Fluxos	Pares de postos de trabalho	Solução inicial	A B	A C	A D	B C	B D	C D
2	A B	8	8	4	7	10	2	8
8	A C	10	4	10	9	8	10	2
3	A D	2	7	9	2	2	8	10
4	B C	4	10	8	4	4	9	7
9	B D	7	2	7	8	9	7	4
5	C D	9	9	2	10	7	4	9
Custo total		226	172	220	230	222	227	171

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
Fluxos	Pares de postos de trabalho	Solução inicial	A B	A C	A D	B C	B D	C D
2	A B	8	8	7	4	2	10	8
8	A C	2	7	2	9	8	2	2
3	A D	10	4	9	10	10	8	10
4	B C	7	2	8	7	7	9	7
9	B D	4	10	4	8	9	4	4
5	C D	9	9	10	2	4	7	9
Custo total		171	227	175	220	227	167	226

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.