Resenha_artigo_shifting_bottleneck_in_the_job_shop (1)

Prévia do material em texto

Universidade Federal de Minas Gerais
Escola de Engenharia
Departamento de Engenharia de Produção
EPD 065 – Modelagem dos Sistemas de Produção
Aluno: André Luiz Villas-Boas Silveira			nº 2006018161
Resenha artigo: The shifting bottleneck procedure for job shop scheduling
	O artigo busca descrever um método de aproximação da solução do problema do seqüenciamento do job shop através da minimização do makespan. Ele seqüencia as máquinas uma por uma, sucessivamente, tomando a cada instante de tempo a máquina que é o gargalo daquelas ainda não seqüenciadas. Todas as vezes, após o seqüenciamento de uma nova máquina, todas as seqüências previamente estabelecidas são reotimizadas. Assim, o problema de seqüenciamento de uma máquina é resolvido repetitivamente até que a solução ótima para o problema dado seja encontrada.
São apresentadas no artigo duas versões para o algoritmo: a versão completa (SBI) e a versão enumerativa (SBII).
No princípio do artigo, os autores definem o problema do job shop scheduling , que consiste em processar os Jobs nas máquinas com o objetivo de minimizar o makespan, ou seja, o tempo necessário para processar todos os Jobs.
O problema de seqüenciamento do job shop está entre os problemas mais difíceis de otimização combinatória. Prova disso é que se consegue com certa facilidade resolver problemas tais como do caixeiro viajante com 300 a 400 cidades, que na prática significa mais de 100.000 variáveis, mas não consegue-se resolver um problema típico de otimização do seqüenciamento com apenas dez Jobs em dez máquinas. Como o problema de seqüenciamento do job shop é algo extremamente importante e típico no dia a dia das empresas, é natural que haja um interesse em encontrar soluções nessa área, utilizando-se de métodos de aproximação, mas até o momento não se encontrou uma solução ótima.
A maioria das soluções presentes na literatura até então resolvem o problema através de regras de priorização de despacho, seguindo regras tais como: PEPS ( primeiro a entrar, primeiro a sair), ou o menor tempo de processamento ou ainda o que tem maior quantidade de trabalho a ser feito. O problema é que essas soluções escolhem um ótimo local e a partir daí essa parte da decisão não é revista. Assim, uma solução não ruim é encontrada, mas no artigo, os autores procuram apresentar um método, a partir do avanço da capacidade de processamento dos computadores, que garante um melhoramento na direção do encontro do seqüenciamento ótimo.
O modelo resolve o problema máquina por máquina, uma de cada vez e consecutivamente. Para cada máquina ainda não seqüenciada, eles usam o problema de seqüenciamento de uma máquina, que é uma relaxação do problema original. O resultado obtido então é utilizado para classificar as máquinas e também para seqüenciar a máquina com melhor classificação. Depois que uma máquina é seqüenciada, o modelo reotimiza as máquinas seqüenciadas anteriormente que podem ser suscetíveis a melhoramento resolvendo um problema de uma máquina. A principal contribuição do modelo é introduzir essa relaxação para decidir que máquina deve ser seqüenciada. A idéia utilizada é a de dar prioridade para os gargalos de produção. Para definir os gargalos, os autores procuram um critério que possa dar graus de prioridade, e não simplesmente uma resposta de sim ou não. 
Com a utilização da técnica de grafos disjuntivos em conjunto com a solução repetitiva de problemas de uma máquina, foi construída um técnica para a solução do Job Shop. Em um grafo disjuntivo, um algoritmo para a definição do caminho mais longo era executado, a fim de indicar qual a próxima máquina-gargalo deveria ser seqüenciada.
O procedimento de reotimização local é executado até que não haja mais atualizações para um ciclo que abrange todas as máquinas (e Jobs). O procedimento de gargalos alternantes quase sempre nos retorna soluções melhores que a maioria das heurísticas de grafos disconjuntivo. Assim, para situações onde a qualidade do seqüenciamento em questão é muito importante, a ponto de justificar os investimentos computacionais, foi desenvolvida uma versão do algoritmo utilizando uma árvore de enumeração.
As versões do algoritmo mostrado se mostraram eficientes para resolver problemas de Job Shop com variadas instâncias. No entanto, a versão enumerativa do algoritmo (SBII), se mostrou mais eficiente na maioria das vezes que a versão completa (SBI), retornando resultados mais próximos da realidade.