Programação de Operações em Máquinas
Alunos: Leticia Peixoto Abranches Christiano Michel Fernandes Freitas
Artigo
Proposição de heurísticas para a minimização do makespan e dos tempos de setup em um ambiente flow shop.
Catalão, março de 2013
1) Introdução:
Com a evolução da indústria o termo competitividade vem sendo abordado e desenvolvido de forma minuciosa. Não basta produzir ou simplesmente desenvolver um bom produto, é preciso ir além e saber explorar ao máximo a produtividade, criando assim um bom relacionamento com a cadeia de produção do setor.
Esta pesquisa apresenta um estudo relacionado ao sequenciamento da produção, que por sua vez é uma linha de estudos da Pesquisa Operacional. O sequenciamento da produção é a ordenação das tarefas em cada máquina e leva em consideração uma gama de objetivos, tais como: redução dos tempos de setup, redução de atrasos, melhoria de fluxo entre outros.
De acordo com Slack et al. (2009), considerando a abordagem do carregamento finita ou infinita, quando o trabalho chega, deve-se tomar decisões sobre a ordem em que as tarefas serão executadas. Essa atividade pode ser chamada de sequenciamento. Para se definir qual a ordem de operações a serem realizadas, usam-se regras de prioridade, como por exemplo: a regra Last In First Out ( LIFO), First In First Out ( FIFO), entre outras.
Liddell(2009) aponta as funções básicas de um bom sistema de sequenciamento, entre elas: i) A possibilidade de programar cada máquina como tendo capacidade finita ou infinita; ii)A capacidade de programar usando múltiplas restrições (como ferramentas e operadores); iii) A habilidade de calcular os tempos de preparação ou set up dependentes da sequência das operações e suas características; iv)A capacidade de sequenciar pedidos com base em datas, prazos, prioridades ou outros atributos técnicos ou gerenciais.
De acordo com Fernandes et al. (2010), flow shop é um ambiente onde o fluxo de produção percorre um sentido unidirecional, ou seja, esse layout é caracterizado por todas as tarefas possuírem a mesma linha de manufatura. Em outras palavras, flow shop é o ambiente de produção em que todas as tarefas têm o mesmo fluxo de processamento nas máquinas.
Conceitualmente o tempo de setup em uma máquina está relacionado ao final de processamento de uma tarefa até o início da segunda. De acordo com Flynn (1987) o tempo de setup esta diretamente relacionada com o grau de similaridade entre tarefas ou operações diferentes, sendo estas processadas em sequência.Segundo Goldacker e Oliveira (2008) usa-se o termo set up para definir o tempo que uma máquina fica parada para realização de uma troca. Esse tempo é decorrente desde o momento em que a máquina interrompe sua produção anterior até o início produção subsequente.
De acordo com Allahverdi e Soroush( 2008), as atividades de setup incluem: obtenção de ferramentas, posicionamento do material a ser trabalhado, devolução de ferramenta, limpeza, ajuste de peças e acessórios, ajuste de ferramentas e inspeção de material em um sistema de manufatura, adequação do ambiente à execução de atividades em uma organização de serviços, entre outros. Os mesmos autores afirmam que os tempos de setup podem ser classificados em: dependentes da sequência e independentes da sequência. Se o tempo de setup é função somente da tarefa a ser processada, independentemente da tarefa anterior, é chamado de independente da sequência. Já o setup dependente da sequência depende tanto da tarefa a ser processada quanto da tarefa anterior.
O objetivo do presente trabalho é analisar e propor métodos de programação e sequenciamento de tarefas, buscando a minimização da soma dos tempos de set up e a redução do makespan em um ambiente flow shop com máquinas de setups dependentes. 2) Revisão Bibliográfica:
De acordo com Morais et al, (2010), em um sistema de produção Flow Shop todas as tarefas e/ou lote de tarefas têm o mesmo fluxo padrão, ou seja, todas possuem o roteiro idêntico de produção em todos os estágios de produção. Se uma tarefa e/ou lote de tarefas não possuir uma operação em alguma das etapas, considera-se que os seus tempos neste estágio são iguais a zero.
O foco deste trabalho está nos setups dependentes da sequência de execução das tarefas. Sabe-se que setups dependentes da sequência são encontrados, geralmente, onde um só equipamento produz muitos tipos diferentes de itens, ou onde máquinas de múltiplas funcionalidades realizam uma variedade de tarefas e/ou lotes de tarefas. É de fundamental importância considerar os tempos de setup, visto que os mesmos possuem custos relevantes, como por exemplo, o custo com a máquina parada e com mão de obra especializada (FERNANDES et al., 2010).
Na literatura é possível encontrar diversas abordagens sobre o estudo de ambientes flow shop, como Fernandes et al. (2010), que estudam este ambiente com três máquinas com diferentes datas de liberação (rj) e tempos de setup (sijk) dependentes da sequência com o objetivo de minimizar o makespan, ou seja, a duração total da programação (Cmax). O objetivo deste trabalho foi apresentar e comparar treze regras de sequenciamento para este problema de programação, as quais foram baseadas nas conhecidas regras SPT (Shortest Processing Time) e LPT (Longest Processing Time). Foram feitas considerações para cada máquina e a experimentação computacional. Analisando os resultados obtidos neste trabalho, dividiram-se as regras em dois grupos: as nove melhores e as três piores. Todas as regras concebidas incluem a data de liberação e tempos de setup na lógica de sequenciamento.
Nagano e Mesquita (2012) abordaram em seu trabalho o problema flow shop permutacional com tempos de preparação das máquinas separados dos tempos de processamento das tarefas, sendo dependentes da sequência de execução das tarefas. Este estudo teve por objetivo apresentar e avaliar novos métodos heurísticos para problemas de programação da produção. Na literatura, o problema é classificado como fortemente NP-hard (non-deterministic polynomial-time hard). O mesmo propôs novos métodos heurísticos construtivos, onde foram desenvolvidos quatro métodos para fins de comparação com os melhores métodos reportados na literatura. Os métodos heurísticos que se apresentaram mais lentos para a obtenção da solução (maior tempo de computação) obtiverem melhores desempenhos com relação à porcentagem de sucesso e porcentagem de desvio relativo. Para este caso, os valores dos resultados obtidos por meio da experimentação e suas formas de análise foram suficientes para verificar e identificar o melhor método heurístico.
Outros autores também abordam o estudo em ambientes flow shop como Nagano et al. (2008) que trata em seu trabalho o problema de programação de operações em um ambiente de produção Flow Shop, tendo como objetivo minimizar o estoque em processamento sem interromper a execução das tarefas. Estes autores propuseram um novo método heurístico que foi comparado com os quatro melhores métodos reportados na literatura para a solução do problema. O método heurístico proposto pelos autores possui duas fases: na primeira é realizada uma ordenação inicial das tarefas, utilizando-se a expressão que possibilita a criação de uma ordenação inicial das tarefas a partir das menores parcelas das somas dos tempos de fluxo de pares de tarefas adjacentes; e na segunda busca-se construir a sequência de solução com a inserção de tarefas nas sequências parciais e sua melhoria com um método de busca na vizinhança. Esta experimentação apresentou um tempo computacional maior em relação aos métodos existentes, porém tal aumento é compensado pela facilidade de implementação do método e pela melhoria na qualidade das soluções. Também vale ressaltar que o método heurístico proposto pelos autores possui desempenho superior ao dos demais, para solução do problema em questão.
3) Algoritmos Propostos
O problema a ser abortado neste artigo é um ambiente de produção flow shop, tendo como restrição a presença de tempos de setup (preparação) dependentes da sequência, objetivando a minimização da duração total da programação (makespan) e da soma dos tempos de setup. Conforme pesquisado é possível observar que não há na literatura estudos com o problema proposto neste trabalho. Sendo assim, foram propostos dois algoritmos que visam uma solução heurística para esse tipo de problema abordado no artigo. A seguir serão descritos os dois algoritmos propostos.
Algoritmo 1:
Passo 1) Crie uma matriz formada pela soma das matrizes dos tempos de setup
Passo 2) Escolha o menor valor na nova matriz
Passo 3) Com o menor valor escolhido cria-se o par ordenado e mantenha-o fixo ( Jx- Jy) . Eliminar a linha e a coluna do par ordenado escolhido e a célula Jy- Jx .
Passo 4) Enquanto houver células válidas, volte ao passo 2.
Passo 5) Com os pares ordenados criados, faz-se a soma dos tempos de processamento dos mesmos, e ordene estes pares pela regra do SPT formando assim a sequência.
Algoritmo 2:
Passo1) Some os tempos de processamento de cada tarefa em cada máquina criando-se assim uma nova linha: pjkt
Passo 2) Crie uma matriz formada pela soma das matrizes dos tempos de setup (sijk)
Passo 3) Crie a matriz Z= pjkt+ sijk, i= 1,...n; j=1,...,n; k= 1,...,m. A linha pjkt deverá ser somada a todos os elementos das colunas J1 até Jn da matriz sijk.
Passo 4) Escolha o menor valor na nova matriz
Passo 5) Com o menor valor escolhido cria-se o par ordenado e mantenha-o fixo ( Jx- Jy) . Eliminar a linha e a coluna do par ordenado escolhido e a célula Jy- Jx .
Passo 6) Enquanto houver células válidas, volte ao passo 4.
Passo 7) Com os pares ordenados criados, faz-se a soma dos tempos de processamento dos mesmos, e ordene estes pares pela regra do SPT formando assim a sequência. 4) Métodos de solução propostos
Para exemplificar os algoritmos propostos, criou-se um problema com quatro tarefas: J1, J2, J3, J4 e duas máquinas: Máquina 1 e Máquina 2, com os respectivos tempos de processamento pj1 e pj2. Além disso, foi criado duas matrizes com os tempos de setup da máquina 1 e da máquina 2, conforme mostra as tabelas abaixo. Os valores das tabelas foram gerados no Excel pela função ALEATÓRIOENTRE, entre valores de 0 a 10 para simular o problema proposto.
Tabela dos tempos de processamento da Máquina 1 (pj1 ) e da Máquina 2 (pj2):
Passo 3) Com o menor valor escolhido cria-se o par ordenado e mantenha-o fixo ( Jx- Jy) . Eliminar a linha e a coluna do par ordenado escolhido e a célula Jy- Jx.
Como o menor valor escolhido foi o número 8, tem-se o par ordenado: J4- J1. Depois foi eliminada a célula J1- J4 e a linha e a coluna do par ordenado, como mostra a tabela a seguir.
Passo 4) Enquanto houver células válidas, volte ao passo 2.
Posteriormente os outros valores escolhidos foram: número 11 ( J1- J2) e número 12 (J2- J3 ).
Passo 5) Com os pares ordenados criados, faz-se a soma dos tempos de processamento dos mesmos, e ordene estes pares pela regra do SPT formando assim a sequência.
Por fim, têm-se os seguintes pares ordenados com suas respectivas soma dos tempos de processamento:
J4- J1(3+9=12)
J1- J2 (9+9= 18)
J2- J3( 9+8= 17)
Pela regra do SPT, tem-se a sequência: J4-J1-J2-J3, mostrada na figura abaixo, com o makespan igual a 39. É importante ressaltar que não será considerado o setup da tarefa que inicia a sequência, que neste caso é a tarefa J4. Além disso, os setups das demais tarefas não são antecipados, ou seja, eles vão acontecer somente quando a tarefa na máquina anterior estiver concluída.
Algoritmo 2:
Passo1) Some os tempos de processamento de cada tarefa em cada máquina criando-se assim uma nova linha: pjkt
Passo 3) Crie a matriz Z= pjkt+ sijk, i= 1,...n; j=1,...,n; k= 1,...,m. A linha pjkt deverá ser somada a todos os elementos das colunas J1 até Jn da matriz sijk.
Passo 5) Com o menor valor escolhido cria-se o par ordenado e mantenha-o fixo ( Jx- Jy) . Eliminar a linha e a coluna do par ordenado escolhido e a célula Jy- Jx.
Como o menor valor escolhido foi o número 14, tem-se o par ordenado: J1- J4. Depois foi eliminada a célula J4- J1 e a linha e a coluna do par ordenado, como mostra a tabela a seguir. Z | J1 | J2 | J3 | J4 | J1 | | 20 | 21 | 14 | J2 | 19 | | 20 | 14 | J3 | 24 | 24 | | 15 | J4 | 17 | 17 | 21 | |
Passo 6) Enquanto houver células válidas, volte ao passo 4.
Posteriormente os outros valores escolhidos foram: número 17 ( J4- J2) e número 19 (J2- J1 ). Como foram esgotadas as células válidas, e a tarefa J3 não foi alocada em nenhum par ordenado, a mesma se encaixa no fim da sequência.
Passo 7) Com os pares ordenados criados, faz-se a soma dos tempos de processamento dos mesmos, e ordene estes pares pela regra do SPT formando assim a sequência.
Por fim, têm-se os seguintes pares ordenados com suas respectivas soma dos tempos de processamento:
J1- 4(9+3=12)
J4- J2 (3+9= 12)
J2- J1(9+9=18)
Pela regra do SPT, tem-se a sequência: J1-J4-J2-J3, mostrada na figura abaixo, com o makespan igual a 42. É importante ressaltar que não será considerado o setup da tarefa que inicia a sequência, que neste caso é a tarefa J1. Além disso, os setups das demais tarefas não são antecipados, ou seja, eles vão acontecer somente quando a tarefa na máquina anterior estiver concluída.
5) Análise dos algoritmos
Foram propostos dois algoritmos: Algoritmo 1 e Algoritmo2, que visam uma solução heurística para o problema abordado neste artigo.
Com relação ao exemplo proposto, o Algoritmo 1 se apresenta como melhor solução, com a sequência J4-J1-J2-J3, visto que o mesmo possui o menor valor de duração total da programação (makespan) que foi igual a 39. O Algoritmo 2, apresentou makespan igual a 42 com a sequência J1-J4-J2-J3.Tais comparações podem ser feitas observando os gráficos de Gantt apresentados acima. 6) Conclusão
Observa-se que o objetivo do presente trabalho foi alcançado, no sentido de propor heurísticas visando minimizar a duração total da programação (makespan) e a soma dos tempos de setup em um ambiente flow shop com máquinas de setups dependentes da sequência.
Como já foi dito anteriormente, não existe na literatura estudos que abordam o problema discutido neste trabalho. Sendo assim, os algoritmos propostos podem ser uma alternativa viável para resolução de problemas semelhantes ao problema estudado neste artigo.
Entretanto, vale ressaltar que ainda é necessário que as heurísticas propostas sejam testadas para um número maior de instâncias, com maior variedade de número de máquinas e tarefas, para que sua eficácia seja comprovada para uma gama maior de problemas teste.
Sugere-se para trabalhos futuros um aprofundamento dessas heurísticas, no sentido de acrescentar melhorias aos algoritmos aqui propostos. 7) Referências
ALLAHVERDI, A.; SOROUSH, H.M. The significance of reducing setup times/setup costs. European Journal of Operational Research, v.187, n.3, p.978-984, 2008.
FLYNN, B. B. The effects of setup time on output capacity in cellular manufacturing. International Journal of Production Research, v. 25, n. 12, p. 1761-1772, 1987.
FERNANDES,S.C; PIRES,T.A; CAMARGO,V.H.C; FUCHIGAMI,H.Y. Programação em flow shop com três máquinas, datas de liberação e tempos de setup dependente da sequência. Encontro Nacional de Engenharia de Produção- ENEGEP,2010,São Carlos. Disponível em < http://static.recantodasletras.com.br/arquivos/2712639.pdf> Acesso dia 18 de dezembro de 2012.
GOLDACKER,F; OLIVEIRA, H. J. Set-up: ferramenta para a produção enxuta. Revista da FAE. Curitiba, v.11, n.2, p.127-139, jul./dez. 2008.
LIDDELL,M. O pequeno livro azul da programação da produção.Edição brasileira: Tecmaran Consultoria e Planejamento,2009.
NAGANO,M.S;MESQUITA,M.S. Métodos Heurísticos para o problema de programação flow shop com tempos de setup separados. Revista Produção Online, Florianópolis, SC, v.12, n. 2, p. 499-521, abr./jun. 2012.
MORAIS,F.M;BOIKO,T.S.P;CANTIERE,P.C;MIYATA,H.H. Análise da Programação da Produção em sistemas flow shop híbrido com tempos de setup dependentes da sequência. Encontro Nacional de Engenharia de Produção -ENEGEP,2010,São Carlos. Disponível em Acesso dia 16 de dezembro de 2012.
NAGANO.M.S; SCARDOELLI. L.Y; MOCCELLIN.J.V. Avaliação de métodos heurísticos em sistemas de produção no-wait flow shop. Revista Eletrônica Produção & Engenharia, v. 1, n. 1, p. 69-80, set./dez. 2008.
SLACK,N; CHAMBERS,S;HARLAND.C; HARRISON.A; JOHNSTON,R. Administração da Produção. Ed. Atlas, 2009.
