segunda-feira, 29 de março de 2010

Problema da linha de montagem

Problema: Em uma fábrica há duas linhas de montagem, cada uma com n estações, a j-ésima estação na linha i é denotada por Si,j e o tempo de montagem nessa estação é ai,j. Um chassi de automóvel entra na fábrica e vai para a linha i (onde i = 1 ou 2), demorando o tempo ei. Depois de passar pela j-ésima estação em uma linha, o chassi vai para a (j+1)-ésima estação de uma das linhas. Não há nenhum custo de transferência se ele ficar na mesma linha, mas demora o tempo ti,j para transferir o automóvel para a outra linha após a estação Si,j. Depois de sair da n-ésima estação em uma linha, decorre o tempo xi para oautomóvel concluído sair da fábrica. O problema é determinar que estações escolher na linha 1 e quais escolher na linha 2 para minimizar o tempo total de passagem de um automóvel pela fábrica.
Solução: Em termos gerais, podemos dizer que uma solução ótima para um problema (encontrar o caminho mais rápido passando pela estação Si,j) contém em seu interior uma solução ótima para subproblemas. (encontrar a passagem mais rápida por S1,j-1 ou S2,j-1). Referimos a essa propriedade como subestrutura ótima, e e ela é uma das indicações de aplicabilidade da programação dinâmica.
Se examinarmos um caminho mais rápido através da estação S1,j ele tem de passar pela estação j-1 na linha 1 ou na linha 2. Desse modo, o caminho mais rápido pela estação S1,j é:

  • O caminho mais rápido pela estação S1,j-1, e depois diretamente pela estação S1,j.
  • O caminho mais rápido pela estação S2,j-1, uma transferencia da linha 2 para a linha 1, e depois através da estação S1,j.
Usando o raciocínio simétrico fazemos a mesma coisa para o caminho mais rápido através da estação S2,j.

Para resolver o problema de encontrar o caminho mais rápido através da estação j de uma das linhas, resolvemos os subproblemas de encontrar os caminhos mais rápidos pela estação j-1 em ambas as linhas. Deste modo, podemos elaborar uma solução ótima para uma instância do problema de programação da linha de montagem pela elaboração de soluções ótimas para subproblemas.

Uma solução recursiva: No problema de programação da linha de montagem, escolhemos como nossos subproblemas os problemas de encontrar o caminho mais rápido pela estação j em ambas as linhas, para j = 1, 2, ..., n. Seja f[i][j] o tempo mais rápido possível para levar um chassi desde o ponto de partida até a estação Si,j.
Nosso objetivo final é descobrir o tempo mais rápido para levar um chassi por todo o percurso na fábrica, que denotamos por F. O chassi tem de passar por todo o caminho até a estação n na linha 1 ou 2, e depois até a saída da fábrica. Tendo em vista que o mais rápido desses caminhos é o caminho mais rápido através da fabrica inteira, temos:
F = min( f[1][n] + x1 , f[2][n] + x2 ) .
Também é fácil raciocinar sobre f[1][1] e f[2][1]. Para chegar até a estação 1 em qualquer linha, basta um chassi ir diretamente até essa estação. Assim,
f[1][1] = e1 + a[1][1] ,
f[1][2] = e2 + a[2][1] .
Agora, vamos considerar como calcular f[i][j] para j = 2, 3, ... n (i = 1 ou 2). Temos que:
f[1][j] = min ( f[1][j-1] + a[1][j] , f[2][j-1] + t[2][j-1] + a[1][j] ) .
Simetricamente temos
f[2][j] = min ( f[2][j-1] + a[2][j] , f[1][j-1] + t[1][j-1] + a[2][j] ) .

2 comentários:

  1. Ae enoc, vamos ver se continua postando e não vai abandonar o blog.... Estou ate pensando em assinar teu feed hauhauhuAhuAhuA

    ResponderExcluir
  2. Devia ter escrito o que vou escrever: conteúdo *inteiro* retirado de "Introdução aos algoritmos" de Thomas Cormen.

    ResponderExcluir