Resenha_artigo_Jacques_Carlier

Prévia do material em texto

Resenha artigo: The one-machine sequencing problem - Jacques Carlier
Nome: André Luiz Villas-Boas Silveira 			nº 2006018161
O artigo aborda o problema do seqüenciamento da produção que é um importante problema a ser solucionado, uma vez que provê a solução de sistemas complicados tais como job shops , buscando o objetivo que é a minimização do makespan. Isto é conseguido, dentre outras formas, através do seqüenciamento do caminho crítico associado com a teoria dos grafos.
O artigo apresenta três possíveis abordagens do problema: através de algoritmos Heurísticos, do método de Branch and Bound e, por fim, através do método de Relaxação do problema.
No algoritmo Heurístico, o job estará pronto quando o melhor tempo estiver seqüenciado. No artigo, prova-se que a distância entre o ótimo do algoritmo Heurístico é 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 Heurístico, no job e set críticos. Todos os nódulos da árvore são associados ao problema de “uma-máquina” e à uma ramificação de menor valor. A ramificação de maior valor será o valor da solução ótima encontrada até aquele momento.
O método de relaxação é utilizado quando um job pode ser antecipado e continuar depois do ponto em que foi interrompido quando estava sendo processado. Isso se dá através da aplicação do algoritmo Heurístico, mas o processo é interrompido quando um job j apresenta uma prioridade maior que um job i.
Nesse artigo, pudemos ver que existem algumas formas de se chegar ao objetivo, nesse caso, minimizar o makespan. Isto é obtido através de algoritmos e métodos, com o auxílio de grafos e do mapeamento do caminho crítico.