Integração entre modelos de otimização e ferramenta de gerenciamento visual para o problema de escalonamento em máquinas de produção em lotes

Universidade do Minho Escola de Engenharia Vitor Duarte Integração entre Modelos de Otimização e Ferramenta de Gerenciamento Visual para o Problema de Escalonamento em Máquinas de Produção em Lotes Novembro de 2021 Universidade do Minho Escola de Engenharia Vitor Duarte Integração entre Modelos de Otimização e Ferramenta de Gerenciamento Visual para o Problema de Escalonamento em Máquinas de Produção em Lotes Dissertação de Mestrado em Engenharia Industrial Trabalho efetuado sob a orientação do Professor Doutor José António Vasconcelos Oliveira Novembro de 2021 ii DIREITOS DE AUTOR E CONDIÇÕES DE UTILIZAÇÃO DO TRABALHO POR TERCEIROS Este é um trabalho académico que pode ser utilizado por terceiros desde que respeitadas as regras e boas práticas internacionalmente aceites, no que concerne aos direitos de autor e direitos conexos. Assim, o presente trabalho pode ser utilizado nos termos previstos na licença abaixo indicada. Caso o utilizador necessite de permissão para poder fazer um uso do trabalho em condições não previstas no licenciamento indicado, deverá contactar o autor, através do RepositóriUM da Universidade do Minho. Licença concedida aos utilizadores deste trabalho Atribuição CC BY https://creativecommons.org/licenses/by/4.0/ iii AGRADECIMENTOS A ordem dos agradecimentos não significa nenhuma escala de importância. Primeiramente gostava de agradecer aos meus pais pela oportunidade de continuar os meus estudos, um desejo pessoal que obteve todo suporte por parte deles. Em segundo, gostava de ressaltar meu orientador, Professor José António Oliveira. Obrigado pelo apoio, horas despendidas e ensinamentos passados. Desde a cadeira de Otimização até nossa última reunião posso destacar que sempre pude aprender um pouco mais. Obrigado por aceitar as dificuldades provenientes de diferentes expressões do nosso vocabulário, sempre tentando contornar e conversar sobre possibilidades. Meus sentimentos de gratidão por todo apoio nessa caminha que minha noiva Milena me deu. Todas as conversas, ideias, suporte, e mais, momentos que esteve comigo sempre que precisei, apoiando-me, pois, sabia do meu desejo e prazer em concluir esta Dissertação. Palavras não chegam. Amo-te. À empresa ITZWOOD, Paulo Soares e Patrícia Soares. Obrigado pelos ensinamentos e oportunidade de verificar na prática processos e peculiaridades, possibilitando converter a situação em um estudo. À Professora Doutora Liji Shen da Universidade de Dresden, que em um momento de dúvida sobre uma passagem do trabalho da mesma, respondeu meu email 10 minutos após enviá-lo. Parece pouco, mas gentilezas e atenção podem ser fatores decisivos para o desenvolvimento da edução e de um profissional. Obrigado. Por fim, obrigado a todos os colegas e professores da Universidade do Minho que me aturaram, ensinaram e promoveram meu processo de aprendizagem. iv DECLARAÇÃO DE INTEGRIDADE Declaro ter atuado com integridade na elaboração do presente trabalho académico e confirmo que não recorri à prática de plágio nem a qualquer forma de utilização indevida ou falsificação de informações ou resultados em nenhuma das etapas conducente à sua elaboração. Mais, declaro que conheço e que respeitei o Código de Conduta Ética da Universidade do Minho. v RESUMO Integração entre Modelos de Otimização e Ferramenta de Gerenciamento Visual para o Problema de Escalonamento em Máquinas de Produção em Lotes Setups são um dos principais causadores de desperdícios nos tempos de processamento em ambiente produtivo. É um tipo de atividade que corriqueiramente é citada como parte daquelas que não agregam valor ao processo de produção. Baseado em um estudo de caso visto em uma companhia produtora de móveis em madeira portuguesa, o presente estudo analisa um sistema onde setups , originados pela troca de processamento entre famílias em máquinas de produção em lotes, agravam os tempos de processamento dos artigos. Sendo um ambiente industrial que pratica o Sistema Kanban de produção, a utilização de kanbans físicos guia a produção. No entanto, em um dos estágios surge a necessidade da produção por lotes, visando eliminar ao máximo a ação dos tempos de setups . Sem nenhum processo previamente elaborado/padronizado no estágio a melhorar, o presente trabalho propõe a integração entre uma ferramenta Lean para gerenciamento visual do fluxo produtivo e modelos de otimização para realizar o escalonamento da produção. A partir da comparação com diversas ferramentas Lean, o Rolling Kanban é definido e apresentado como solução a utilizar para o controlo visual. O estágio de estudo é caracterizado como um ambiente composto por três máquinas em série ( Flow shop ) processadoras de lotes, nas quais a composição das famílias pode variar. Para o problema descrito, um modelo de programação linear mista é desenvolvido para a decisão de escalonamento da produção. Devido o modelo exato não comportar instâncias maiores do que dez tarefas, uma modificação da clássica NEH Heurística é proposta. Perante os modelos exatos e aproximados desenvolvidos, um exemplo é realizado propondo a integração do modelo junto à ferramenta Rolling Kanban , sintetizando as potencialidades de ganhos competitivos pela união dos métodos. PALAVRAS-CHAVE Rolling Kanban ; Sistema Kanban; Flow shop ; Modelo de Programação Linear Mista; NEH Heurística vi ABSTRACT An Integration Between Optimization Models and Lean Visual Control Tool Applied to Batch Processing Machines Setups times are one of the most crucial causes of waste in processing times at the industrial environment. This type of activity is commonly mentioned as part of no add value’s activities. Based on a case study seen in a Portuguese wood company, this current study analyses a system where setups times, originated due to changes between different batches of part of families, affect the makespan. As an industrial environment that practices the Kanban System of production, the use of physical kanbans guides production. However, in one of the stages there is a need for batch production, aiming to eliminate as much as possible the action of setup times. Without any previously elaborated/standardized process in the stage to be improved, this work proposes the integration between a Lean tool for visual management of the production flow and optimization models to carry out the production scheduling. Based on the comparison with different Lean tools, Rolling Kanban is defined and presented as a solution to be used to visual control. The study stage is characterized as an environment composed of three batch processing machines in series ( Flow shop ), in which the composition of the families can vary. For the problem described, a mixed linear programming model is developed for the production scheduling decision. Because the exact model does not support instances larger than ten jobs, a modification of the classic NEH Heuristic is proposed. Considering the exact and approximate models developed, an example is executed proposing the integration of the model with the Rolling Kanban tool, synthesizing the potential for competitive gains by combining the methods. KEYWORDS Rolling Kanban; Kanban System; Flow shop ; Mixed Integer Linear Programming (MILP); NEH Heuristic vii ÍNDICE Agradecimentos .................................................................................................................................. iii Resumo............................................................................................................................................... v Abstract.............................................................................................................................................. vi Índice de Figuras ................................................................................................................................ ix Índice de Tabelas ................................................................................................................................ x Lista de Abreviaturas, Siglas e Acrónimos ........................................................................................... xi 1. Introdução .................................................................................................................................. 1 2. Revisão da Literatura .................................................................................................................. 5 2.1 JIT e Sistema Kanban.......................................................................................................... 5 2.1.1 Particularidades do Sistema Kanban ............................................................................ 6 2.1.2 Kanban em função dos tempos de setup ..................................................................... 9 2.1.3 Ferramenta de controlo visual – Rolling Kanban ......................................................... 12 2.2 Escalonamento ................................................................................................................. 14 2.2.1 Classificação em 3 campos - 𝛼 𝛽 𝛾 ........................................................................... 18 2.2.2 Métodos de solução para problemas de Escalonamento ............................................. 22 2.3 Ambiente Flow shop .......................................................................................................... 25 2.3.1 Flow shop com setups ............................................................................................... 26 2.3.2 Flow shop com processamento de lotes ..................................................................... 29 2.3.3 Non-permutation Flow shop ....................................................................................... 35 3. Estudo de Caso: ItzWood – Soluções Tecnológicas .................................................................... 38 3.1 ItzWood – Soluções Tecnológicas, LDA .............................................................................. 38 3.1.1 Estágios e Fluxos Produtivos ...................................................................................... 38 3.1.2 Ordem de Produção - Kanban .................................................................................... 40 3.1.3 Estágio Produtivo - Pintura ......................................................................................... 43 3.2 Enquadramento do Estudo de Caso ................................................................................... 45 3.2.1 Classificação 𝛼|𝛽|𝛾 - Pintura .................................................................................... 46 viii 3.2.2 Nota: complexidade computacional do estudo ............................................................ 47 4. Metodologia .............................................................................................................................. 49 4.1 Modelo de Programação Linear Mista ................................................................................ 49 4.1.1 Adaptação do modelo de programação linear para o estudo de caso .......................... 51 4.2 Heurística Proposta – NEH Modificada .............................................................................. 59 4.3 Utilização da Ferramenta Rolling Kanban ........................................................................... 62 5. Resultados e Discussões ........................................................................................................... 66 5.1 Instâncias Iniciais – Experimentos Computacionais ............................................................ 66 5.2 Relação: estudo de caso x modelo matemático .................................................................. 69 5.3 Experimentos Computacionais – NEH-Modificada .............................................................. 71 5.4 Enquadramento – Rolling Kanban ..................................................................................... 74 6. Conclusões ............................................................................................................................... 77 Referências Bibliográficas ................................................................................................................. 79 Apêndice A – Pseudocódigo NEH-Modificada .................................................................................... 87 Apêndice B – Formulação AMPL ....................................................................................................... 89 4 e suas particularidades, nomeadamente para a existência dos setups , produção por lotes e o conceito de Non-permutation Flow shop . O Capítulo 3 caracterizou a empresa que motivou o estudo de caso. Assim, sector de atuação, estágios produtivos e enquadramento quando aos conceitos explicados no Capítulo 2 foram descritos para situar o leitor do problema a ser resolvido. O Capítulo 4 reuniu a metodologia utilizada neste trabalho. Foi explicado mais profundamente a ferramenta Rolling Kanban , assim como o modelo de programação linear desenvolvido, em especial as adaptações e extensões utilizadas a partir do trabalho de Shen e Gupta (2018). Finalizando o Capítulo 4, realiza-se uma explicação da NEH Heurística e a modificação proposta. Para o Capítulo 5, as instâncias utilizadas para testar modelo matemático são apresentadas. Logo em seguida, o solucionador é apresentado com respetiva razão de escolha. Seguindo, a justificação de uso da NEH Heurística é desenvolvida, baseado nos dados da organização estudada. Por fim do capítulo, o algoritmo e modelo matemático descritos são introduzidos no contexto do Rolling Kanban . No Capítulo 6, último do trabalho, centralizam-se as conclusões, recapitulação dos objetivos do trabalho e possíveis estudos futuros sobre a temática. 5 2. REVISÃO DA LITERATURA Neste capítulo realiza-se uma revisão dos principais conceitos contidos nesta dissertação. O capítulo divide-se em três secções, tendo em vista os objetivos do trabalho. A primeira secção aborda o âmbito de fabricações Just In Time . Conceituou-se produção “puxada” ( pull systems ) e o sistema de produção orientado por cartões ( Kanban system ). Ambas as definições estão contidas ao denominado “Sistema Toyota de Produção”. A partir do Sistema Kanban, uma subsecção é reservada para esclarecimento do modelo original. Reviu-se também outros “kanbans” adaptados a diferentes sistemas. Ainda no Sistema Toyota de Produção foram introduzidas ferramentas/técnicas de controlo visual do Sistema Kanban, especificamente para ambientes em que existam tempos de setups. Por fim, concluiu-se com uma breve síntese do funcionamento da ferramenta (que foi aplicada no estudo de caso) nomeada “ Rolling Kanban ”. A segunda parte do capítulo destinou a tratar do assunto Escalonamento. Primeiramente, o conceito e papel do Escalonamento são esclarecidos. Posteriormente, classificações e particularidades são citadas, visando a compreensão das diversas possíveis situações a serem estudadas. Por fim, são citados métodos exatos e aproximados para solução de problemas de otimização combinatória, nomeadamente programação linear e heurísticas, em contexto de Escalonamento. A terceira e última secção trata do ambiente conhecido como Flow shop , realizando uma análise histórica do Flow shop ; Flow shops com existência de setups ; máquinas processadoras de lotes; e, termina com uma discussão sobre Permutation Flow shops e Non-permutation Flow shop s. 2.1 JIT e Sistema Kanban Ao longo dos anos, a produtividade alcançada pelas companhias japonesas despertou o interesse de estudo entre diversos profissionais ao longo do mundo. A principal empresa relacionada ao contexto dessas produções é a companhia automotiva Toyota. Para mais, o nome associado por trás desse sucesso, e dito como criador do “Sistema Toyota de Produção”, é o do engenheiro, e na época vicepresidente da empresa, Taiichi Ohno (Mitchell & Schonberger, 1983; Sugimori et al., 1977). O Sistema Toyota de Produção tem como uma de suas bases, ou, um de seus sistemas internos a filosofia “Just in time” /JIT. O conceito de produções JIT pode ser definido como uma filosofia que exige a redução dos stocks intermédios ( Work In Process (WIP)), auxiliando no melhoramento do processo e diminuição de sua variabilidade. A ideia chave dessa filosofia é produzir certos itens, em certas quantidades, em um certo tempo (Ohno, 1988; H. Wang & Hsu-Pin (Ben) Wang, 1991). 6 Entretanto, é difícil realizar o JIT para planeamentos da produção onde as operações são realizadas em simultâneo, e, portanto, o fluxo da quantidade produzida no estágio predecessor não é mantido ( Push Systems ). Em geral, não se aplica a produção empurrada ( push ) para ambientes de alta customização, devido desperdícios incontroláveis ( e.g. erro na quantidade produzida) oriundos da alta variabilidade do sistema. Assim, pode-se afirmar que a filosofia JIT atua melhor em produções que o fluxo do material processado é ordenado pelo estágio de produção anterior (produção puxada/ Pull Systems ), suportando melhor a ocorrência de variações no sistema (Monden, 2011). Dentro do Sistema Toyota de Produção define-se “Kanban” como uma das ferramentas para se conseguir produções JIT. Esse nome é atribuído a cartões (físicos ou digitais) que servem para autorizar o processamento, movimentação dos produtos não acabados (WIP) ou compra de material (matériasprimas e/ou insumos). Enquanto “Sistema Kanban”, define o ambiente que se utiliza desses cartões para mover e controlar a produção. Em outras palavras, é um subsistema do Sistema de Produção Toyota (Sohal et al., 1989). 2.1.1 Particularidades do Sistema Kanban O Sistema Kanban foi desenvolvido sob condições específicas, logo, é natural que existam dificuldades para sua implementação em ambientes que divergem do original. Entre as características divergentes, pode-se citar: longos tempos de preparação ( setup ), incerteza de fornecimento, operações não padronizadas, tempo de processamento instável, grandes flutuações de procura e ambientes com consideráveis distâncias físicas entre estágios produtivos (Ohno, 1982; Aggarwal, 1985). Entretanto, as características citadas acima são situações recorrentes nos mercados atuais, e assim, faz-se necessário, por parte das organizações, realizar adaptações visando sobrevivência (Van Veen-Dirks, 2005). Diversos estudos de caso foram relatados usando o Sistema Kanban de maneira adaptada. Acerca destes estudos, desenvolveram-se modificações, seja ou na lógica produtiva ou no próprio kanban (cartão), consoantes a adaptação necessária. Lage Junior & Godinho Filho (2010) sintetizam casos de sistemas que aderem (ou não) à teoria do kanban original, variando suas configurações de acordo com o contexto empregado. Tais variações visam, dentre outras, as possíveis vantagens: a possibilidade de aderir procuras instáveis, facilidade para entrada de novos produtos, operar com diversos fornecedores, melhor balanceamento dos estágios de produção. A Tabela 1 representa uma síntese de aplicações reais, modificadas ou não, em que o Sistema Kanban foi inserido. 7 Tabela 1 – Exemplos de kanbans/Sistema Kanban Nome da Abordagem Vantagens Aplicação real em Comentários/Imagem Kanban (ordem de produção) Redução dos stocks intermédios; fácil controlo visual (Monden, 2011) E-Kanban Possibilidade de atuar entre estágios produtivos (ou fornecedores) de grande distância física; visualização e controle em temporeal. (Mackerron et al., 2014); (Jin et al., 2011). Sistema regenerativo de controle para produção puxada Atuação para sistema com alta variabilidade nos tempos de processamento; e com grande número de itens. (Seidmann, 1988). Job-shop Kanban Possibilita o uso do kanban para ambientes com diversos fluxos produtivos (Job-shop); e para ambientes de procura instável. (Gravel & Price, 1988). Diferentemente do original Sistema Kanban, nessa abordagem os cartões são destinados as operações e não aos produtos. Sistema Kanban modificado Atuação em ambientes com: grande quantidade de itens; máquinas com alto tempo de reparo. (Otenti, 1992). A linha de produção é dividida em equipes que controlam os respetivos inventários. Nessa abordagem um maior número de trabalhadores é necessário. Falso Sistema (kanban) de controle puxado Pode ser efetivamente utilizado em ambientes com gargalos produtivos. (Hendrick, 1988). Permite a abordagem empurrada ( push systems ) quando não é possível o sistema original kanban. Sistema Kanban baseado no método do caminho crítico Permite uma melhor coordenação do fluxo em estágios de montagem. (Abdul-Nour et al., 1998). Kanban com código de barra Efetivamente aplicado para fábricas com muitos fornecedores e procura dos produtos com instabilidade. (Chaussé et al., 2000). 8 A primeira linha da Tabela 1 refere-se a um exemplo do kanban original e as subsequentes são compostas por exemplos com modificações. Apresentou-se, respetivamente, o nome da abordagem, as vantagens da aplicação, o trabalho fonte/referência e comentários ou uma imagem que permite prover uma noção da modificação. Como marco inicial da Tabela 1, define-se “kanban” como uma ferramenta do Sistema Kanban que visa alcançar a filosofia JIT (Monden, 2011). No exemplo em imagem da primeira linha da Tabela 1, tem-se o exemplo do kanban para produção. Esse cartão serve para desencadear a produção. O outro tipo de kanban inicialmente implantado no Sistema Kanban (na companhia Toyota) são aqueles que sinalizam a retirada de materiais nos stocks (em virtude da necessidade de material). As demais linhas da Tabela 1 destinam-se às variações (em reação da possibilidade de vantagens ou impossibilidade da original aplicação) de kanbans/Sistemas Kanbans. • E-Kanban – Variação virtual do kanban original. Pode ser qualquer aplicação eletrónica que realize o fluxo da produção ou requisição de material. Mackerron et al. (2014) utilizam dessa abordagem em um estudo prático para requisição de material aos fornecedores. Como recente aplicação, Pekarcikova et al. (2020) desenvolvem um estudo de simulação para a mesma abordagem; • Sistema regenerativo de controle para produção puxada – Proposto por Seidmann (1988), é uma aplicação automática das funções do kanban. Em outras palavras, o fluxo produtivo entre estágios desenrola-se automaticamente (controlo do WIP). A razão da automação nesse caso é tentar atuar em ambientes com alto grau de variabilidade/customização; • Job-shop Kanban – Aplicado em Gravel e Price (1988), essa variação destinou-se para ambientes Job-shops, portanto, produção na qual diferentes fluxos produtivos são possíveis. Divergindo do kanban original, essa abordagem destina cada cartão para a operação e não ao produto; • Sistema Kanban modificado – Desenvolvido em Otenti (1992). O autor propõe uma divisão do ambiente produtivo em várias equipas. Cada uma dessa com seus respetivos inventários. Essa variação de configuração permite uma rápida resposta para máquinas em que o reparo pode levar um elevado tempo; • Falso Sistema (kanban) de controle puxado – A palavra “falso” é empregada por Hendrick (1988) para um sistema de produtos com baixo volume e alto custo. Nesse sistema a produção, quando permitida, utilizou-se da lógica empurrada ( push ); 9 • Sistema Kanban baseado no método do caminho crítico - Abdul-Nour et al. (1998) propuseram uma abordagem do kanban dependente do método do caminho crítico. Comumente relacionado à gestão de projetos; • Kanban com código de barras – É o exemplo de kanban do qual se utiliza a empresa que destina o estudo de caso dessa dissertação. Permite fácil acesso às informações a produzir; possibilita uma melhor adaptação para procuras instáveis e rápido acesso às quantidades existentes em stocks. Para uma última observação dos kanbans apresentados na Tabela 1, estas modificações podem ou não seguir as quatro principais funções da ferramenta kanban: 1 - Gerir uma visualização/sinal entre estágios; 2 - Coordenar interno ao estágio e na passagem para o estágio seguinte; 3 - Limitar o WIP; 4 - descentralizar o fluxo produtivo. Para os estudos referenciados na Tabela 1, os quatros primeiros (sem considerar o kanban original) seguem as funções do kanban original. Já os restantes modificam sua função em algum dos quatro pontos (Lage Junior & Godinho Filho, 2010). Entretanto, e demonstrando a versatilidade da ferramenta, o kanban utilizado no estudo de caso é um kanban com código de barra e segue as principais funções do sistema kanban original. 2.1.2 Kanban em função dos tempos de setup Uma das principais características que faz o Sistema Kanban modificar-se é a existência de tempo de setup (Millstein & Martinich, 2014). Esses tempos são aqueles decorridos pelas trocas de processamento, início de operação ou finalização do dia produtivo. Generalizando, são tempos despendidos com preparação ou troca de processamento (Chris N. Potts & Kovalyov, 2000). Perante elevados tempos com setups , Millstein e Martinich (2014) contraindicam a utilização da utilização do Sistema Kanban. Os autores relatam que existirá um alto desperdício de tempo em caso de se seguir o Sistema Kanban para ambientes com altos setups . Em outras palavras, a frequência de ocorrência de setups será grande devido o Sistema Kanban atuar sobre um fluxo produtivo puxado, e, caso tais setups despenderem muito tempo ou custos, os desperdícios serão elevados. Visando o controlo produtivo em Sistema Kanban com tempos de setups , algumas técnicas de gerenciamento visual do fluxo produtivo foram desenvolvidas para adaptação quanto a tempos de preparação ou troca de processamento. A Tabela 2 dissemina exemplos dessas “técnicas kanban” para controlo/gerenciamento visual da produção mesmo com a ocorrência de tempos com setups , indicando, 10 respetivamente, nome, característica do setup , o trabalho fonte/referência de conceituação e uma imagem para entendimento visual. Tabela 2– Técnicas de gerenciamento visual para Sistemas Kanban com existência de tempos de setup Técnica Kanban Característica do(s) setup(s) Referência Imagem Kanban box / Faxbox /Caixa de correio Tempos não existentes ou negligenciáveis. Não dependem da sequência de processamento. (Hirano, 2009; Monden, 2011). Pattern production Baixo tempo com setup e depende da sequência de processamento. (Seidman & Holloway, 2002). Lot-making board Baixo tempo com setup e depende da sequência de processamento. Uma sequência fixa não pode ser empregada. (Gross & McInnis, 2003; Smalley, 2009). Roda Kanban dos setups por famílias de produtos Tempos de setups baixos entre troca para produção de itens de mesma família e tempos elevados para diferentes famílias. (King & King, 2018) Rolling Kanban Tempos de setups baixos entre troca para produção de itens de mesma família e tempos elevados para diferentes famílias. Uma produção cíclica não pode ser estabelecida. (Braglia et al., 2020) Kanban triangular ou por sinal Inevitáveis elevados tempos de setup. (Monden, 2011; Smalley, 2009) 11 É possível, a partir da Tabela 2, perceber que os tempos de setup caracterizados na segunda coluna crescem ao longo do quadro (cima para baixo). Uma breve síntese de cada técnica é desenvolvida a seguir. • Kanban box – É um exemplo para uma produção sem a existência de tempos para preparação. A técnica, denominada Kanban box armazena kanbans que chegam ao longo do tempo de maneira que a produção seguirá o fluxo da ordem de chegada. Portanto visualiza-se o First-InFirst-Out (FIFO). Essa é a situação apropriada para se atingir o JIT (Braglia et al., 2020; Monden, 2011); • Pattern Production – Técnica que leva em consideração produções dependentes da sequência de execução. Entretanto, é possível encontrar uma sequência ótima entre as ordens a produzir. Assim, estabelece-se uma sequência fixa onde os kanbans são ordenados de acordo como tal; • Lot-Making Board – Aplicado a sistemas com dependência da sequência a produzir. Porém, diferente do ponto anterior, uma sequência fixa não pode ser seguida; • Roda Kanban – Cada área da roda destina-se a um período de produção para uma família de produtos, acoplando também os tempos (elevados) de preparação existentes entre a troca de famílias. A roda gira em um sentido e aquela sequência é mantida para produção de todas as ordens; • Rolling Kanban – Tem características de setups similares ao ponto anterior. No entanto, uma produção cíclica não pode ser desenvolvida em razão de procuras instáveis a curto prazo. Como solução, o Rolling Kanban desenvolve-se em um quadro no qual o operador monta a sequência produtiva de acordo com o horizonte estabelecido para execução. Essa técnica adapta-se à chegada constante de ordens; • Kanban por sinal – Destina-se à produção por lotes. Entretanto, sempre decorrerá elevados tempos com setups , independente da sequência aderida. O quinto ponto destaca a ferramenta Rolling Kanban. Os autores Braglia et al. (2020) resgatam a ferramenta a partir de um trabalho de consultoria da empresa italiana FESTO, descrido em Boyer (2004). Os autores justificam a importância da técnica devido a uma lacuna entre ferramentas existentes, especificamente uma que enquadre produções no qual a troca processamento decorra entre diferentes famílias. Com observação que tais trocas (entre diferentes famílias) acarretam altos tempos de setup (baixos tempos para troca entre produtos da mesma família). 12 Para essas produções, normalmente utiliza-se o conceito e aplicação dos lotes de produção, no qual uma máquina/recurso processa mais de um trabalho ao mesmo tempo (Chris N. Potts & Kovalyov, 2000). Nesse caso, o fluxo característico de sistemas puxados (primeira ordem a entrar no sistema, primeira a sair) deve ser quebrado para formação dos lotes. Em detrimento desse problema, o Rolling Kanban surgiu como uma ferramenta visual capaz de auxiliar o desencadeamento do Sistema Kanban para o processamento em lotes. Mais, com o pormenor da ocorrência de altos setups para troca de famílias e baixos para uma mesma família. O Rolling Kanban para além deste desencadeamento, promove também o escalonamento do processamento das ordens de produção (nesse contexto, kanbans), já que permite o realizador do processo visualizar as tarefas restantes e estrutura-las ao longo do período produtivo (Braglia et al., 2020). 2.1.3 Ferramenta de controlo visual – Rolling Kanban A Figura 1 reúne dois exemplos de Rolling Kanban. Na Figura 1a representou-se a ideia inicial da configuração do quadro descrido em Boyer (2004). Já a Figura 1b revela o redesenho do trabalho de Boyer realizado por Braglia et al. (2020). Figura 1 – Exemplos de Rolling Kanban; Figura 1a – Desenhado por Boyer (2004); Figura 1b – Desenhado por Braglia et al. (2020) É relevante a menção que a fundamentação teórica por trás da ferramenta é escassa. Apenas os dois trabalhos mencionados formam o campo de trabalhos anteriores desenvolvidos sobre o Rolling Kanban (Braglia et al., 2020). Logo, como já mencionado, esta dissertação tem como um dos objetivos a expansão dos estudos e aplicações acerca da ferramenta. No restante desse subtópico uma breve explicação da ferramenta é realizada. Para além, uma aplicação prática com descrição pormenorizada é proposta no Capítulo 4. 13 A partir da Figura 2 é possível visualizar que alguns elementos são fundamentais para formação (física) da ferramenta. Inicialmente, um horizonte temporal precisa ser definido. Posteriormente esse horizonte é seccionado em períodos produtivos (dias, turnos, horas). Essas divisões são representadas pelas letras “A B C D E” da Figura 2b. Evidentemente, o horizonte temporal é a soma desses períodos. Por exemplo, se cada período representar um dia, o horizonte temporal (A+B+C+D+E) é igual a uma semana (5 dias) de planeamento da produção. O início da produção é representado na Figura 2a. Cada ordem (kanban) foi disposta de acordo com a respetiva prioridade ( e.g. kanbans com maior tempo de espera para processamento tem maior prioridade). Logo, itens alocados na coluna B são mais prioritários que itens em C e assim sucessivamente. O estágio atual da produção é evidenciado pelo objeto em branco na Figura 2a e preto na Figura 2b. Ao final de cada período produtivo, o objeto se desloca para direita (Figura 2a → Figura 2b). Em caso de chegada, durante o horizonte de planeamento, de novas ordens, os kanbans são postos a esquerda do objeto preto (Figura 2b), podendo haver atribuição a uma coluna que ainda falta ser produzida, caso haja capacidade produtiva. Figura 2 – Funcionamento Rolling Kanban; Figura 2a – Primeiro período produtivo (Braglia et al., 2020); Figura 2b – Segundo período produtivo (Braglia et al., 2020) Sobre a Figura 2b, nota-se kanbans destacados. Estes foram os produzidos no primeiro período (A) e, portanto, eliminados do quadro (dando seguimento ao fluxo produtivo). A escolha de quais kanbans produzir (escalonamento das ordens) é realizada pelo operador. Seguindo alguns passos descritos em Boyer (2004). 20 Portanto, máquina é “ligada” apenas no momento em que de acordo com o escalonamento todas as tarefas possam ser executadas (naquela máquina) sem interrupções; • No-wait (𝑛𝑤𝑡) – Semelhante à No-Idle , 𝑛𝑤𝑡 significa que uma tarefa 𝑗 não deve esperar para iniciar seu processamento na máquina seguinte. Entretanto, em alguns casos um tempo máximo ou mínimo é permitido, e para estes casos 𝛽 =𝑡𝑖𝑚𝑒 𝑙𝑎𝑔s; • Pulmão (𝐵𝑢𝑓𝑓𝑒𝑟 ou 𝑏) – Quando 𝛽 = 𝐵𝑢𝑓𝑓𝑒𝑟=𝑏, isto expressa que existe entre máquinas uma restrição de espaço. Se a capacidade de armazenamento entre máquinas for infinita (𝛽 = ∞), a condição No-Idle deverá ser aplicada, e, a taxa de utilização das máquinas será máxima. Se a capacidade for finita para uma máquina 𝑖 ∈𝑀, 𝛽 = 𝑏𝑖. Se não houver qualquer local para armazenamento entre máquinas, então a condição a condição No-Wait deve ser aplicada ou 𝛽 =𝑏𝑙𝑜𝑐𝑘, que indica quando uma tarefa está finalizada na máquina predecessora porém bloqueada para início na máquina seguinte (que está em utilização); • Lotes (𝑏𝑎𝑡𝑐ℎ) – Reproduz a existência de produção por lotes. Isto infere que mais de uma tarefa pode ser processada em uma máquina. Máquinas capazes de realizar a produção por lotes recebem a denominação de Batch Processing Machine (BPM). Essa representação pode variar entre Serial Batching (𝑠−𝑏𝑎𝑡𝑐ℎ) e Parallel Batching (𝑝−𝑏𝑎𝑡𝑐ℎ). Serial Batching traduz que o processamento das tarefas é realizado de maneira serial, ou seja, o tempo de processamento do lote é a soma dos tempos de processamento das tarefas presentes no lote. Parallel Batching representa uma BPM em que o tempo de processamento do lote é o maior tempo de processamento entre as tarefas presentes no lote, em outros termos, as tarefas são processadas em simultâneo (em paralelo). A ocorrência de lotes também pode diferir entre lote disponível , que significa que a transferência das tarefas contidas no lote deve ocorrer em conjunto (por exemplo, em paletes que carregam todas as ordens juntas), ou tarefa disponível , que é a situação em que uma tarefa finalizada no lote pode ser transferida para a máquina seguinte. Por fim, mais uma peculiaridade de produção por lotes, a denominação lote inconsistente quer dizer que os lotes podem diferentes configurações ao longo dos estágios produtivos. Lotes inconsistentes são essencialmente parte de um escalonamento non-permutation , já que sendo os lotes inconstantes, a sequência de processamento dos trabalhos tenderá a não ser fixa entre as máquinas (Shen & Gupta, 2018); • Famílias (𝑓𝑚𝑙𝑠) – Relata existência de famílias de produtos, que são produtos com características físicas similares ou com tecnologias de processamento semelhantes. Estendendo 21 o conceito de setups e lotes, 𝑠𝑖𝑗𝑘 pode representar, por exemplo, o custo decorrido pela troca de processamento entre o lote de produção que continha a família 𝑗 pelo lote de produção que contém a família 𝑘, na máquina 𝑖. Mais, Tecnologia de grupo e Família de produtos incompatíveis são dois termos presentes nesse contexto de Escalonamento. Tecnologia de grupo significa quando um grupo (lote) deve ser processado em conjunto, não podendo ser “repartido” em sub-lotes ( e.g. lot streamming ) (Cheng et al., 2000). Família de produtos incompatíveis infere que produtos de diferentes famílias não podem ser processados juntos em nenhuma circunstância (Mönch & Roob, 2018). Vale a ressalva que Família de produtos incompatíveis pode também ocorrer entre as máquinas, significando mudanças de famílias entre máquinas (Isenberg & Scholz-Reiter, 2013); • Escalonamento Online (𝑜𝑛𝑙𝑖𝑛𝑒) – Em geral, os problemas de escalonamento se dão de forma determinística/ offline (M. Liu & Chu, 2012; Ouelhadj & Petrovic, 2009; Pruhs et al., 2004). Isto significa que todo o conhecimento acerca de tempos e disponibilidades é sabido antes do início do processamento. 𝛽 =𝑜𝑛𝑙𝑖𝑛𝑒 infere que as tarefas chegam ao longo do período de processamento, portanto, decisões em tempo real devem ser tomadas sobre essas tarefas. Outras comuns afetações ao campo 𝛽 são as já mencionadas 𝑟𝑗, 𝑑𝑗, 𝑑𝑗  e 𝑤𝑗, representando, respetivamente, que o problema tem restrições relacionadas à data de lançamento, data de vencimento, deadline e custo/peso das tarefas 𝑗 ∈𝐽. Demais atribuições ao campo 𝛽 são normalmente autoexplicativas, caso não, cabe ao estudo em questão realizar a conceituação. Como último campo da classificação 𝛼| 𝛽| 𝛾, a simbologia 𝛾 refere-se ao critério de otimização, logo, é a procura pela maximização ou minimização (ou ambas) de uma ou mais métricas. Brucker (2007) segmenta os tipos de critérios em duas classes. A primeira, chamada de objetivos de gargalo , estão objetivos preocupados com a(s) última(s) tarefa(s) a ser(em) concluída(s) (Equação 1). A segunda, são os objetivos de soma , em que se preocupam com a somatória de uma métrica/objetivo (Equação 2). 𝑓𝑚𝑎𝑥(𝐶)=max{𝑓𝑗(𝐶𝑗)| 𝑗 ∈𝐽} (1) ∑𝑓𝑗(𝐶)= ∑𝑓𝑗 𝑛 𝑗=1 (𝐶𝑗) (2) Para ambas Equações, 𝐶𝑗 representa o tempo de conclusão da tarefa 𝑗. Já 𝑓𝑗 indica uma função custo associada à tarefa 𝑗, que pode ou não ser especificada. Como dois dos 𝛾 mais estudados, temos 𝛾 = 𝐶𝑚𝑎𝑥 = max{𝐶𝑗 | 𝑗 ∈𝐽} que quantifica o maior tempo de conclusão entre das tarefas em 𝐽, também nomeado como makespan , e 𝛾 =∑𝐶𝑗 𝑛 𝑗=1 (tempo total de percurso) que indica a somatória dos tempos 22 de conclusão da cada tarefa 𝑗 ∈𝐽. Uma possível variação no tempo total de percurso é a inclusão de pesos 𝑤𝑗, portanto com 𝛾 =∑𝑤𝑗𝐶𝑗 𝑛 𝑗=1 . Para demais exemplos listados abaixo, todos podem seguir à objetivo de gargalo ou objetivos de soma. • Atraso (𝐿𝑗) – Indica o atraso associado à tarefa 𝑗. Define-se atraso como: 𝐿𝑗= 𝐶𝑗−𝑑𝑗. Notase que 𝐿𝑗 pode ser tanto positivo quanto negativo; • Atraso positivo (𝑇𝑗) – Diferentemente de 𝐿𝑗, 𝑇𝑗 pode apenas apresentar valores positivos. Portanto, 𝑇𝑗=max(𝐶𝑗−𝑑𝑗,0)=max (𝐿𝑗,0), e representa o quanto tardio está uma tarefa relativamente à data de entrega (𝑑𝑗) estabelecida; • Penalidade por atraso (𝑈𝑗) – É uma penalidade em uma unidade pela ocorrência de atraso. Isto é: 𝑈𝑗= {1, 𝐶𝑗>𝑑𝑗 0, 𝑐𝑎𝑠𝑜 𝑐𝑜𝑛𝑡𝑟á𝑟𝑖𝑜; • Precocidade (𝐸𝑗) – Quantifica o quão antes uma tarefa 𝑗 foi finalizada antes de sua respetiva 𝑑𝑗. Em outras palavras, significa o quanto está antecipada uma tarefa relativamente à data de entrega (𝑑𝑗) estabelecida. Logo: 𝐸𝑗= max (𝑑𝑗− 𝐶𝑗,0). Diferentemente das demais, 𝐸𝑗 é dita como uma função não-regular no estudo de Escalonamento. A razão está por 𝐸𝑗 ser não-crescente em 𝐶𝑗, ou seja, é uma função que não é favorecida por um menor 𝐶𝑗. Esse tipo de função é mais recente no estudo de Escalonamento, e comum para ambientes que buscam baixos desvio no plano de produção ( e.g. ambientes que buscam JIT) (Brucker, 2007; Pinedo, 2016). Para concluir o campo 𝛾, o número de atribuições possíveis a este campo depende da quantidade de critérios de otimização, por exemplo se duas funções estão sendo avaliadas 𝛾 = 𝛾1𝛾2. 2.2.2 Métodos de solução para problemas de Escalonamento Sendo o Escalonamento um problema de análise combinatória, os métodos para soluções desenvolvidos ao longo dos anos são basicamente divergidos entre métodos exatos e métodos aproximados. Em princípio, existindo um conjunto finito de soluções viáveis, qualquer algoritmo que abordasse todas as caraterísticas do problema encontraria a melhor resposta para o mesmo, e, portanto, se teria uma resposta exata para a situação. No entanto, uma complicação é vista quando o número de soluções possíveis é muito alto. Deste último caso, pode-se preferir uma resposta que se utiliza de menos recurso e resulte numa aproximação da melhor solução, sendo assim o método de obtenção desta resposta chamado de aproximado . Em IO, os métodos aproximados devem fornecer uma qualidade sobre a 23 aproximação. Em outras palavras, cabe ao profissional garantir que a resposta aproximada não se distancie muito da resposta ótima (Festa, 2014). Alguns problemas de Escalonamento podem ser reduzidos a conhecidos problemas de otimização combinatória, logo resolvidos a partir de metodologias desenvolvidas para os mesmos (Brucker, 2007). A modelagem matemática foi massivamente implementada ao decorrer dos tempos para estes problemas. Mais, dentro da modelagem matemática, e buscando a solução exata do problema, a Programação Linear foi uma das abordagens mais comuns na busca por soluções. Programação linear é um técnica bastante conhecida dentro da comunidade de IO, e eficaz principalmente em problemas de pequeno e médio porte (Brucker, 2007; Pinedo, 2016). A relevância dessa técnica como fonte de solução pode ser evidenciada em livros base da teoria do Escalonamento. Tanto Brucker (2007) como Pinedo (2016) destinam parte de capítulos com preocupação de explicar a programação linear. Uma simples síntese de Programação Linear pode ser descrita da seguinte forma: 𝑀𝑎𝑥𝑖𝑚𝑖𝑧𝑎𝑟 𝑜𝑢 𝑀𝑖𝑛𝑖𝑚𝑖𝑧𝑎𝑟 →𝐹𝑢𝑛çã𝑜 𝑜𝑏𝑗𝑒𝑡𝑖𝑣𝑜 𝑆𝑢𝑗𝑒𝑖𝑡𝑜 𝑎 (𝑠.𝑎.)→𝐶𝑜𝑛𝑗𝑢𝑛𝑡𝑜 𝑑𝑒 𝑟𝑒𝑠𝑡𝑟𝑖çõ𝑒𝑠 Formalizando, a Programação Linear baseia-se em um objetivo que se deseja otimizar, nomeado de função objetivo; e um conjunto de restrições que delimitam aquele problema. No tocante ao objetivo do problema, este pode divergir entre um objetivo de maximização ou minimização. Basicamente em um objetivo de minimização (maximização) busca-se, dentro das soluções possíveis, o menor (maior) valor de uma função linear. Já o conjunto de restrições (também linear), é formado por equações ou inequações que relacionam características do problema com a variáveis existentes (Hiller & Lieberman, 2014). Exemplificando, tem-se: 𝑀𝑖𝑛 𝑍(𝑥)= 𝑐1𝑥1+ ⋯+ 𝑐𝑛𝑥𝑛 (3) s.a. 𝑎11𝑥1+⋯+𝑎1𝑛𝑥𝑛≥ 𝑏1 (4) ⋮ 𝑎𝑚1𝑥1+⋯+𝑎𝑚𝑛𝑥𝑛≥ 𝑏𝑚 (4.n) 𝑥𝑗≥0, ∀ 𝑗=1,..,𝑛 (5) Pela Equação 3 pode-se constatar a função objetivo (𝑍(𝑥)), que nesse caso é de minimização. A função depende das variáveis de decisão , nesse caso representas por (𝑥1… 𝑥𝑛). Como elemento restante da 24 Equação 3, 𝐶 =(𝑐1… 𝑐𝑛) são parâmetros do problema, valores conhecidos e constantes. As Inequações 4 e 5 representam as restrições do problema. As n-Inequações 4 representam a relação (linear) entre as variáveis de decisão e outros parâmetros do problema (neste caso a matriz 𝐴𝑚 𝑥 𝑛 = (𝑎11… 𝑎𝑚𝑛) e o vetor 𝐵 = (𝑏1…𝑏𝑚)). A Inequação 5 apenas dita que as variáveis de decisão não podem ser negativas. Sintetizando, busca-se em um problema com parâmetros 𝐶, 𝐴𝑚 𝑥 𝑛 e 𝐵, minimizar 𝑍(𝑥), de forma que os valores encontrados para (𝑥1… 𝑥𝑛), ou seja, a solução, respeitem as restrições do problema (Inequações 4 e 5). Caso as variáveis de um problema modelado em programação linear devam ser todas inteiras (restrição/imposição), tem-se o chamado Programação Linear Inteira ou Programação Inteira . Se for imposto que as variáveis apenas podem receber valores binários, ou seja, 0 ou 1, tem-se o caso de Programação Linear Binária . Em caso de um modelo de programação linear com algumas das variáveis restritas a serem inteiras, tem-se Programação Linear Mista (Brucker, 2007). Destaca-se o método Simplex, algoritmo de Branch and Bound e método de programação dinâmica , como importantes algoritmos desenvolvidos para resolver os problemas de programação linear (Festa, 2014; Hiller & Lieberman, 2014). O uso da programação linear ainda é uma das abordagens mais utilizadas para resolver problemas de otimização combinatória, e consequentemente, problemas de escalonamento. A causa dessa utilização pode ser dada pelo rigor, flexibilidade e extensiva capacidade de modelagem da programação linear (Floudas & Lin, 2005). Entretanto, por grande parte dos problemas de escalonamento serem NP-Hard , a abordagem por programação linear é aconselhada apenas em problemas de tamanho médio ou pequeno (Reza Hejazi & Saghafian, 2005). Todavia, para solucionar problemas de escalonamento, ainda são diversos os exemplos do uso da programação linear/modelagem matemática/métodos exatos, até os atuais dias. Por exemplo, no artigo de revisão de Daniel Alejandro Rossit et al. (2018) para Nonpermutation Flow shop das 74 situações avaliadas 12 utilizam procedimentos exatos; em Allahverdi (2015) para ambientes Flow shop com setups e famílias de tarefas, das 38 situações descritas 8 utilizam de métodos exatos; e no artigo de revisão para Flow shops Flexíveis (𝐹𝐹𝐶), Lee e Loong (2019) mostram que 8% dos artigos avaliados foram resolvidos por métodos exatos. Uma das formas de implantar a programação linear é modelá-la em uma linguagem computacional ( e.g. AMPL) e atribuir este modelo a um solucionador ( solver ) ( e.g. CPLEX). Diversos solucionadores estão disponíveis gratuitamente. Um exemplo de serviço gratuito que fornece diversas possibilidades de resolvedores, em diversas linguagens, para diferentes modelagens (programação linear é uma das 25 possibilidades) é o NEOS SERVER. Tal serviço é hospedado pela Universidade de Wisconsin, Estados Unidos, e vem sendo utilizado em Universidade de todo o mundo, como Universidade de Klagenfurt, Austria, e Universidade do Minho, Portugal (Neos Server, 2021). A partir do facto que grande parte dos problemas de Escalonamento são NP-Hard , os métodos aproximados compõem uma importante parcela nos métodos para resolução destes problemas. Potts e Strusevich (2009) em seu trabalho de descrição dos principais marcos do estudo do Escalonamento separam a quarta década desde o início do estudo dessa área como a “década dos métodos aproximados”. Os autores definem “Heurística” como sendo um algoritmo aproximado que não se preocupa com avaliação dos piores casos ( worst-case ) ou comportamento do algoritmo. Potts e Strusevich (2009) também separam tipos de Heurística em: 1 - Heurísticas construtiva, que são aquelas que partem de uma solução vazia ao passo que no decorrer do método a solução é construída. Alguns exemplos já foram citados no trabalho, são casos das Heurísticas SPT e EDD; 2 - Heurísticas de busca local, que são originadas pelo relaxamento do problema, possibilitam partir de uma solução inicial já estabelecida, uma série de passo que busca a melhoria desta solução. Vale destacar o conceito de “vizinhança” que nada mais é do que movimento permitidos visando encontrar uma melhor solução; 3 – Metaheurísticas, que nada mais são que Heurísticas de busca local que ao longo dos anos demonstraram, para situações genéricas, uma performance digna deste termo. Pode-se destacar alguns famosos métodos como Algoritmos genéticos, Simulated Annealing e Busca Tabu ( Tabu Search ). 2.3 Ambiente Flow shop O ambiente Flow shop , que conceitua uma configuração na qual todas as tarefas devem seguir uma mesma sequência de máquinas para respetivo processamento, vem sendo massivamente estudado ao longo dos anos. A importância desse ambiente tem caráter tanto teórico como prático. Do ponto de vista teórico, o trabalho de Johnson (1954) marca o Escalonamento como um estudo de análise combinatória e área independente dentro da IO (C. N. Potts & Strusevich, 2009). Especificamente, o trabalho de Johnson (1954) tratou de um ambiente Flow shop , logo, pode-se apontar esse artigo como o estudo inicial para esse tipo de ambiente (Campbell et al., 1970; T. C.Edwin Cheng et al., 2000; Rabadi et al., 2019; Srikar & Ghosh, 1986; Tseng & Stafford, 2001). Johnson (1954) demonstrou que existe uma solução ótima para o escalonamento de tarefas em um ambiente com 2 ou 3 máquinas, em que a sequência de tarefas não muda entre máquinas ( permutation / 𝛽 =𝑝𝑟𝑚𝑢). A metodologia de resolução proposta por Johnson recebeu o nome do autor (regra de Johnson) e serve, até os atuais dias, para 26 estudos, discussões ou solução inicial em novos métodos ( e.g. Li e Lu (2020); Rabadi et al. (2019); Wu et al. (2020); Zou et al. (2020)). Vistos de outra perspetiva, os estudos de caráter teórico acerca do Flow shop iniciam na década de 50 e perpetuam-se até os presentes dias, demonstrando sua relevância. Do ponto de vista prático, ambientes Flow shop destacam-se pelos inúmeros fabricos que necessariamente devem seguir uma sequência fixa de máquinas: células de produção robótica (Dawande et al., 2007); pintura automotiva (Salmasi et al., 2010); indústria de semicondutores (Celano et al., 2010); fabrico de eletrónicos (Gelogullari & Logendran, 2010); dentre outros exemplos como linhas de montagem, indústria metalúrgica, indústria química e indústria alimentícia (González-Neira et al., 2017). Portanto, do ponto de vista prático, a relevância dos estudos sobre Flow shop dá-se pela diversidade de setores e atividades que essa configuração atinge. Assim, unindo a teoria à prática, a importância dos estudos sobre ambientes Flow shop é justificada pela abrangência de atuação (diversas atividades/setores/fabricos) que naturalmente contribuirá para o desenvolvimento de novos problemas, métodos e/ou discussões. 2.3.1 Flow shop com setups O ambiente Flow shop analisado por Johnson (1954), também conhecido como Flow shop regular , segue premissas que distanciam o problema das situações do mundo real (Gupta, 1979). Além da consideração sobre permutation / 𝛽=𝑝𝑟𝑚𝑢, o Flow shop regular não inclui tempos/custos com setups . Allahverdi e Soroush (2008) enaltecem o papel crucial dos setups nas operações, e comentam que mesmo com fundamental importância alguns trabalhos ignoram esses tempos/custos ou os incluem nos tempos de processamento. Os autores diferenciam custos e tempos com setups , onde custos com setups designam custos para configurar qualquer recurso usado antes de um novo início de operação; já tempo de setup atribui-se ao tempo despendido para preparar o recurso (máquina). Nesta dissertação o termo setup infere tanto aos custos com setups como os tempos com setups , comentando diferenças quando necessário . Setups vem recebendo significativa atenção na literatura. Allahverdi et al. (1999), Allahverdi et al. (2008) e Allahverdi (2015) constituem uma série de três extensivos artigos de revisão para setups baseados na classificação 𝛼| 𝛽| 𝛾 e com respetiva atualização devido o passar dos anos. Os três artigos reúnem, cronologicamente, métodos para resolução deste tipo de problema, além de distinguir os setups pela incidência (ou não) de lotes com sequência-dependente ou sequência-independente. Cheng et al. (2000) seguem a mesma lógica dos trabalhos citados, entretanto com foco específico para ambientes Flow shop . Os autores comentam fundamentalmente sobre classificação, representação e complexidade computacional existente para Flow shop com setups . Cheng et al. (2000) destacam também uma 27 diferença entre tempos com setups e tempos de remoção, que seriam aqueles decorrentes pós processamento, como inspeções ou transferências de produto, podendo variar entre tarefa-dependente ou tarefa-independente. Alguns autores ( e,g, Ríos-Mercado e Bard (2003)) evidenciam os setups para o primeiro processamento no recurso (𝑠𝑖0𝑘). Esta evidência dá-se por 𝑠𝑖0𝑘 não ser originado pela troca de tarefas, e a menção também é válida pela desconsideração desses setups em outros estudos ( e.g. Srikar e Ghosh (1986)). Seguindo a mesma lógica de 𝑠𝑖0𝑘, setups pós a última operação também podem ser evidenciados (𝑠𝑖𝑛𝑛+1), como uma preparação para o dia seguinte de produção ou uma última ação (exemplo, limpeza) necessária no dia produtivo. Outro pormenor a destacar entre setups é feito em Stefansdottir et al. (2017), no qual os autores realizam uma especificação sobre a atividade de limpeza , segregando-a dos demais setups . Os autores declaram possibilidades de ganhos quando atividades de limpeza são consideradas à parte dos comuns setups . Mais, Stefansdottir et al. (2017) também fazem uma completa elaboração das características gerais dos setups , sendo estas: separabilidade, substituibilidade, ponto de referência, flexibilidade, tarefa-dependência e lote-dependência. A Figura 4, com base nos trabalhos anteriormente citados, apresenta um esquema dos tipos, nomenclaturas e abreviações que sintetizam os diferentes setups para ambientes Flow shop. Figura 4 – Esquema Flow shop com setups A Figura 4 inicia pela existência (ou não) do processamento por lotes (indicado pela letra “b”) em ambientes Flow shop . O seguinte critério de segmentação dá-se pelo setup ser sequência--dependente (SD) ou sequência-independente (SI) entre tarefas ou famílias (indicado pela letra “f”). Portanto, e visto no último nível da Figura 4, para um setup em contexto de processamento por lotes , que depende da sequência em que as famílias de produtos são processadas, usou-se “SD,bf” como abreviação. Se famílias não existem no sistema, tem-se a abreviação “SD,b”; se os setups duma produção em lotes não dependem da sequência de processamento das famílias, tem-se “SI, bf”. Em 28 igual caso, porém, apenas com tarefas, deu-se “SI, b”. Para a situação de não existência de lotes de produção e que o setup depende da sequência de processamento das famílias, tem-se “SD, f”, sem famílias “SD”. Os últimos dois casos destinam, respetivamente, os casos vistos em uma produção sem lotes onde os setups não dependem da sequência de processamento das famílias “SI, f” ou das tarefas “SI”. Uma importante observação é que a Figura 4 apresenta a possibilidade de haver famílias de produtos, mas o respetivo processamento destas famílias pode não ser necessariamente por lotes. Vale a lembrança de que a capacidade de realizar o processamento em lotes depende apenas do recurso (máquina), portanto, a existência de famílias de produtos independe se a máquina é processadora de lotes ou não. Os setups podem também divergir entre antecipatórios e não-antecipatórios . Utilizando a característica de separabilidade descrita em Stefansdottir et al. (2017), setups antecipatórios e não-antecipatórios dependem da possibilidade de início do setup acontecer (máquina sucessora) antes do término da tarefa (portanto, antecipatório/separável) na máquina predecessora (Figura 5a); ou o setup ocorrer apenas (máquina sucessora) ao término da tarefa na máquina predecessora (portanto, nãoantecipatório/inseparável) (Figura 5b). Figura 5 – Gráfico de Gantt para setups antecipatórios (5a) e não-antecipatórios (5b) 29 A Figura 5 é estruturada por 3 máquinas e 2 tarefas (J1 e J2) com respetivos setups (em preto) e tempos de processamento (cinza - J1 e laranja - J2). Pela Figura 5a pode constatar um diagrama de Gantt referenciando setups antecipatórios. Nota-se que é possível antecipar a ocorrência do setup em máquinas sucessoras, por exemplo, antes do término de J1 na máquina 1 o setup de J1 já é realizado na máquina 2. Setups antecipatórios são o que Stefansdottir et al. (2017) conceitualizam como a possibilidade de trabalhar offline . Já para o segundo diagrama de Gantt (Figura 5b), nota-se que o setup apenas ocorre quando a respetiva tarefa é finalizada na máquina predecessora. Por exemplo, o setup referente a J1 na máquina 2 só ocorre quando J1 é finalizado na máquina 1. Evidentemente, para dois ambientes Flow shop idênticos (quantidade de máquinas, tarefas e iguais tempos de processamento) que divergem entre setups antecipatórios e não-antecipatórios, o makespan do ambiente Flow shop para setups antecipatórios será menor. Concluindo este subtópico, é fundamental comentar, mesmo que brevemente, acerca da complexidade computacional encontrada em problemas Flow shop com setups . Para um ambiente Flow shop regular (sem setups ), com minimização do makespan e arbitrário número de máquinas (𝐹𝑚| | 𝐶𝑚𝑎𝑥), sabe-se que esse problema é NP-hard em forte senso (Lawler et al., 1993). Para um também caso de arbitrariedade de máquinas, porém com a inclusão de setup , Garey e Johnson (1979) mostram que esse problema também é NP-hard em forte senso. Entretanto, Cheng et al. (2000) observam que dentro dos problemas Flow shop com setups existem situações polinomialmente resolvíveis (resolução do problema em tempo polinomial). Os autores destacam que problemas Flow shop com setups sequênciadependente e processamento em lotes (SD,bf e SD,b) são os mais complexos quando comparado entre todas situações da Figura 4. À razão de superior complexidade computacional, nestas situações tem-se para além de um problema de escalonamento Flow shop um problema de formação de lotes. 2.3.2 Flow shop com processamento de lotes Implicitamente comentado no subtópico anterior, uma das motivações para realizar produções com lotes é a existência de setups . Mais do que existir setups , Chris N. Potts e Kovalyov (2000) generalizam que a produção por lotes ocorre devido qualquer oportunidade de ganho em efetividade. Normalmente, a preferência por produção em lotes será em virtude de um processamento mais rápido ou mais económico que o processamento individual das tarefas (Chris N. Potts & Kovalyov, 2000). Com menor generalização dos ganhos, Van Der Zee (2013) cita que a partir da produção de lotes atinge-se melhoramentos em métricas como tempo(s) de ciclo, redução de inventário para WIP, capacidade de resposta ao cliente e taxa de produtividade. 36 A razão de preferência por Permutation Flow shop pode ser averiguada pelo número de possíveis escalonamentos. Enquanto existem (𝑛!)𝑚 escalonamentos para uma situação de Non-permutation Flow shop , existem 𝑛! escalonamentos para Permutation Flow shop (Rossi & Lanzetta, 2014). Outra justificativa pode decorrer da prova que existe um escalonamento ótimo para Flow shops regulares com 2 ou 3 máquinas (Johnson, 1954; Pinedo, 2016). Mais, não tratar o ambiente Flow shop de maneira geral ( Non-permutation Flow shop ) pode ocorrer também pela impossibilidade de troca da sequência entre estágio (J. Schaller, 2012). Uma troca da sequência só se é possível caso exista um mecanismo de armazenamento entre estágio (pulmões), onde possa-se “segurar” os itens e permitir que outras tarefas “passem” à frente. Se 𝛽 → 𝑏 =0, implicitamente tem-se um ambiente Permutation Flow shop . Outras restrições que tornam o ambiente Permutation Flow shop são 𝛽 =𝑏𝑙𝑜𝑐𝑘 e 𝛽 =𝑛𝑜−𝑤𝑎𝑖𝑡 (Daniel Alejandro Rossit et al., 2018). Em linhas gerais, apesar de existir situações em que o Permutation Flow shop apresente resposta ótima, a forma geral de um ambiente Flow shop ( Non-permutation Flow shop ) domina o Permutation Flow shop para mais de 3 máquinas no ambiente (Figura 8) (Chris N. Potts et al., 1991; Pugazhendhi et al., 2003; D. Rossit et al., 2016). Em outras palavras, Permutation Flow shop é uma subclasse do Non-permutation Flow shop (Chris N. Potts et al., 1991). Figura 8 – Espaço solução Permutation Flow shop e Non-permutation Flow shop (traduzido de D. A. Rossit et al. (2018)) Dos principais aspetos que podem prejudicar a análise por negligenciar ambientes non-permutation Flow shop , pode-se citar que: 1 – para ambientes com 4 ou mais máquinas o Permutation Flow shop pode não ser ótimo (Koulamas, 1998); 2 – para objetivos diferentes à minimização do makespan , principalmente no tocante de datas de vencimento (𝑑𝑗), Lin e Ying (2009) e Lin et al. (2009) mostram que a diferença de ganho em eficiência é em média 10% superior a favor de ambientes Non-permutation Flow shop , podendo atingir 30%; 3 – a natureza da operação contrapor-se à Permutation Flow shop , como casos de um Flow shop com diferentes famílias entre máquina ( e.g. Isenberg e Scholz-Reiter (2013)) ou Flow shop com falta de operações ( missing operations ) (Henneberg & Neufeld, 2016; Rossit et al., 2021). 37 Com o desenvolvimento tecnológico e ganhos que acompanham a evolução do mercado, os problemas de Non-permutation Flow shop vem despertando interesse de estudo (Rossit et al., 2018). Rossit et al. (2018) em seu artigo de revisão apenas à Non-permutation Flow shop relatam que 65% dos artigos selecionados para compor seu trabalho foram desenvolvidos depois de 2006, portanto, demonstrando-se esta uma temática recente. Outra forma de fortalecer “ Non-permutation Flow shop ” como uma temática recente é vista ao filtrar por palavras-chaves, título e resumo na base de dados Scopus a partir das palavras “ Non-permutation flow* ” ou “ Non permutation flow* ”. Dos 52 resultados obtidos pela pesquisa, apenas 2 são anteriores ao ano de 2005 (Scopus, 2021). Por fim, Non-permutation Flow shop mescla-se com outros assuntos já aqui comentados, tais como processamento por lotes e existência de setups . No mesmo sentido que a sequência de processamento das tarefas ser ou não alterada nos estágios, a sequência de processamento dos lotes pode ou não ser alterada. Ng e Kovalyov (2007) apresentam um relevante estudo na temática de Permutation Flow shop vs Non-permutation Flow shop com o processamento em série dos lotes e setups dependentes. Os autores provam que para o problema 𝐹| 𝑠− 𝑏𝑎𝑡𝑐ℎ, 𝑠𝑖𝑗𝑘| 𝐶𝑚𝑎𝑥, independente dos setups serem antecipatórios ou não, e independente dos lotes serem consistentes ou não, existe um escalonamento ótimo com o conceito de permutation / 𝛽 =𝑝𝑟𝑚𝑢 para 1, 2 ou 3 máquinas. 38 3. ESTUDO DE CASO: ITZWOOD – SOLUÇÕES TECNOLÓGICAS Este capítulo descreve as características da empresa que origina o problema de estudo. O setor de atuação, os estágios produtivos, o fluxo de produção e os problemas vistos são tratados na primeira parte do capítulo. Na segunda parte é concatenado as classificações abordadas na revisão da literatura com a situações real, e assim, formula-se o sistema e seus componentes que embasam o restante da dissertação. 3.1 ItzWood – Soluções Tecnológicas, LDA A empresa contida na presente dissertação tem como nome “ItzWood – Soluções Tecnológicas, LDA”. A empresa pratica a manufatura de artigos sustentados pela matéria-prima madeira, presando pela inovação tecnológica e alta qualidade para com qualquer móvel/artigo que surja de uns dos materiais mais nobres, belos e sustentáveis – a madeira (Itzwood, 2021). A companhia está localizada na região norte de Portugal, mais especificamente na cidade de Paços de Ferreira. A cidade está inserida num polo reconhecido pelas atividades têxteis, couro e madeira. Desta última afirmação, a Figura 9 segrega respetivamente, a indústria da madeira e cortiça (com exclusão do mobiliário) (Figura 9a) e de mobiliário e colchões (Figura 9b) em Portugal por “NUT 2” (divisão do território português em sete regiões). Sendo evidente o domínio territorial da região Norte nessa indústria. Figura 9 – Segregação do setor de atuação da empresa por NUT 2; Figura 3a - Indústria da madeira e cortiça; Figura 3b - Indústria mobiliária e colchões (Direção-Geral das Atividades Económicas, 2021) 3.1.1 Estágios e Fluxos Produtivos A ItzWood é composta por cinco estágios produtivos, sendo estes: marcenaria, pintura, acabamento, expedição e estofos. Em cada estágio pode também existir subdivisões. Isto é o caso dos estágios 39 marcenaria e pintura, com as subdivisões: pré-corte, CNC, trabalho manual e aros (para marcenaria); primário, lixagem e acabamento (para pintura). A Tabela 3 sintetiza a numerização (códigos) utilizada nesta dissertação para atribuir cada estágio e respetiva subdivisão. Tabela 3– Numeração dos estágios produtivos Código Estágio Subdivisão 1 Marcenaria 11 Pré-corte 12 CNC 13 Trabalho manual 14 Aros 2 Pintura 21 Primária 22 Lixagem 23 Acabamento 3 Acabamento - 4 Expedição - 5 Estofos - De acordo com a Tabela 3, pode-se definir uma representação do fluxo produtivo como uma união entre os códigos, por exemplo: 11 - 12 - 13 - 14 - 2 - 3 - 4. Algumas observações devem ser comentadas: atualmente o estágio da marcenaria (1) é apenas indicativo, portanto, se o fluxo produtivo iniciar pela marcenaria (imensa maioria dos fluxos existentes) receberá um número entre 11-14; atualmente o estágio da pintura ainda não é operacionalmente segregado, portanto, apenas existem fluxos que contém o código 2 e nenhum com valores entre 21-23. A implementação da correção dessa segunda observação (utilizar os códigos entre 21-23) é um dos procedimentos futuros prioritários na empresa. Para proporcionar uma ideia espacial do fluxo produtivo, a Figura 10 localiza cada estágio e subdivisão (pelo código) e simula um fluxo produtivo em que todos os estágios são acionados. Tal esquema estruturou-se a partir do layout da empresa. 40 Figura 10 – Exemplo de fluxo produtivo É percebível a partir da Figura 10 a existência de dois níveis na empresa. O estágio da pintura é realizado no nível subsolo (cave). Os demais processos são feitos ao nível do solo. A Figura 10 exemplifica um fluxo que apenas algumas máquinas de cada estágio foram necessárias. Por isso não se vê linhas penetrando em certas máquinas. Outra observação se dá caso mais de um kanban estivesse a ser processado. Para este exemplo, o funcionamento ocorreria em paralelo, logo, mais de um fluxo deveria ser indicado. A Figura 10 apenas os stocks intermédios da pintura foram representados. Todavia, entre toda troca de estágio existe espaços determinados para stocks intermédios. Quanto às ordens de produção, o subtópico seguinte aborda o esclarecimento do funcionamento quando é recebida uma ordem de produção. 3.1.2 Ordem de Produção - Kanban Ao ser recebido um pedido para fabricação (por parte do cliente), as seguintes ações são tomadas antes de iniciar o processo produtivo: elaboração do projeto e orçamentação e o envio para validação do cliente. Caso validado, a ordem de produção será gerada. Nos casos em que o produto já tenha sido pedido e 41 produzido para o mesmo cliente, a validação do projeto não é necessária, decorrendo a imediata possibilidade de geração da ordem de produção e início da produção. Posto a ordem em produção, pedidos customizados carregam 25 dias úteis de prazo e pedidos padrões 15 dias úteis. A empresa utiliza cartões (kanbans - ordens de produção) como uma forma de guiar a produção. Para além do controlo visual, as informações e pormenores do produto estão contidas no kanban (por meio do respetivo código de barras) para facilitar o operador durante a operação. Cada kanban também informa a quantidade que deve ser produzida, assim como, a quantidade a se produzir naquele estágio. Por exemplo, para se produzir X artigos pode ser necessário no pré-corte (11) Y cortes diferentes. Esses Y cortes podem seguir para o trabalho manual (13) e serem unidos (colados) dando forma a X peças. Todas nestas informações são acessíveis via kanban. A utilização dos kanbans é entendida como uma mais-valia pela empresa. Conforme foi reportado no Capítulo 2, o sistema kanban promove diversas vantagens. No âmbito da ItzWood esses ganhos são bem observados. Dentre os principais, destacam-se: • Diminuição dos stocks intermédios: como cada kanban contém a quantidade de material necessária, o conhecimento da quantidade a produzir é de fácil acesso. Antes do processamento o operador verifica (no sistema interno) se aquela quantidade está presente em stock, utilizando só a quantidade demandada. Podendo também, em caso de falta de produto, requisitar o(s) item(s); • Antecipação da falta de material: o estágio seguinte de produção também pode facilmente obter as informações do kanban e requisitar itens; • Rápido rastreio da ordem de produção; • Fácil controlo do sistema produtivo. A passagem entre estágios dá-se por colocar o kanban num “sequenciador” presente no estágio seguinte. Entende-se por sequenciador uma caixa como a representada na Figura 11. 42 Figura 11 - Sequenciador É possível visualizar três locais onde o kanban pode ser depositado. O primeiro local (de cima para baixo), pintado de vermelho, destina-se para kanbans com “problema”, por exemplo falta de material. O segundo é destinado para kanbans “via verde” aonde são depositados aqueles com máxima prioridade. Em certos momentos, o gestor pode resgatar uma ordem da pilha de kanbans a produzir (terceiro deposito) e afetálo ao posto “via verde” – prioritário. O último local, como já mencionado, é destinado à sequência natural das ordens de produção, sendo o próximo item a adentrar no estágio o localizado mais abaixo. Na Figura 11 pode-se observar uma pilha de kanbans no último nível, logo, o kanban mais abaixo desta pilha é o próximo a entrar em estágio de produção. Para mudanças de estágio, o operador do estágio atual deposita o kanban no terceiro posto (em preto) do sequenciador do estágio seguinte. Um exemplo com mesma estética e funcionalidade são as caixas de correio descritas em Hirano (2009). Entre os códigos 11 – 14 (pré-corte; CNC; trabalho manual; aros) o fluxo peça por peça ( one-piece-flow ) é razoavelmente conservado. Os tempos de processamento destes estágios seguem valores similares e estáveis, assim como baixos e consistentes tempos com setups para as trocas de kanbans. Portanto, naturalmente o primeiro item posto no estágio 11 será (na maioria das vezes) o primeiro item a sair do estágio 14 (obedecendo o First-In-First-Out , FIFO). A quebra do FIFO pode ocorrer para kanbans com diferentes fluxos. Por exemplo, considere que uma encomenda tem sua ordem de produção indicada por um kanban denominado como “A” e outra encomenda (completamente diferente da vista no kanban A) tem sua ordem de produção indicada pelo kanban denominado com “B”. O kanban A tem um fluxo específico para respetivo fabrico descrito pelos estágios 11 - 12 - 13 - 2. Já o kanban B tem um fluxo para respetivo fabrico descrito pelos estágios 11 - 12 - 13 - 14 - 2. Portanto, mesmo em caso da produção do kanban A ser iniciada antes da produção do kanban B, o kanban B pode chegar antes no estágio da pintura (2) devido seu fluxo necessitar de um estágio a menos. Ainda neste exemplo, enquanto o kanban A pode estar em processamento no estágio “aros” o kanban B pode ter terminado seu 43 processamento no estágio “trabalho manual” e seguir fluxo para o estágio da pintura, e, portanto, a regra FIFO sendo quebrada. Este é um exemplo descrito no Capítulo 2 subsecção 2.3.3 para Flow shop com falta de operações. 3.1.3 Estágio Produtivo - Pintura Contrapondo a filosofia JIT para a abordagem por kanbans (Sistema Kanban), a produção por lotes caminha em passos opostos à preservação da política FIFO. Mesmo sabendo das vantagens inerentes à adesão do Sistema Kanban, existem favorecimentos na produção por lotes que podem se sobressair quando comparados às vantagens do Sistema Kanban. Assim, certas produções necessitam adaptar a produção por lotes ao funcionamento do Sistema Kanban (Savsar, 1997; Sivakumar & Shahabudeen, 2009). Algumas técnicas que auxiliam essas adaptações foram descritas na Tabela 2 (Roda Kanban; Rolling Kanban ; Kanban triangular). No contexto da empresa estudada, o estágio produtivo destinado à pintura (código - 2) realiza produção por lotes. Assim, por seguir o Sistema Kanban e em um dos estágios ocorrer produção por lotes, são necessárias adaptações. O estágio da pintura é composto por três máquinas, todas com capacidade de suportar mais de um kanban por processamento (produção por lotes). As máquinas 1 e 3 são responsáveis para aplicação da pintura propriamente dita e realização do acabamento. Já na máquina 2 realiza-se o processo de lixagem. Uma descrição de cada máquina e respetivo processo é feita a seguir. • Máquina 1 (M1) – Pintura Primária (21): Consiste em um processo de pintura mais fundamental. Níveis de detalhamento são menores caso apenas essa máquina for utilizada. Os tipos de acabamento proporcionados pelo subprocesso são “baratos” (valor monetário). E as cores usadas são “básicas” (preto e branco); • Máquina 2 (M2) – Lixagem (22): Necessária para todo fluxo que continuará no estágio da pintura pós pintura primária. É uma operação de apoio. Visa promover futura qualidade na fixação do acabamento e/ou tinta. Em outras palavras, é uma “limpeza” necessária para posterior pintura e/ou acabamento. Vale a ressalva que essa atividade retém um tempo maior de processamento que as outras duas; • Máquina 3 (M3) – Pintura Acabamento (23): Consiste em um processo de extremo detalhamento à peça. Diversos acabamentos e cores podem ser empregados nesta máquina. Os efeitos produzidos na peça são de alta qualidade, e, portanto, o material consumido por esta máquina é “caro” (valor monetário). 44 As vantagens de se produzir por lotes (de kanbans) no estágio da pintura se dá por: 1 – pela redução de gastos com material. Dado que existe uma quantidade mínima de material para funcionamento da máquina, o material não consumido será desperdiçado após o processamento, caso o próximo kanban dispor outra configuração (pintura ou acabamento); 2 – pela redução de tempos necessários para trocar as configurações da máquina. Se decorrer uma troca entre cores, a máquina precisará ser limpa. O mesmo acontece em caso de diferente acabamento, com tempo ligeiramente menor do que uma troca de cores. Claramente, a operacionalidade do estágio da pintura não funcionaria com as ferramentas destinadas à abordagem kanban. O sequenciador perder sua função, já que o fluxo FIFO não mais pode ser seguido. Mais, caso seja empregado o sequenciador, a visibilidade do operador para com elaboração dos lotes seria dificultada, pois sempre que fosse preciso elaborar o lote a produzir o operador teria de decidir a composição do lote conforme o acumulado de kanbans (terceiro posto do sequenciador). Esta decisão poderia requerer tempo e resultar em erros no reposicionamento no sequenciador, devido a poder haver uma grande quantidade de kanbans à espera de processamento. Portanto, pode-se afirma que o sequenciador no estágio da pintura é inefetivo. Um dos problemas da atual operação consiste no procedimento de receção dos produtos e kanbans no estágio da pintura. Atualmente este procedimento não é padronizado. Problemas são vistos por esta nãopadronização, principalmente devido ao fato de não existir um espaço específico para transmissão dos produtos (e respetivo kanban). Logo, o operador que leva os produtos até a pintura deposita em qualquer espaço físico disponível o produto e o kanban. Assim, quando se acumula diversos artigos (e kanbans) a visibilidade do operador é afetada pela dispersão em que os mesmos se encontram, não sendo possível o conhecimento, com absoluta certeza, dos itens que estão disponíveis para processamento. Como consequência, uma melhor composição dos lotes ou escalonamento de kanbans poderá não ser realizada. Quanto a composição dos lotes, atualmente, essa fundamenta-se na similaridade tecnológica entre os kanbans, buscando adiar a necessidade com longos setups (produtos com tecnologias diferentes). Entende-se por “tecnologia”, aplicada no estágio da pintura, a cor e acabamento que serão atribuídos a um item. Uma escala de preferência entre a execução seguida de dois kanbans pode ser sistematizada na Figura 12. 45 Figura 12 – Escala de preferência entre duas ordens a produzir (estágio – pintura) Portanto, de acordo com a Figura 12 se existir na fila para processamento na máquina 1 ou na máquina 3 um kanban para pintar com a mesma cor (do kanban em processamento) e mesmo acabamento, a preferência desse kanban ser o próximo a processar é máxima (1ª combinação). Ao contrário (4ª combinação), se nenhum kanban em espera para processamento coincidir com tinta e acabamento, um novo lote será processado (com alto tempo de setup ). Uma observação é importante para a 3ª combinação (*) (mesmo acabamento e diferente cor), se esse kanban precisar também pintar essa escala de preferência é quebrada. Ela se torna igual a última na escala de preferência. Motivo dado, pois caso necessite pintar, toda a máquina precisa ser reconfigurada (lavada) e o acabamento será perdido. Essa observação é válida devido a máquina 1 processar kanbans que necessitam apenas realizar um acabamento, logo, existe a possibilidade da 3ª combinação. Para simplificação, nesse trabalho um lote construiu-se levando em conta a família de cor, e dentro do lote, a sequência de processamento é liderada pela semelhança dos acabamentos. 3.2 Enquadramento do Estudo de Caso Antes de enquadrar o estudo de caso na classificação 𝛼|𝛽|𝛾, é necessária uma descrição aprofundada do processo da pintura. Feito, cada campo da classificação pode receber, com clareza, uma respetiva atribuição. A máquina 1 (M1) estabelece o início de todo o processo. Em outras palavras, qualquer ordem de produção que entra no estágio da pintura realizará a pintura primária (M1). Atualmente, o operador responsável por M1 é o realizador dos lotes de produção da mesma. Este operador leva em consideração os fatores tecnológicos (pintura e acabamento) descritos na Figura 12. Quando definido o lote a processar, o operador por meio do código de barras do kanban regista no sistema o início daquela(s) ordem(s). Para a máquina 3 (M3), o processo funciona idêntico à M1. A diferença é que a pilha de kanbans em M1 é originária dos estágios predecessores, enquanto em M3 a pilha estabelece-se pelo que foi processado a partir de M1. De maneira similar à M1, o operador responsável por M3 também é 52 Figura 13 – Continuidade temporal das tarefas/máquinas A partir da Figura 13b pode-se perceber que o aumento do makespan pela inclusão do procedimento de secagem. O termo “interrupção” foi utilizado para caracterizar uma descontinuidade das operações. Durante o período de secagem as máquinas estão “disponíveis”, porém ociosas. Diferentemente dos problemas clássicos de Escalonamento, esse intervalo de não-produção é um reflexo de um procedimento intermédio, e não uma espera de finalização na máquina predecessora. O efeito da existência do procedimento de secagem sobre o modelo de programação linear visto acima sugere duas inclusões (parâmetro e variável) e modificações nas restrições. A primeira inclusão é a do tempo de secagem 𝑠𝑒𝑐𝑗𝑘(parâmetro), e, portanto, o início de um lote na máquina sucessora deve ser s011 Máquina 1 J1J2J3J4 s122 Máquina 2 J1J2J3J4 s123 Máquina 3 J1J2J3J4 Tempo Makespan Máquina 1 s011 J1J2J3J4 Secagem s122 Máquina 2 J1J2 Interrupção J3J4 s123 Máquina 3 J1J2J3J4 Secagem Tempo Makespan Figura 13a Figura 13b Secagem J3 e J4 Secagem J1 e J2 Secagem J3 e J4 Secagem J1 e J2 s012 s013 Interrupção s012 s013 Família 1/ Lote 1 Família 2/ Lote 2 s121 Família 1/ Lote 1 Família 2/ Lote 2 s121 53 maior ou igual à conclusão das tarefas do respetivo lote na máquina predecessora mais o tempo de secagem entre a máquina predecessora e sucessora. Logo, podemos afirmar que existe uma data de lançamento como resultado do procedimento intermédio. Assim, 𝑟𝑗𝑘 será uma nova variável incluída (segunda inclusão) no modelo que representa a disponibilidade da tarefa 𝑗 ∈𝑁 na máquina 𝑘 ∈𝑀; formalizando, 𝑠𝑒𝑐𝑗𝑘 é tempo de secagem específico da tarefa 𝑗 ∈𝑁 pós a máquina 𝑘 ∈𝑀. Assim, forma-se a seguinte relação (restrição): 𝑟𝑗(𝑘+1) =𝐶𝑗𝑘 +𝑠𝑒𝑐𝑗𝑘, ∀ 𝑗∈𝑁; 𝑘 =1,…,𝑚−1 (15) Portanto, a disponibilidade de uma tarefa 𝑗 ∈𝑁 na máquina sucessora 𝑘+1 é igual ao tempo de conclusão da respetiva tarefa na máquina predecessora 𝑘 acrescido do tempo de secagem necessário pós processamento de 𝑗 em 𝑘. Como neste caso específico o procedimento de secagem também existe pós a última máquina (𝑚), assim makespan também deve ser modificado. Logo, pode-se escrever a quantificação do makespan para o caso como: 𝐶𝑚𝑎𝑥 ≥𝐶𝑗𝑚 +𝑠𝑒𝑐𝑗𝑚, ∀ 𝑗 ∈𝑁 (16) Além da quantificação da disponibilidade e novo makespan, têm-se a limitação do início de um lote (que deve ser maior ou igual à disponibilidade), portanto: 𝑇𝑏𝑘 ≥𝑟𝑗𝑘 −(1−𝑥𝑗𝑏(𝑘+1))∙𝑏𝑖𝑔𝑀, ∀ 𝑗∈𝑁; 𝑘 ∈𝑀; 𝑏 ∈𝐵 (17) Sendo o conjunto de restrições (17) a garantia de que um lote apenas inicie processamento de acordo com a disponibilidade. Dando seguimento as alterações por existência de procedimentos intermédios, o conjunto restrições (12) restringe o tempo de conclusão de uma tarefa para com o tempo de conclusão do seu respetivo lote. A relação criada funciona até a última máquina, pois como o tempo de conclusão pode ser maior ou igual ao respetivo lote da tarefa nada limita a quantificação certa do tempo de conclusão na última máquina. Para facilitar o entendimento, dar-se um exemplo: Cenário: Portanto, evidentemente a tarefa 𝑗=1 será finalizada antes de 𝑗=2, já que 𝑗 =1 está no primeiro lote da última máquina. Segundo o conjunto de restrições (12) têm-se a situação: 𝑘 =𝑚; 𝑛 =2; 𝑗=1∈𝐹 =1; 𝑥11𝑚=1 ; 𝑗=2∈𝐹 =2; 𝑥22𝑚=1; 𝑝1𝑚 =10; 𝑝2𝑚 =10; 𝑠12𝑚=10; 𝑇1𝑚 =200. 54 𝐶1𝑚 ≥200+1∙10−(1−1)∙𝑏𝑖𝑔𝑀 ∴𝐶1𝑚 ≥210, logo: 𝑇2𝑚 =210+10=220, assim, 𝐶2𝑚 ≥220+1∙10−(1−1)∙𝑏𝑖𝑔𝑀 ∴ 𝐶2𝑚 ≥230. Como o objetivo é de minimização tem-se 𝐶2𝑚 =𝐶𝑚𝑎𝑥 =230. Entretanto é visto que nada impede a quantificação de 𝐶1𝑚 entre 230≤𝐶1𝑚 >210. No modelo inicial proposto essa correção é feita pelo conjunto de restrições (14), como agora a quantificação do makespan foi substituída pelo conjunto (16) uma nova relação deve ser estabelecida para quantificação correta dos tempos de conclusão na última máquina. Sendo esta: 𝑇𝑏𝑘 +∑𝑥𝑖𝑏𝑘 𝑛 𝑖=1 ∙𝑝𝑖𝑘 ≥𝐶𝑗𝑘 −(1−𝑥𝑗𝑏𝑘)∙𝑏𝑖𝑔𝑀 , ∀ 𝑗 ∈𝑁;𝑏 ∈ 𝐵;𝑘 ∈𝑀 (12.1) Podendo concluir que o conjunto de restrições (18) serve como um complemento do conjunto de restrições (12). A partir do estudo de caso descrito no Capítulo 3, nota-se que as famílias variam entre estágios (similar Isenberg e Scholz-Reiter (2013)). Assim, uma modificação necessária é apenas a inclusão de um índice no parâmetro 𝛽𝑗𝑓. Portanto o novo parâmetro 𝛽𝑗𝑓𝑘 é 1 caso a tarefa 𝑗 ∈𝑁 pertença à família 𝑓 ∈ 𝐹 na máquina 𝑘 ∈𝑀; 0 caso contrário. Evidentemente, o conjunto de restrições (8) que faz presente esse parâmetro é alterado. Agora sendo: 𝑥𝑗𝑏𝑘 ≤𝛽𝑗𝑓𝑘 − 𝛽𝑖𝑓𝑘 − 𝑥𝑖𝑏𝑘 +2 , ∀ 𝑗 ∈𝑁; 𝑘 ∈𝑀; 𝑖 ∈𝑁; 𝑏 ∈𝐵; 𝑓 ∈𝐹 (8.1) Outro ponto relevante para esse conjunto de restrições (8.1) se dá por uma sugestão de melhoria aqui proposta. Seja essas restrições apenas relevantes para o caso de restringir que diferentes famílias habitem o mesmo lote, então tal condição pode ser simbolizada por: 𝑆𝑒 𝛽𝑗𝑓𝑘 + 𝛽𝑖𝑓𝑘 =1→𝛽𝑗𝑓𝑘 + 𝛽𝑖𝑓𝑘 ≥𝑥𝑗𝑏𝑘 +𝑥𝑖𝑏𝑘. Ou seja, quando as famílias forem diferentes (𝛽𝑗𝑓𝑘 + 𝛽𝑖𝑓𝑘 =1) então o máximo de 𝑥𝑗𝑏𝑘 +𝑥𝑖𝑏𝑘 é 1. Assim, o conjunto de restrições para esse tipo de situação poderia ser modelado na forma de implicação, porém, feito isso o modelo poderia ter uma performance abaixo do desejado. Uma outra forma é modelar da forma que o conjunto (8.1) sugere. Para essa forma a relação é capaz de proibir a seguinte situação: 𝛽𝑗𝑓𝑘 =0; 𝛽𝑖𝑓𝑘 =1;𝑥𝑖𝑏𝑘 =1 forçando 𝑥𝑗𝑏𝑘 ser 0. Entretanto uma falha é vista para a situação com: 𝛽𝑗𝑓𝑘 =1; 𝛽𝑖𝑓𝑘 =0;𝑥𝑖𝑏𝑘 =1, possibilitando 𝑥𝑗𝑏𝑘 ser 1 (combinação que não deveria ser possível). Para proibir essa combinação, a seguinte relação é proposta: 𝑥𝑗𝑏𝑘 ≤𝛽𝑖𝑓𝑘 − 𝛽𝑗𝑓𝑘 − 𝑥𝑖𝑏𝑘 +2 , ∀ 𝑗 ∈𝑁; 𝑘 ∈𝑀; 𝑖 ∈𝑁; 𝑏 ∈𝐵; 𝑓 ∈𝐹 (8.2) 55 Como pode ser observado, o conjunto de restrições (8.2) não seria capaz de proibir 𝑥𝑗𝑏𝑘 =1 para a combinação 𝛽𝑗𝑓𝑘 =0; 𝛽𝑖𝑓𝑘 =1;𝑥𝑖𝑏𝑘 =1. Porém, quando em conjunto com as restrições (8.1) ambas combinações elencadas acima tornam-se impossíveis. Até o presente momento, com as modificações sugeridas pode-se formalizar um modelo de programação linear para o escalonamento em um ambiente Flow shop com famílias de produtos, setups dependentes e máquinas processadoras de lotes ( serial batch ). Tendo as premissas de lote disponibilidade, processos intermédios e diferentes famílias por máquinas (estágios) sido introduzidas ao modelo. Outras dois modificações ainda podem ser feitas ao modelo, trazendo um caráter mais realístico ao modelo. A primeira é uma possibilidade de dividir um lote e processá-los em sequência. Essa situação foi ilustrada na Figura 7 (segundo e terceiro gráfico). Basicamente, se não houver benefício, seja este de tempo ou financeiro, o lote pode ser dividido e processado em sequência. Note que há uma diferença para a situação descrita em Shen e Gupta (2018), onde o lote pode ser dividido, porém, sendo o setup para processamento de uma mesma família zero (𝑠𝑔𝑔𝑘 =0) não faz sentido a divisão do lote e processamento seguido dos lotes dividido. Aqui no estudo, abre-se esta possibilidade, já que os setups entre troca de uma mesma família é diferente de zero (𝑠𝑔𝑔𝑘 >0). O reflexo desse adento apenas sugere uma modificação nos conjuntos do modelo e seguida remodelação destes nas restrições (11). A última ressalva sugere, talvez, a característica mais realista a introduzir no modelo. Na imensa maioria dos problemas de Escalonamento é considerado um horizonte temporal contínuo. Ou seja, os recursos estão disponíveis o tempo inteiro. Isto na verdade, na maioria dos ambientes, é uma simplificação. Por exemplo, trabalhadores realizam suas ações apenas durante os respetivos turnos de serviço, enquanto os problemas clássicos de escalonamento irá considerar uma disponibilidade temporal contínua. Assim, para o estudo de caso e respetiva adaptação, considerou-se os períodos que não se pode processar ordens. Isso implica diretamente na janela temporal da máquina 1, máquina 2 e máquina 3, em que a cada intervalo de tempo pré-definido as operações não poderão ser afetadas às máquinas. Entretanto, o mesmo não acontece com o procedimento de secagem, em que neste pode ser feito uso de horas nãoprodutivas . A Figura 14 ilustra as diferentes disponibilidades para Máquina 1, Máquina 2, Máquina 3 e respetivos procedimentos de secagem ao longo de um exemplo para 8 dias. 56 Figura 14 – Disponibilidade de tempo semanal A Figura 14 simula uma semana produtiva, seu sucessivo fim de semana e início de semana produtiva seguinte. Como visto, uma tarefa 𝑗∈𝑁 não pode ser executada em uma determinada máquina 𝑘 ∈𝑀 em uma janela temporal posterior às 8 horas produtivas do respetivo dia até o início do próximo dia produtivo. Por outro lado, o processo de secagem está sempre disponível. Assim, uma tarefa finalizada na máquina 1 ou máquina 3 e movida para secagem pode fazer uso integral do recurso temporal. A partir dessa particularidade entre procedimentos, o modelo matemático deve ser capaz de não permitir uma execução de uma tarefa 𝑗 ∈𝑁 em uma máquina 𝑘 ∈𝑀 durante horas não-produtivas. Uma solução para inserção dessa condição é a inclusão de tarefas fictícias. Essas tarefas devem ter o respetivo tempo de conclusão igual ao final de um dado dia e duração para processamento de 16 horas (para semana produtiva). Uma representação de tal proposta é exemplificada na Figura 15. Figura 15 – Escalonamento de tarefas fictícias ao longo do tempo As tarefas fictícias 𝑗1,…,𝑗10 portanto devem ser restritas quando ao tempo de conclusão em cada máquina. Além do mais, essas tarefas devem ser processadas individualmente, ou seja, o lote que contém uma dessas tarefas é composto apenas pela respetiva tarefa. Para que a composição do lote seja de uma tarefa basta indicar uma família diferente para cada tarefa fictícias. Uma importante observação vista na Figura 15, se dá para algumas tarefas que iniciam seu processamento pela máquina 2 ou máquina 3. Tal comportamento não pode ser permitido em ambientes Processo Máquina 1 Secagem Máquina 2 Máquina 3 Secagem 0 8 16 24 32 40 48 56 64 72 80 88 96 104 112 120 128 136 144 152 160 168 176 184 192 (Horas) Final dia 1 Final dia 2 Final dia 3 Final dia 4 Final dia 5 Final dia 6 Final dia 7 Final dia 8 Início dia 2 Início dia 3 Início dia 4 Início dia 5 Início dia 6 Início dia 7 Início dia 8 DISPONIBILIDADE DE TEMPO Processo Máquina 1 Secagem Máquina 2 Máquina 3 Secagem 0 8 16 24 32 40 48 56 64 72 80 88 96 104 112 120 128 136 144 152 160 168 176 184 192 (Horas) Final dia 1 Final dia 2 Final dia 3 Final dia 4 Final dia 5 Final dia 6 Final dia 7 Final dia 8 Início dia 2 Início dia 3 Início dia 4 Início dia 5 Início dia 6 Início dia 7 Início dia 8 J9 J10 J7 J7 J6 J6 J5 J5 J6 J5 J1 J1 J1 J2 J3 J4 J2 J5 J4 J6 J5 J4 DISPONIBILIDADE DE TEMPO J7 J8 57 Flow shop . Para contorno desta situação, designa-se os respetivos tempos de processamento e setups existentes como nulos. Claramente, para um escalonamento de um grande número de tarefas, um algoritmo deve ser desenvolvido para rápido criação e preenchimento no tempo das tarefas fictícias. Para concentrar as modificações, com exclusão do pormenor descrito na Figura 14 e Figura 15 (que requer, para melhor reprodução, inclusão de um procedimento heurístico), têm-se o novo modelo matemático: 𝑃𝑎𝑟â𝑚𝑒𝑡𝑟𝑜𝑠,Í𝑛𝑑𝑖𝑐𝑒𝑠 𝑒 𝐶𝑜𝑛𝑗𝑢𝑛𝑡𝑜𝑠: 𝑛: número de tarefas; 𝑗: índice para tarefas; 𝑚: número de máquinas; 𝑘: índice para máquinas; 𝑓: índice e número de famílias; 𝑔: índice de famílias; 𝑏: índice e número de lotes; 𝑁: conjunto de tarefas. 𝑁 ={1,…,𝑛}; 𝑀: conjunto de máquinas. 𝑀 ={1,…,𝑚}; 𝐹{𝑘 ∈𝑀}: conjunto de famílias na máquina 𝑘 ∈𝑀. 𝐹{𝑘} ={1,…,𝑓}; 𝐵: conjunto de lotes. 𝐵 ={1,…,𝑏}; 𝐽′{𝑘 ∈𝑀,𝑔 ∈𝐹{𝑘}}: conjunto de tarefas 𝑗 ∈𝑁 que pertencem a uma família 𝑔∈𝐹{𝑘} em 𝑘 ∈𝑀; 𝑝𝑗𝑘: denota o tempo de processamento de uma tarefa 𝑗∈𝑁 na máquina 𝑘 ∈𝑀; 𝐵𝑏𝑘: denota o 𝑏-néssimo (𝑏 ∈𝐵) lote processado em 𝑘 ∈𝑀. Exemplo: 𝐵11 representa o primeiro lote feito na máquina 1; 𝑠𝑓𝑔𝑘: denota o tempo gasto pela troca de processamento de um lote com tarefa(s) da família 𝑓 ∈𝐹{𝑘}∪{0} para a família 𝑔∈𝐹{𝑘} na máquina 𝑘 ∈𝑀. 𝑠0𝑔𝑘 representa o tempo necessário para iniciar o período produtivo a partir da família 𝑔∈𝐹{𝑘} em 𝑘 ∈𝑀; 𝛽𝑗𝑓𝑘: parâmetro que recebe o valor de 1 caso a tarefa 𝑗 ∈𝑁 pertença à família 𝑓 ∈𝐹{𝑘} na máquina 𝑘 ∈𝑀; 0 caso contrário; 𝑠𝑒𝑐𝑗𝑘: parâmetro para o procedimento de secagem. Tempo despendido para secar a tarefa 𝑗∈ 𝑁 pós processamento na máquina 𝑘 ∈𝑀; 𝑏𝑖𝑔𝑀: um número grande. 58 𝑉𝑎𝑟𝑖á𝑣𝑒𝑖𝑠 𝑑𝑒 𝑑𝑒𝑐𝑖𝑠ã𝑜: 𝑥𝑗𝑏𝑘: variável binária que recebe o valor 1 caso a tarefa 𝑗∈𝑁 for agrupada ao lote 𝑏 ∈𝐵 na máquina 𝑘 ∈𝑀, 0 caso contrário; 𝑇𝑏𝑘: quantifica o tempo do início do lote 𝐵𝑏𝑘; 𝐶𝑗𝑘: quantifica o tempo de conclusão da tarefa 𝑗 ∈𝑁 na máquina 𝑘 ∈𝑀; 𝑟𝑗𝑘: data de lançamento da tarefa 𝑗 ∈𝑁 na máquina 𝑘 ∈𝑀; 𝐶𝑚𝑎𝑥: quantifica o makespan. 𝑀𝑜𝑑𝑒𝑙𝑜: minimizar 𝐶𝑚𝑎𝑥 (6) sujeito a: ∑𝑥𝑗𝑏𝑘 𝐵 𝑏=1 =1 , ∀ 𝑗 ∈𝑁; 𝑘 ∈𝑀 (7) 𝑥𝑗𝑏𝑘 ≤𝛽𝑗𝑓𝑘 − 𝛽𝑖𝑓𝑘 − 𝑥𝑖𝑏𝑘 +2 , ∀ 𝑗 ∈𝑁; 𝑘 ∈𝑀; 𝑖 ∈𝑁; 𝑏 ∈𝐵; 𝑓 ∈𝐹{𝑘} (8.1) 𝑥𝑗𝑏𝑘 ≤𝛽𝑖𝑓𝑘 − 𝛽𝑗𝑓𝑘 − 𝑥𝑖𝑏𝑘 +2 , ∀ 𝑗 ∈𝑁; 𝑘 ∈𝑀; 𝑖 ∈𝑁; 𝑏 ∈𝐵; 𝑓 ∈𝐹{𝑘} (8.2) ∑𝑥𝑗1𝑘 𝑛 𝑗=1 ≥1 , ∀ 𝑘 ∈𝑀 (9) 𝑇1𝑘 ≥𝑠0𝑔𝑘 ∙𝑥𝑗1𝑘 , ∀ 𝑘 ∈𝑀;𝑔∈𝐹{𝑘};𝑗 ∈𝐽′{𝑘,𝑔} (10.1) 𝑇𝑐𝑘 ≥𝑇𝑏𝑘 + 𝑠𝑓𝑔𝑘 ∙𝑥𝑗𝑏𝑘 +∑∙𝑥𝑗′𝑏𝑘 ∙𝑝𝑗𝑘𝑗′∈𝐽′{𝑘,𝑓} −(1−𝑥𝑖𝑏𝑘)∙𝑏𝑖𝑔𝑀 , ∀ 𝑏 =1,…𝑏− 1; 𝑐 =2,…,𝑏; 𝑐 >𝑏;𝑘 ∈𝑀;𝑗∈𝐽′{𝑘,𝑓};𝑖 ∈ 𝐽′{𝑘,𝑔};𝑖 ≠𝑗; 𝑓 ∈ 𝐹{𝑘};𝑔∈𝐹{𝑘} (11.1) 𝐶𝑗𝑘 ≥𝑇𝑏𝑘 +∑𝑥𝑖𝑏𝑘 𝑛 𝑖=1 ∙𝑝𝑖𝑘 −(1−𝑥𝑗𝑏𝑘)∙𝑏𝑖𝑔𝑀 , ∀ 𝑗∈𝑁;𝑏 ∈ 𝐵;𝑘 ∈𝑀 (12) 𝑇𝑏𝑘 +∑𝑥𝑖𝑏𝑘 𝑛 𝑖=1 ∙𝑝𝑖𝑘 ≥𝐶𝑗𝑘 −(1−𝑥𝑗𝑏𝑘)∙𝑏𝑖𝑔𝑀 , ∀ 𝑗∈𝑁;𝑏 ∈ 𝐵;𝑘 ∈𝑀 (12.1) 𝑇𝑏(𝑘+1) ≥𝐶𝑗𝑘 −(1−𝑥𝑗𝑏(𝑘+1))∙𝑏𝑖𝑔𝑀 , ∀ 𝑗∈𝑁;𝑏 ∈ 𝐵;𝑘 =1,…,𝑚− 1 (13) 𝑟𝑗(𝑘+1) =𝐶𝑗𝑘 +𝑠𝑒𝑐𝑗𝑘, ∀ 𝑗 ∈𝑁; 𝑘 =1,…,𝑚−1 (15) 𝑇𝑏𝑘 ≥𝑟𝑗𝑘 −(1−𝑥𝑗𝑏(𝑘+1))∙𝑏𝑖𝑔𝑀, ∀ 𝑗∈𝑁; 𝑘 ∈𝑀; 𝑏 ∈𝐵 (17) 𝐶𝑚𝑎𝑥 ≥𝐶𝑗𝑚 +𝑠𝑒𝑐𝑗𝑚, ∀ 𝑗 ∈𝑁 (16) A partir da nova estruturação do modelo, alguns comentários devem ser feitos. Assim como explicado para o conjunto de restrições (8.1), (8.2) e (12.1), o conjunto de restrições (10.1) e (11.1) representam apenas alterações dos conjuntos (10) e (11) para a nova estrutura dos índices e conjuntos do modelo. 59 Além disso, a simbologia para os setups (𝑠𝑓𝑔𝑘) acompanha nestas restrições da variável 𝑥𝑗𝑏𝑘, representando a existência do setup apenas quando 𝑥𝑗𝑏𝑘 =1. 4.2 Heurística Proposta – NEH Modificada Ao passo do esclarecimento (Capítulo 2) que problemas de escalonamento podem ser resolvidos por métodos aproximados, o presente trabalho fez uso de uma heurística, nomeadamente uma modificação da NEH heurística, para solucionar o problema descrito. A NEH heurística é talvez a principal heurística no contexto de ambientes Flow shop . Obviamente, por se tratar de um método aproximado, a solução entregue pela NEH heurística não garante a solução ótima, mas diversos autores ( e.g. Dong et al. (2008) e Kalczynski e Kamburowski (2008)) elegem a NEH heurística como o melhor algoritmo construtivo para este tipo de ambiente ( Flow shop ) (W. Liu et al., 2017). No entanto, a NEH heurística foi desenvolvida para o já definido Flow shop regular, o que faz necessário modificações no algoritmo para receber e solucionar problemas Flow shop “não-regulares”. No que toca o estudo de caso, o conceito de famílias e consequentes setups são as principais modificações a serem inclusos no método. A começar pelo tratamento de famílias, a modificação da NEH heurística proposta aqui preocupa-se que o resultado do método seja o escalonamento destas famílias, utilizando o conceito de tecnologia de grupo . O escalonamento dentro da família não é de necessária preocupação. Este não precisa ser abordado já que se trata de um caso de lote disponibilidade . Como já pode ser avaliado, os conceitos de lotes inconsistentes e Non-permutation Flow shop não existe para o método, podendo, ou não, piorar o desvio da resposta com a resposta ótima. Pela inclusão dos setups , o trabalho tomou como base o conceito de tempo efetivo de processamento por máquina explicado em Schaller et al. (2000). Com o adento que foi necessária uma adaptação para cálculo do tempo efetivo de processamento, justificado por tarefas mudarem de famílias nas diferentes máquinas. O Algoritmo 1 norteia os passos para execução do método. As equações 18 e 19 suplementam o Algoritmo 1. Para maior exemplificação dos passos descritos no Algoritmo 1, o Apêndice A demonstra o pseudocódigo em Python 3.9.1 60 Algoritmo 1 NEH-Modificada Passo 1 Calcular o setup médio da família f ϵ F na máquina j (Equação 18) Passo 2 Calcular o tempo efetivo de processamento de cada família na máquina j (Equação 19) Passo 3 Classifique as famílias de acordo com os maiores tempos efetivos de processamento Passo 4 Classificar as duas famílias com maiores tempos efetivos de processamento e verificar qual sequência entre elas resulta em um menor makespan. Defina a sequência parcial como δ = (δ1, δ2) e faça i = 2 Passo 5 Para o restante das famílias inclua a seguinte família e desenvolva i+1 sequências parciais. Verifique qual das sequências resulta em um menor makespan , tornando a mesma a sequência parcial para i+1 famílias Passo 6 Verifique se i < K, se sim, faça i = i+1 e retorne ao passo 5; caso contrário o escalonamento foi definido com o respetivo makespan 𝑠𝑗𝑓 =(∑𝑠𝑓𝑥𝑗 𝐾 𝑥=1 )/𝐾 (18) 𝐸𝑓𝑗 = 𝑠𝑗𝑓 + ∑𝑝𝑥𝑗𝑥∈𝑁𝑓 (19) A adaptação necessária que diverge do dito em Schaller et al. (2000) consiste em ter em consideração que as tarefas pertencentes as famílias não são fixas ao longo das máquinas. Ou seja, o cálculo para o setup médio por máquina (Equação 18) não pode ser seguido como em Schaller et al. (2000). Para contorno da situação, o presente trabalho propôs que a somatória ocorra em função de uma matriz tarefa x família exemplificada abaixo. 1 0 0 0 0 0 1 0 0 0 1 0 1 0 0 0 0 1 1 0 0 0 1 0 0 1 0 0 0 0 0 1 0 0 0 0 1 0 1 0 0 0 0 1 0 0 0 0 1 0 1 0 0 0 0 1 0 1 0 0 1 0 0 0 0 0 0 1 0 1 0 0 61 Na situação exemplificada, 12 tarefas pertencem a 6 famílias. Em um cenário “padrão” a somatória das linhas seria 1, representando que cada tarefa tem apenas uma família. Nesta adaptação uma tarefa pode “trocar” de família durante o processo produtivo. O exemplo é dado por uma situação com 3 máquinas em que na primeira máquina existem 2 famílias e 6 famílias nas restantes máquinas. As duas famílias da primeira máquina podem ser consideradas como origem, e são representadas pelas primeiras duas colunas da matriz acima. Na linha dois tem o primeiro exemplo de tarefa com “duas famílias”. Para a tarefa 2 (linha dois) é visto que esta pertence as famílias 1 e 5, ou seja, na primeira máquina esta tarefa pertence à família 1 e nas restantes máquinas à família 5. Da mesma forma dita para a linha 2, as linhas 3,4,7,9,10 e 12 são exemplos similares. A partir da matriz explicada no parágrafo anterior, o funcionamento da NEH heurística, nomeadamente passo 4, tenderá a ter famílias de “origem” como as duas selecionadas para compor a primeira sequência parcial. No entanto, como o restante do método baseia-se na inserção de tarefas nas possíveis posições, duas famílias de “origem” dificilmente serão adjacentes (nas duas primeiras posições a processar), demonstrando coerência na adaptação. Evidentemente que para o cálculo do makespan a matriz exemplificada não pode ser utilizada, assim, portanto, considera-se apenas as famílias “finais” das tarefas, e não as de “origem”, portanto, uma nova matriz é vista com soma de linhas igual a 1. Outra nota importante que diverge do descrito em Schaller et al. (2000) está na equação 18. No que representa o setup de mudança de família 𝑠𝑓𝑥𝑗 (𝑓 →𝑥) em Schaller et al. (2000) aparece como 𝑠𝑥𝑓𝑗(𝑥 →𝑓). Essa mudança é representativa para o cálculo do tempo efetivo de processamento (equação 19) e consequente conclusão no passo 4. A mudança proposta aqui é justificada devido o objetivo de construir uma solução (a partir da primeira máquina), logo, não faz sentido avaliar o setup médio de uma família despendido entre famílias anteriores a esta família 𝑥 →𝑓. Sendo então, necessário avaliar setups para famílias que sucedem aquela 𝑓 →𝑥. Sumarizando, a Equação 18 fundamental para os passos de 1-4 atua sob a lógica da matriz descrita, tendo o tempo efetivo de processamento (Equação 19) como resultado da Equação 18 acrescido do tempo de processamento de todas as tarefas que compõe a família avaliada (∑𝑝𝑥𝑗𝑥∈𝑁𝑓). Uma importante nota sobre a utilização da NEH-Modificada se dá em virtude da mesma ser idealizada para a situação de estudo descrita. Onde, deve-se ter atenção que o nível de customização aumento ao longo das máquinas. Outras palavras, a quantidade de família na máquina 1 é menor que na máquina 3. Portanto, para replicação da NEH-Modificada é necessário encontrar a máquina com maior quantidade 68 Tabela 5 – Resultados das instâncias iniciais Para a Tabela 5 as seguintes segregações podem ser feitas: 1a tabela encontra-se divida entre resultados fixos relativos às instâncias; 2resultados variantes do solucionador utilizado. Entre os solucionadores testados têm-se o GUROBI e o CPLEX. Como pode-se apercebe-se pela Tabela 5, o solucionador GUROBI para instâncias entre VD01 e VD07 foi relativamente melhor no tocante ao tempo computacional. Para a instância VD09, o CPLEX apresentou um tempo computacional menor, no entanto, o resultado foi obtido com um GAP (desvio da resposta) maior que zero. Para as seguintes instâncias (VD10 e VD11), no qual possuem dez ou mais tarefas, o tempo regulamentado como máximo pelo NEOS SERVER foi ultrapassado. Para encontrar uma resposta mesmo assim (denominada solução incumbente), estabeleceu-se um tempo máximo (tempo no qual o solucionador para de procurar resposta) de 8 horas (288000 segundos), e foi possível observar certa similaridade no GAP para ambos solucionadores. Em destaque na Tabela 5, a instância VD08 foi o principal ponto de diferença entre os solucionadores, sendo a mesma destacada na Tabela 5. Para esta instância, o GUROBI necessitou aproximadamente de 1 hora e 20 minutos, enquanto para o CPLEX o máximo de tempo determinado pelo NEOS SERVER foi excedido. Para comprovar essa observação, mais dez experimentos foram realizados com o CPLEX e a instância VD08, no qual todos excederam o máximo de tempo. Como última observação relevante, fazendo uma junção entra a Tabela 4 e Tabela 5, a partir das instâncias VD08 e VD09, pode-se notar-se que a diminuição da possibilidade do número de lotes influencia fortemente no tempo computacional. Instância Nome Tempo Total Gap Tempo Total Gap Quantidade Restrições Não-zeros Variáveis Lineares Variáveis Binárias VD01 00:00:01 0% 00:00:03 0% 62 176 13 8 VD02 00:00:01 0% 00:00:01 0% 106 336 17 12 VD03 00:00:02 0% 00:00:02 0% 167 573 19 18 VD04 00:00:02 0% 00:00:02 0% 394 1580 25 32 VD05 00:00:02 0% 00:00:15 0% 447 1548 34 36 VD06 00:00:01 0% 00:00:02 0% 655 2380 37 48 VD07 00:00:13 0% 00:00:13 0% 2571 11352 55 108 VD08 01:20:31 0% 08:02:02 Máx Tempo Permitido 7531 35864 73 192 VD09 00:01:43 0% 00:01:17 0,006025% 4659 21216 67 144 VD10 08:02:07 Máx Tempo Permitido 08:02:03 Máx Tempo Permitido 17103 98480 91 300 VD11 08:02:10 Máx Tempo Permitido 08:02:01 Máx Tempo Permitido 35175 199440 109 432 VD10* 08:00:00 31,60% 08:00:00 27,99% 17103 98480 91 300 VD11* 08:00:00 44,30% 08:00:00 41,69% 35175 199440 109 432 Gurobi CPLEX * Instância com restrição de 28800 segundos para encontro da solução. 69 5.2 Relação: estudo de caso x modelo matemático Após os testes efetuados com as instâncias inicias fica claro que o modelo matemático proposto só comporta instâncias pequenas. A Figura 18 representa o comportamento no quesito tempo para cada uma das instâncias, com o adento da quantidade de restrições no passar das instâncias. Figura 18 – Tempo para solução e quantidade de restrições por instância A partir de instâncias com dez tarefas, em consonância com a Figura 18, pode ver-se que o modelo não é capaz fornecer uma resposta em 8 horas (28800 segundos) e, portanto, a respetiva aplicação em alguns cenários pode ser completamente inviável. Seja por não fornecer uma resposta ou fornecer uma resposta (solução incumbente) de baixa qualidade. Vale mais uma vez lembrar que as instâncias inicias foram simplificadas para ser possível a elaboração da Tabela 4 e facilitar a ilustração para o leitor. As instâncias, mesmo com menos de dez tarefas, poderiam ser mais complexas com um maior número de máquinas e divergência de famílias por máquinas, crescendo horizontalmente o modelo da Tabela 4. Mesmo que a partir de um determinado número de tarefas, máquinas ou famílias o modelo mostre-se inviável, pode existir cenários que onde o número de tarefas, máquinas ou famílias seja baixo, e, portanto, o modelo seja uma solução (ótima) para solucionar o problema de escalonamento. Dado o impasse, é necessário verificar o histórico das ocorrências na empresa estudada, especificamente no estágio produtivo da pintura. Assim, antes de mais, como mencionado que diversos fluxos existem na organização (Capítulo 3 – página 53), deve-se ter em conta os principais fluxos existentes e observar 70 quais estágios antecedem o estágio da pintura nestes fluxos. Em outras palavras, ter em consideração o estágio que origina a procura evidenciada no estágio da pintura. A Figura 19 sumariza a quantidade de processamento de produtos para cada um dos fluxos vistos na imagem (eixo Y). Figura 19 – Contagem por fluxo produtivo Pela Figura 19 é visto que 548 processos para fabrico de produtos não tem um fluxo definido. Logo, considerar esses fluxos seria uma ação de incerteza para o respetivo estudo, sendo estes, por opção, excluídos do estudo. A maior ocorrência está no fluxo 27, porém, este reside apenas no estágio 3 (Acabamento) – não ocorrendo necessariamente um processamento (nem entrada no estágio 2), sendo este também excluído do estudo. Após as duas maiores incidências, têm-se os fluxos 12 e 59 (destacados na Figura 19), com o número de processamento similares. Os dois fluxos são descritos, respetivamente o fluxo 12 e 59, no lado direito da Figura 19, compondo assim os estágios 11-12-13-2-3 para o fluxo 12 e 12-14-13-2-5 para o fluxo 59. Sendo também possível observar que para ambos os fluxos o estágio que antecede o estágio da pintura é o estágio 13 (trabalho manual). Assim, para saber a real necessidade, e poder, ou não, empregar o modelo exato no estágio da pintura, deve-se avaliar a quantidade de kanbans que saem do estágio 13 e se direcionam para o estágio da pintura. Para tal visualização, a Figura 20 sintetiza no período de março de 2020 e janeiro de 2021 quanto a quantidade de kanbans que processados no estágio 13, portanto, que seguiram o fluxo produtivo para o estágio da pintura. 71 Figura 20 – Contagens de kanbans estágio 13 Pode-se, pela Figura 20, observar a existência de uma média (linha constante no eixo y) de 6,86 saídas de kanbans. Assim, usando apenas a média como fator de decisão, o modelo exato deveria ser empregado, seja que para as instâncias testadas (n = 8) o modelo ainda fornece resposta ótima em tempo aceitável. Porém, também pode ser visualizado diversos valores acima de 10 tarefas e um valor máximo de 27 saídas. Sendo, portanto, necessário recorrer a um método mais rápido e eficiente computacionalmente para encontro de um escalonamento. Em outra palavras, a utilização de uma heurística (ou qualquer modelo aproximado) é completamente apropriado, devido a Figura 20 apresentar diversos valores acima de 10 tarefas. 5.3 Experimentos Computacionais – NEH-Modificada Para avaliação da NEH-Modificada realizou-se um estudo do desempenho, nomeadamente o tempo computacional para encontro da solução, da heurística NEH-modificada (explicada no Capítulo 4). O estudo deu-se para instâncias de tamanho igual a instância VD11 (maior instância avaliado sob a ótica do modelo matemático), possibilitando de certa forma comparar com o modelo matemático e instâncias de grandes tamanhos. O resultado do tempo computacional da NEH-Modificada foi esquematizado na Tabela 6, enquanto a Figura 21 ilustrou graficamente os resultados da Tabela 6. Mais, o estudo deu-se com desenvolvimento do algoritmo na linguagem computacional Python em sua versão 3.9.1, fazendo, principalmente, uso da biblioteca Numpy. A máquina utilizada para os experimentos foi um Intel-Core i7 2.80GHz 16GB RAM 72 Tabela 6 – Resultados NEH-Modificada Figura 21 – Tempo de solução por instâncias NEH-Modificada Ao avaliar os resultados da Tabela 6, pode-se perceber que a heurística apresentou tempos computacional na ordem 10−3 e 10−2 segundos, sendo, portanto, aplicacional no tocante do tempo necessário para o encontro de uma solução. Para a Figura 21, nota-se relevância visual ao adicionar uma máquina na instância com 500 tarefas, evidenciando que um aumento das máquinas pode ser um estudo relevante, devido o impacto em segundos no acréscimo de uma máquina no problema. Os resultados da Tabela 6 e Figura 21 fundamental uma questão importante do estudo. Inicialmente, deve-se destacar a potencialidade do uso de modelo aproximados por motivo do baixo custo computacional para encontro da solução. No trabalho de Koulamas (1998) a NEH Heurística em sua forma original necessitou de 4 𝑥 10−2 segundos para obter uma solução em uma instância de 5 Tarefas (n) Máquinas (m) Tempo (s) 12 3 0,00192118 25 3 0,00299668 27 3 0,00300217 50 3 0,00499153 75 3 0,00501299 150 3 0,00904441 300 3 0,00992346 500 3 0,01304746 500 4 0,01440692 1000 4 0,02590775 73 máquinas e 200 tarefas. No presente estudo, um modelo com maiores adaptações e peculiaridades consome menos de 1 𝑥 10−1 segundos para obter uma solução em uma instância de 3 máquinas e 300 tarefas. Evidenciando que, passado 20 anos os modelos aproximados melhoraram sua performance (possivelmente consoante a evolução tecnologia) e continuam a consumir pouco recurso temporal para obter soluções (para o problema de escalonamento Flow shop ) independente do fato do tamanho das instâncias. Após explicação da NEH-modificada e respetiva adequação quanto ao algoritmo, fica claro que uma comparação direta com o modelo matemático só seria possível com adaptação do mesmo, devido fatores como secagem não foram incluídas na heurística. Assim, definindo um gap da resposta ótima e resposta da heurística como a percentagem sob a resposta ótima que resulta da diferença entre o valor da heurística e modelo matemático (Equação 20), a Tabela 7 concentrou tais resultados de forma a compará-los. Vale a ressalva que as instâncias foram nomeadas igualmente, com quantidade de tarefas, máquinas e famílias iguais, porém, nestas existem as modificações citadas acima (exclusão do tempo de secagem). 𝐺𝑎𝑝 (%)= 𝑉𝑎𝑙𝑜𝑟 𝐴𝑝𝑟𝑖𝑥𝑖𝑚𝑎𝑑𝑜− 𝑉𝑎𝑙𝑜𝑟 ó𝑡𝑖𝑚𝑜 𝑉𝑎𝑙𝑜𝑟 ó𝑡𝑖𝑚𝑜 𝑥 100 (20) Tabela 7 – Modelo Exato vs Modelo Heurístico A partir da Tabela 7, pode-se notar-se que o maior desvio visto foi de 24% (instância VD04). Mais, ocorreu para três instância resultados iguais ao proposto pelo modelo exato. Outro ponto de extrema relevância é dado por existir uma situação onde a heurística superou o resultado encontrado pelo modelo Instância Nome MILP (F.O) NEH (F.O) GAP(%) VD01 139 139 0% VD02 170 170 0% VD03 179 182 2% VD04 104 129 24% VD05 293 293 0% VD06 266 293 10% VD07 231 233 1% VD08 260 279 7% VD09 260 279 7% VD10* 315 351 11% VD11* 412 402 -2% * Instâncias cujo os resultados do modelo exato representam soluções incumbentes 74 matemático (instância VD11). Para esta instância e instância VD10 foi preciso, assim como visto na Tabela 5, recorrer ao limite de tempo do NEOS SERVER, obtendo-se, portanto, as respetivas soluções incumbentes (ou seja, a melhor solução encontrada até o momento em que o processo de otimização é interrompido). Obviamente, estas soluções podem não ser ainda a solução ótima (no caso da instância VD11 pode-se afirmar que não é a solução ótima), justificando um resultado de pior qualidade por parte do método exato, em outra perspetiva, justificando o fato do modelo heurístico apresentar uma resposta de melhor qualidade. A comparação descrita na Tabela 7 serve também para expor a tendência para o problema estudado ser Np-Hard . O abrupto crescimento exponencial do tempo de solução entre as instâncias VD09 e VD10 fortalece a teoria à custa deste repentino de crescimento ser característico da classe Np-Hard . Logo, pondo em causa que o uso dos modelos aproximados, em paralelismo com um estudo que sustenta a qualidade do modelo, deve ser sempre proposto para contornar a ineficiência e ineficácia dos modelos exatos. 5.4 Enquadramento – Rolling Kanban Nesta secção abortou o enquadramento, de maneira descritiva, da ferramenta visual Rolling Kanban . Para tal, considerou-se a instância (sem tempo de secagem) VD08 (2x). Portanto, a situação descritiva conta com 16 tarefas com planeamento produtivo para 1 semana. O quadro Rolling Kanban idealizado conta com 5 segmentados desse horizonte (5 dias), descritos como “A” “B” “C” “D” e “E”. Todos os valores para tempos nas instâncias são considerados em minutos. Inicialmente apenas a instância VD08 se encontra para processamento no início do período genérico idealizado (Figura 22). Assim, para início, 8 tarefas devem ser escalonadas. De acordo com o que foi visto, para essa instância o modelo exato pode ser utilizado. Como resposta obteve um escalonamento com função objetivo de 260 (minutos) e última família processada a família 1. 75 Figura 22 – Exemplo Rolling Kanban Face a situação simulada, têm-se que durante esse primeiro processamento mais 8 tarefas idênticas chegaram dos estágios predecessores (Figura 23). A primeira resposta que deve-se ter é se essas 8 tarefas podem ser feitas no restante do horizonte produtivo descrito. Se uma semana é composta por 2400 minutos, obviamente que é possível o processamento dessas 8 tarefas. No entanto, nota-se ao processar novamente essas 8 tarefas, a somatória decorrida será no mínimo 520 minutos, logo, mais que a secção “B” permite (1 dia produtivo – 480 minutos). Nesse caso a sequência deve ser seguida na mesma e continuada no dia seguinte. Um ponto importante aqui é perceber que a família 1 finalizou a primeira produção, assim existirá um setup a acontecer, pode-se nesses casos considerar então que 𝑠0𝑓1 >0 e a família 0 é a família 1 na máquina 1. Neste caso específico caso a sequência se mantém, com o adento que a função objetivo foi de 290 devido o setup mencionado (𝑠0𝑓1 =30). Assim, é possível observar que este segundo sequenciamento deverá ser finalizado no primeiro dia analisado e continuado no dia posterior. Consequentemente pelo que consiste o Rolling Kanban , o marcador irá para “C”, a coluna “B” fica vazia (no início do dia) e após um total de 550 minutos (“A” + parte de “B”) uma nova resposta pelo modelo deve ser executada. 76 Figura 23 – Escala de preferência entre duas ordens a produzir (estágio – pintura) Finalizando a adaptação do modelo para a ferramenta de controlo visual, caso mais de 10 trabalhos necessitem ser sequenciados, deve-se ser feito uso do método heurístico, e, caso visualize a possibilidade de cumprimento no horizonte temporal estabelecido (uma semana) os “novos” trabalhos devem ser retirados do modelo respeitando aqueles que a mais tempo estão à espera do respetivo processamento. 77 6. CONCLUSÕES Produção Lean , Sistema Kanban, Kanban são filosofias vastamente implementados pelas organizações nos tempos atuais. Visando a redução do desperdício e sendo capaz de abordar conceitos qualitativos e quantitativos durante a respetiva utilização, o universo de estudo para estes temas pode ser classificado com atual e em constante desenvolvimento. Entretanto, como visto neste estudo, o Rolling Kanban é uma poderosa ferramenta para estas áreas de estudos, mas que pouco foi comentada em contexto académico. Partindo deste ponto, a presente dissertação cumpre com um dos seus objetivos que consiste em trazer mais uma possibilidade de implementação, mais, exemplifica a forma mais básica de utilização da ferramenta. Todavia, as ferramentas lean tendem a serem implementadas em contextos cada vez mais complexos. No caso de estudo trazido pelo trabalho, um dilema existe devido a empresa em questão usar do Sistema Kanban, porém um dos estágios não pode seguir à risca o Sistema idealizado na companhia Toyota. Assim, o trabalho desenvolveu como portar-se diante da adaptação, e como fazer uso da ferramenta. Não só para o estudo de caso preocupou-se o presente trabalho. É possível perceber que uma extensa revisão da literatura foi realizada no tocante a Produção Lean , Sistema Kanban e respetivas ferramentas de controlo visual. Promovendo, portanto, outras possibilidades de replicação para um tema que visivelmente colabora para controlo e efetividade produtiva. Do mesmo sentido, porém, para Escalonamento, uma extensa revisão dos principais temas e diferentes situações foi feita. Se preocupando principalmente com o ambiente Flow shop , o estudo trouxe importantes conceitos que ajudam a área de Escalonamento na tentativa de maior utilização prática. Abordou-se também exemplos de métodos para resolução de tais problemas. Para os métodos de resolução, na opinião do autor, este ponto consiste na maior contribuição científica do trabalho. Especialmente para o modelo de programação linear mista, já que o desenvolvimento do modelo final engloba temáticas que podem ser facilmente vistas em outras situações. Mais, a adaptação do modelo trouxe à tona importantes conceitos debatidos somente em um único trabalho anterior, e que desde então não foram desenvolvidos por outros autores. Outro ponto a destacar foi provar por dados reais a necessidades em certos casos de modelos aproximados. A NEH-Modificada foi desenvolvida neste caso especial e entra para lista de casos de extensão do modelo original. A partir desta extensão, o objetivo geral foi atingido, quando, modelo exato e/ou aproximado enquadraram-se na ferramenta Rolling Kanban . A união da ferramenta e modelo foi 84 and complexity. Journal of the Operational Research Society . https://doi.org/10.1057/jors.1992.66 Potts, Chris N., & Kovalyov, M. Y. (2000). Scheduling with batching: a review. In European Journal of Operational Research . https://doi.org/10.1016/S0377-2217(99)00153-8 Potts, Chris N., Shmoys, D. B., & Williamson, D. P. (1991). Permutation vs. non-permutation Flowshop schedules. Operations Research Letters . https://doi.org/10.1016/0167-6377(91)90014-G Pruhs, K., Sgall, J., & Torng, E. (2004). Online scheduling. In Handbook of Scheduling: Algorithms, Models, and Performance Analysis . https://doi.org/10.1201/9780429428890-20 Pugazhendhi, S., Thiagarajan, S., Rajendran, C., & Anantharaman, N. (2003). Performance enhancement by using non-permutation schedules in flowline-based manufacturing systems. Computers and Industrial Engineering . https://doi.org/10.1016/S0360-8352(02)00189-4 Rabadi, G., Msakni, M. K., Rodriguez-Velasquez, E., & Alvarez-Bermudez, W. (2019). New characteristics of optimal solutions for the two-machine Flowshop problem with unlimited buffers. Journal of the Operational Research Society . https://doi.org/10.1080/01605682.2018.1475114 Rad, S. F., Ruiz, R., & Boroojerdian, N. (2009). New high performing heuristics for minimizing makespan in permutation Flowshop s. Omega . https://doi.org/10.1016/j.omega.2007.02.002 Reza Hejazi, S., & Saghafian, S. (2005). Flowshop -scheduling problems with makespan criterion: A review. In International Journal of Production Research . https://doi.org/10.1080/0020754050056417 Ríos-Mercado, R. Z., & Bard, J. F. (2003). The Flowshop Scheduling Polyhedron with Setup Times. Journal of Combinatorial Optimization . https://doi.org/10.1023/A:1027372722187 Rossi, A., & Lanzetta, M. (2014). Native metaheuristics for non-permutation Flowshop scheduling. Journal of Intelligent Manufacturing . https://doi.org/10.1007/s10845-012-0724-8 Rossit, D., Tohmé, F., Frutos, M., Bard, J., & Broz, D. (2016). A non-permutation Flowshop scheduling problem with lot streaming: A mathematical model. International Journal of Industrial Engineering Computations . https://doi.org/10.5267/j.ijiec.2015.11.004 Rossit, Daniel A., Vásquez, Ó. C., Tohmé, F., Frutos, M., & Safe, M. D. (2021). A combinatorial analysis of the permutation and non-permutation Flowshop scheduling problems. European Journal of Operational Research . https://doi.org/10.1016/j.ejor.2019.07.055 Rossit, Daniel Alejandro, Tohmé, F., & Frutos, M. (2018). The Non-Permutation Flow-Shop scheduling problem: A literature review. In Omega (United Kingdom) . https://doi.org/10.1016/j.omega.2017.05.010 Rossit, Daniel Alejandro, Tohmé, F., & Frutos, M. (2019a). An Industry 4.0 approach to assembly line resequencing. International Journal of Advanced Manufacturing Technology . https://doi.org/10.1007/s00170-019-03804-0 Rossit, Daniel Alejandro, Tohmé, F., & Frutos, M. (2019b). Industry 4.0: Smart Scheduling. International Journal of Production Research . https://doi.org/10.1080/00207543.2018.1504248 Rossit, Daniel Alejandro, Toncovich, A., Rossit, D. G., & Nesmachnow, S. (2021). Solving a Flowshop scheduling problem with missing operations in an Industry 4.0 production environment. Journal of Project Management . https://doi.org/10.5267/j.jpm.2020.10.001 Rudan, J., Kersbergen, B., Van Den Boom, T., & Hangos, K. (2013). Performance analysis of MILP based 85 model predictive control algorithms for dynamic railway scheduling. 2013 European Control Conference, ECC 2013 . https://doi.org/10.23919/ecc.2013.6669393 Salmasi, N., Logendran, R., & Skandari, M. R. (2010). Total flow time minimization in a Flowshop sequence-dependent group scheduling problem. Computers and Operations Research . https://doi.org/10.1016/j.cor.2009.04.013 Savsar, M. (1997). Simulation analysis of a pull-push system for an electronic assembly line. International Journal of Production Economics . https://doi.org/10.1016/S0925-5273(97)00055-8 Schaller, J. (2012). Scheduling a permutation Flowshop with family setups to minimise total tardiness. International Journal of Production Research . https://doi.org/10.1080/00207543.2011.575094 Schaller, J. E., Gupta, J. N. D., & Vakharia, A. J. (2000). Scheduling a flowline manufacturing cell with sequence dependent family setup times. European Journal of Operational Research . https://doi.org/10.1016/S0377-2217(99)00387-2 Seidman, T. I., & Holloway, L. E. (2002). Stability of pull production control methods for systems with significant setups. IEEE Transactions on Automatic Control . https://doi.org/10.1109/TAC.2002.803531 Seidmann, A. (1988). Regenerative pull (Kanban) production control policies. European Journal of Operational Research . https://doi.org/10.1016/0377-2217(88)90230-5 Shen, L., & Buscher, U. (2012). Solving the serial batching problem in Job shop manufacturing systems. European Journal of Operational Research . https://doi.org/10.1016/j.ejor.2012.03.001 Shen, L., & Gupta, J. N. D. (2018). Family scheduling with batch availability in Flowshop s to minimize makespan. Journal of Scheduling . https://doi.org/10.1007/s10951-017-0529-x Shen, L., Gupta, J. N. D., & Buscher, U. (2014). Flowshop batching and scheduling with sequencedependent setup times. Journal of Scheduling . https://doi.org/10.1007/s10951-014-0369-x Sivakumar, G. D., & Shahabudeen, P. (2009). Algorithms for the design of a multi-stage adaptive kanban system. International Journal of Production Research . https://doi.org/10.1080/00207540802302071 Smalley, A. (2009). Connecting Assembly with Batch Process Via Basic Pull System. Management Science/Operation Research . Sohal, A. S., Keller, A. Z., & Fouad, R. H. (1989). A Review of Literature Relating to JIT. International Journal of Operations & Production Management . https://doi.org/10.1108/eum0000000001228 Srikar, B. N., & Ghosh, S. (1986). A milp model for the n-job, m-stage Flowshop with sequence dependent set-up times. International Journal of Production Research . https://doi.org/10.1080/00207548608919815 Stefansdottir, B., Grunow, M., & Akkerman, R. (2017). Classifying and modeling setups and cleanings in lot sizing and scheduling. European Journal of Operational Research . https://doi.org/10.1016/j.ejor.2017.03.023 Stoop, P. P. M., & Wiers, V. C. S. (1996). The complexity of scheduling in practice. In International Journal of Operations and Production Management . https://doi.org/10.1108/01443579610130682 Strusevich, V. A., & Zwaneveld, C. M. (1994). On non-permutation solutions to some two machine Flowshop scheduling problems. ZOR Zeitschrift Für Operations Research Mathematical Methods of Opeartions Research . https://doi.org/10.1007/BF01435460 86 Sugimori, Y., Kusunoki, K., Cho, F., & Uchikawa, S. (1977). Toyota production system and kanban system materialization of just-in-time and respect-for-human system. International Journal of Production Research . https://doi.org/10.1080/00207547708943149 Tang, L., & Zhao, Y. (2008). Scheduling a single semi-continuous batching machine. Omega . https://doi.org/10.1016/j.omega.2007.11.003 Throughput Optimization in Robotic Cells. (2007). In Throughput Optimization in Robotic Cells . https://doi.org/10.1007/0-387-70988-6 Tseng, F. T., & Stafford, E. F. (2001). Two MILP models for the N × M SDST Flowshop sequencing problem. International Journal of Production Research . https://doi.org/10.1080/00207540010029433 Uzsoy, R. (1995). Scheduling batch processing machines with incompatible job families. International Journal of Production Research . https://doi.org/10.1080/00207549508904839 Van Der Krogt, R., Geraghty, J., Salman, M. R., & Little, J. (2010). On supporting Lean methodologies using constraint-based scheduling. Journal of Scheduling . https://doi.org/10.1007/s10951-0090144-6 Van Der Zee, D. J. (2013). Family based dispatching with batch availability. International Journal of Production Research . https://doi.org/10.1080/00207543.2012.756590 Van Veen-Dirks, P. (2005). Management control and the production environment: A review. International Journal of Production Economics . https://doi.org/10.1016/j.ijpe.2004.06.026 Wagner, H. M. (1959). An integer linear-programming model for machine scheduling. Naval Research Logistics Quarterly . https://doi.org/10.1002/nav.3800060205 Wang, H., & Hsu-Pin (Ben) Wang. (1991). Optimum number of kanbans between two adjacent workstations in a JIT system. International Journal of Production Economics . https://doi.org/10.1016/0925-5273(91)90093-9 Wang, J. Q., Fan, G. Q., & Liu, Z. (2020). Mixed batch scheduling on identical machines. Journal of Scheduling . https://doi.org/10.1007/s10951-019-00623-9 Webster, S., & Baker, K. R. (1995). Scheduling groups of jobs on a single machine. Operations Research . https://doi.org/10.1287/opre.43.4.692 Womack, J. P., Jones, D. T., & Roos, D. (1990). The machine that changed the world, Rawson Associates. New York . Wu, C. C., Gupta, J. N. D., Cheng, S. R., Lin, B. M. T., Yip, S. H., & Lin, W. C. (2020). Robust scheduling for a two-stage assembly shop with scenario-dependent processing times. International Journal of Production Research . https://doi.org/10.1080/00207543.2020.1778208 Zou, Y., Wang, D., Lin, W. C., Chen, J. Y., Yu, P. W., Wu, W. H., Chao, Y. P., & Wu, C. C. (2020). Twostage three-machine assembly scheduling problem with sum-of-processing-times-based learning effect. Soft Computing . https://doi.org/10.1007/s00500-019-04301-y 87 APÊNDICE A – PSEUDOCÓDIGO NEH-MODIFICADA Pseudocódigo (Python) - NEH-Modificada import numpy as np import time n = tarefas m = maquinas k = familias #type(k) = list K = len(k) def makespan(sequencia, batch_time, setups) #calculo do makespan def batch_time(matriz_1_0_familia_tarefa, tempos_processamento) #calculo do tempo para processamento do lote def setup_medio(setups) #media do setup da familia por maquina a = batch_time(matriz_1_0_familia_tarefa, tempos_processamento) b = setup_medio(setups) c = a+b a1 = batch_time(matriz_1_0_familia_tarefa_mod, tempos_processamento) #matriz modificada (igual pagina 62 do trabalho) #encontrar as 2 familias com maior tempo efetivo de processamento schedule = [] for i in range(K): schedule.append(0) for f in range(K): schedule[f] = sum(c[:,f]) j=[] schedule1 = schedule.copy() schedule1.sort(reverse = True) for i in schedule1: rodada = 0 for p, k in enumerate(schedule): if i == k: if rodada ==0: j.append(p) rodada = rodada + 1 else: rodada =0 continue # se empate 88 while sum(j)<sum(k): for p, i in enumerate(j): b= j.copy() b.remove(i) if i in b: j[p] = i+1 #further delta = j.copy() delta = [j[0], j[1]] #first schedule: first_make = makespan(delta, a1, Setups) if makespan(delta[::-1], a1, Setups_fam) < first_make: delta = delta[::-1] fase = 2 while fase < K: o = j[fase] for i in range(fase+1): if i ==0: delta.insert(i, o) delta1 = delta.copy() makespan(delta, a1, Setups_fam) resp = [delta1, makespan(delta, a1, Setups_fam)] delta.remove(o) else: delta.insert(i, o) delta1 = delta.copy() if makespan(delta, a1, Setups_fam) < resp[1]: resp = [delta1, makespan(delta, a1, Setups_fam)] delta.remove(o) else: delta.remove(o) delta = resp[0] fase = fase+1 print(resp) print('Tempo computacional: {} segundos'.format(time.time() - t1)) 89 APÊNDICE B – FORMULAÇÃO AMPL