Resenha_Carlier_Davi

Prévia do material em texto

“The one-machine sequencing problem”
Jacques Carlier
Nome: Davi Campos Drummond 					
nº 2008018339
O artigo aborda um problema de seqüenciamento de produção, mais especificamente o seqüenciamento de duas máquinas não-gargalo e uma máquina gargalo que processa apenas um job de cada vez, buscando minimizar o makespan do seqüenciamento. O problema descrito no artigo é importante, uma vez que provê a solução de sistemas complicados tais como job shops. O problema é NP-difícil, porém existem métodos de Branch and Bound eficientes e um destes é descrito no artigo. Isto foi conseguido, dentre outras formas, através do seqüenciamento do caminho crítico associado com a teoria dos grafos. O resultado prova que a diferença entre o ótimo e o seqüenciamento realizado pelo algoritmo de Schrage é menor do que d1.
O artigo apresenta três abordagens complementares do problema. Primeiro ele analisa os estudos realizados sobre o algoritmo heurístico de Schrage e analisa o problema pelo mesmo, depois apresenta um método de Branch and Bound, proposto pelo autor, baseado no algoritmo de Schrage e, por fim, o autor faz com que se permita preempção através do método de Relaxação do problema.
No algoritmo de Schrage, o job pronto para entrar na máquina com o maior tempo de delivery time deve ser seqüenciado. No artigo, prova-se que a distância entre o ótimo e o seqüenciamento de Schrage é menor que o tempo de processamento crítico do job que foi definido. Além disso, o artigo mostra como este algoritmo é codificado através de uma complexidade de n log n.
O método de Branch and bound é baseado no algoritmo de Schrage, no job e set críticos. Todos os nódulos da árvore são associados ao problema de “uma-máquina” e a uma ramificação de menor valor. A ramificação de maior valor será o valor da melhor solução encontrada até aquele momento.
O método de relaxação foi estudado por outros autores (Florian et al.; Lageweg et al.), estes também construíram seqüenciamentos de Schrage e definiram sets para calcular o lower bound. Os estudos de Baker and Su [2] permitem preempção para encontrar o melhor makespan, ou seja, um job pode ser interrompido e continuado depois a partir do ponto em que estava sendo processado quando foi interrompido. Este problema é resolvido por um algoritmo preemptivo, o autor aplica o algoritmo de Schrage, porém o processamento do job j é parado quando um job i com uma prioridade maior fica disponível para ser processado. 
Nesse artigo, pudemos ver que existem formas não muito complexas de se minimizar o makespan de seqüenciamentos de job shops, considerados NP - difícil. Isto é obtido através de algoritmos e métodos, com o auxílio de grafos e do mapeamento do caminho crítico.