O problema do job-shop e exemplos de aplicação
As atividades de planejamento fazem parte de nosso dia a dia. Ao organizar as tarefas da agenda da semana, organizar as reuniões de nosso time de trabalho na empresa ou organizar uma viagem de férias com a família estamos exercendo a ação de planejamento.
Cada uma dessas atividades, possui um conjunto de tarefas a serem realizadas e uma ordem lógica entre elas, além da constante necessidade de recursos específicos para realizar cada atividade. Quando realizamos o planejamento, ordenamos cada tarefa da maneira que consideramos a melhor possível, por exemplo para realizar um passeio durante uma viagem é necessário ter um meio de transporte (recursos) e os lugares que você quer visitar (tarefas).
No caso do planejamento de uma reunião, se definimos quais serão os temas (tarefas) a serem discutidos (para não perder o foco com comentários que não são o objetivo no momento) e escolhemos uma sala e horário, teremos, ao fim da execução do plano traçado, uma reunião de trabalho produtiva e efetiva.
De maneira semelhante, o planejamento (scheduling) e o escalonamento também estão presentes na indústria, onde a tecnologia moderna tem produzido, em escala crescente, sistemas com a finalidade de organizar tarefas (jobs) que, seja pela importância que adquirem em seu contexto ou pela sua complexidade e custo, justificam os esforços despendidos na sua otimização e automação. Esses sistemas podem usar tecnologias da Indústria 4.0, como Inteligência Artificial e Big Data, criando sistemas ciber-físicos que simulam a realidade de uma fábrica inteligente.
Ou seja, o que as indústrias desejam é obter planos de produção que otimizem tempo, custo e qualidade.
Vamos usar o exemplo da foto abaixo para ficar mais clara a questão do planejamento de um conjunto de tarefas a serem processadas em um conjunto de máquinas.
Cada braço robótico (máquina) executa uma determinada tarefa na linha de produção e ao final da linha você tem o produto completo. Porém, encontrar a sequência de operações para cada máquina buscando minimizar o tempo de execução não é nada simples, já que existem diversas possibilidades de sequências que podem ser escolhidas, sendo de grande complexidade identificar qual seria a ideal para o objetivo traçado [1].
As diferentes configurações que esses problemas da definição de sequências de operações podem ter traçam os variados ambientes encontrados na indústria e servem como base para definir a forma como as máquinas processam as tarefas, tais como máquinas paralelas não relacionadas, flow shop, job-shop, open shop, entre outros [2].
O problema de planejamento de job-shop (JSSP) na indústria consiste na otimização do fluxos de tarefas (jobs) que compartilham recursos, de acordo com um determinado objetivo — redução do tempo total de produção ou do consumo de energia elétrica são alguns exemplos recorrentes.
Ele é ideal para quando se existe um conflito sobre qual decisão deve ser tomada, por exemplo qual ordem de serviço deve ser realizada primeiro levando em conta o seu tempo, processo de produção e a data de entrega, podendo sofrer alterações conforme o aumento ou redução da demanda.
O processo de JSSP pode ser visto abaixo no exemplo de uma fábrica de vestuário.
A fábrica de Roupas S.A. confecciona dois modelos de vestido: o modelo A é um vestido casual com um design simples e tecido estampado e o modelo B é um vestido de festa com um tecido liso, mas um design mais trabalhado.
Os dois compartilham as mesmas máquinas ao longo do processo de confecção. Sendo que, o modelo A é mais rápido de cortar e costurar, mas leva mais tempo no tingimento do tecido. Já o modelo B, leva mais tempo no corte e costura do tecido e menos tempo no tingimento. Vamos considerar que nesse exemplo a tarefa de cortar sempre vem antes de costurar e o tingimento pode ocorrer antes ou depois dessas tarefas.
Levando em conta o fluxo de tarefas e o tempo gasto em cada uma, realiza-se o planejamento de job-shop, com o objetivo de finalizar os dois pedidos no menor tempo possível.
Nos desenhos acima é possível ver a simulação da sequência de tarefas e identificar o caminho dos vestidos ao longo da fábrica, com os retângulos coloridos representando o tempo e a sequência de cada um nas máquinas. Sendo que no primeiro ela está otimizada e no segundo não.
Um exemplo mais complexo é a otimização do sequenciamento de operações em uma aciaria, projeto que a ENACOM desenvolveu para a Gerdau. Um case de sucesso de fábrica inteligente com tecnologias da Indústria 4.0 usando solução em nuvem (cloud computing).
Ele simula no sistema ciber-físico uma sequência ideal de operações para as corridas na aciaria, considerando os objetivos de manter as máquinas de lingotamento em funcionamento contínuo, com o menor número de pausa possível e, ao mesmo tempo, atender as datas de entrega da produção.
Na imagem abaixo, podemos ver a representação do processo otimizado:
Os processos de manufatura de job-shop tem vantagens e desvantagens. Algumas vantagens são a fácil flexibilidade, o melhor uso de recursos, adaptabilidade à mudança, entre outras. Porém, uma das desvantagens principais é o aumento de complexidade para o planejamento (scheduling) e organização de todas as tarefas, que muitas vezes se tornam inviáveis de fazer manualmente. Para facilitar esse processo de ordenação das tarefas pode-se usar ferramentas computacionais baseadas em tecnologias da Indústria 4.0 para fábricas inteligentes, como a desenvolvida para a Gerdau que realiza esse sequenciamento por meio de um sistema otimizado.
Algumas das técnicas de otimização que podem ser usadas nas ferramentas para solucionar o problema de JSSP são: as técnicas tradicionais – Programação Linear, Busca Tabu, Regras de Prioridade, etc – e as avançadas – Inteligência Artificial, Big Data, Lógica Fuzzy, Redes Neurais, etc.
A ENACOM trabalha com várias dessas técnicas nas soluções que desenvolve, incluindo a Teoria de Controle Supervisório, tema abordado no mestrado do Franklin, membro da nossa equipe de otimização, e que é explicada abaixo.
A Teoria de Controle Supervisório (TCS) é uma das ferramentas usadas para a solução do problema de planejamento de job-shop. O Supervisor e o modelo do sistema são representados por autômatos (forma de representar um Sistema a Eventos Discretos), que são grafos orientados [3]. A imagem abaixo representa a estrutura da TCS:
Com essa ferramenta, pode-se reduzir significativamente o espaço de busca para a geração de soluções (sequências de operação das máquinas no sistema) candidatas. É importante dizer que a TCS não informa qual de todas as sequências dentro do espaço de busca (Supervisor) é a melhor, mas a escolha de qualquer dessas sequências está livre de falhas e de bloqueio do sistema [4].
Sua aplicação para a solução do tipo de problemas de scheduling pode levar a resultados diferentes dos encontrados por técnicas que não a usam, já que a característica conservadora dessa ferramenta retira do universo de busca possíveis soluções no sistema que não são consideradas seguras.
A união dela com algoritmos de otimização para a solução de problemas de planejamento tem sido proposta em diversos trabalhos, onde o Supervisor fornece o espaço de busca de sequências candidatas livre de falhas e de bloqueio e o algoritmo de otimização acha a melhor sequência dentro desse espaço.
Percebe-se, assim, a possibilidade de tratar o problema de escalonamento de tarefas estudado nas áreas de Pesquisa Operacional e de Engenharia de Produção, utilizando a modelagem dos sistemas por autômatos e a TCS.
A ENACOM possui uma equipe de pesquisa dedicada ao desenvolvimento de algoritmos de otimização customizados para os mais diversos problemas de planejamento presentes na indústria.
Para aprofundar mais sobre o conteúdo técnico do uso da Teoria de Controle Supervisório para a solução de problemas de planejamento de tarefas, você pode acessar a tese de mestrado do Franklin aqui.