Baixe o app para aproveitar ainda mais
Prévia do material em texto
Universidade Federal de Minas Gerais Escola de Engenharia da UFMG Curso de Graduação em Engenharia de Produção Disciplina: Modelagem de Sistemas de Produção Professor: Carlos Roberto Venâncio de Carvalho Resenha do Artigo: “The one-machine sequencing problem” Jacques Carlier Gabriela de Moura Cabral nº 2008018479 Nathália Gesualdi nº 2009... Setembro/2010 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.
Compartilhar