UNESP UNIVERSIDADE ESTADUAL PAULISTA “JÚLIO DE MESQUITA FILHO” CAMPUS DE GUARATINGUETÁ FACULDADE DE ENGENHARIA DE GUARATINGUETÁ JOSÉ LUIZ ELISEI SEQUENCIAMENTO DE LOTES EM PRENSAS DE ALTA CAPACIDADE COM TEMPO DE SETUP DEPENDENTE DA SEQUÊNCIA Guaratinguetá 2012 JOSÉ LUIZ ELISEI SEQUENCIAMENTO DE LOTES EM PRENSAS DE ALTA CAPACIDADE COM TEMPO DE SETUP DEPENDENTE DA SEQUÊNCIA Dissertação apresentada à Faculdade de Engenharia do Campus de Guaratinguetá, Universidade Estadual Paulista, para a obtenção do título de Mestre em Engenharia Mecânica na área de Projetos e Materiais. Orientador: Prof. Dr. Edson Luiz França Senne Guaratinguetá 2012 E43s Elisei, José Luiz Sequenciamento de lotes em prensas de alta capacidade com tempo de setup dependente da sequência / José Luiz Elisei. – Guaratinguetá : [s.n.], 2012 111 f. : il. Bibliografia: f. 82-87 Dissertação (mestrado) – Universidade Estadual Paulista, Faculdade de Engenharia de Guaratinguetá, 2012 Orientador: Prof. Dr. Edson Luiz França Senne 1. Otimização combinatória I. Título CDU 519.863 DEDICATÓRIA Dedico a Cristina, André, Raquel, Ângelo, Luiz e Hilda, que deram sentido à minha vida, fazendo de mim algo melhor. AGRADECIMENTOS No mundo dependemos de todos. Nossos esforços são somados à energia divina, viva em cada ser com que nos deparamos e essa energia se materializa, por isso agradecer deve ser um exercício constante, a cada momento de nossa existência. Agradeço ao meu amigo e orientador prof. Senne, que tem em seu comportamento a lição maior a nos ensinar. Aos professores Marins, Delamaro, Jorge, Messias, Cassilda, Salomon, Marcos Pereira e Galeno por seus esforços, que tanto fizeram por esse programa. Aos funcionários da FEG que sempre me atenderam com boa vontade. A meu chefe e amigo Rodolfo que compreendeu e me deu o espaço necessário para continuar. Ao aluno Viktor Otto Schwarzmeier, pela implementação na linguagem C do algoritmo heurístico proposto neste trabalho. Agradeço a meus pais, que deram sua vida por nós. E finalmente à minha família, que pagaram alto custo nessa jornada, mas me entenderam e apoiaram em todos os momentos. ELISEI,J.L. Sequenciamento de lotes em prensas de alta capacidade com tempo de setup dependente da sequência. 2012. 111 f. Dissertação (Mestrado em Engenharia Mecânica) – Faculdade de Engenharia do Campus de Guaratinguetá, Universidade Estadual Paulista, Guaratinguetá, 2012 RESUMO O presente trabalho é fruto da observação de um problema real encontrado em uma indústria de autopeças, que produz peças estampadas em aço para caminhões, automóveis e tratores, utilizando prensas de alta capacidade. As prensas utilizadas necessitam de um ferramental, que precisa ser montado na prensa antes de começar a produção. Devido a esse fato, o setup de uma prensa pode variar de acordo com a sequência de produção que for realizada. Além disso, como o ferramental é único, quando uma peça está sendo produzida em uma prensa, outra peça que utilize o mesmo ferramental não poderá ser produzida em qualquer outra prensa. Neste trabalho procurou-se resolver o problema de programação da produção para esta indústria, que caracteriza-se como um problema de sequenciamento com máquinas paralelas e com tempo de setup dependente da sequência de produção. Para resolver tal problema, foram formulados alguns modelos matemáticos para obtenção de soluções exatas. No entanto, como trata-se de um problema de Otimização Combinatória NP- difícil, foi desenvolvido também um método heurístico híbrido utilizando as técnicas VND (Variable Neighborhood Descent) e ILS (Iterated Local Search) para a obtenção de soluções para grandes exemplares do problema em um tempo computacional razoável. Palavras-chave: Otimização Combinatória, Problema de sequenciamento, Setup dependente da sequência, Formulação matemática, Método heurístico híbrido. ELISEI,J.L. Scheduling batches in high capacity presses with setup time sequence dependent. 2012. 111 f. Dissertation (Master in Mechanical Engineering) – Faculdade de Engenharia do Campus de Guaratinguetá, Universidade Estadual Paulista, Guaratinguetá, 2012 ABSTRACT The present work is based on a real world problem found in the auto parts industry, which produces steel stamped parts for trucks, cars and tractors, using high- capacity presses. The presses used need a tooling that has to be mounted on the press before production begins. Because of this, the setup of a press can vary according to the sequence of production that is performed. Moreover, as the tooling is unique for each type of auto part, when an auto part is being produced on a press, another auto part of the same type can not be produced in any other press. In this work one tried to solve the problem of production scheduling for a specific plant, which is characterized as a scheduling problem with parallel machines and sequence-dependent setup times. To solve this problem, some mathematical models were formulated to obtain exact solutions. However, as the problem is a NP-hard Combinatorial Optimization problem, a hybrid heuristic method was also developed, using the techniques VND (Variable Neighborhood Descent) and ILS (Iterated Local Search) to obtain approximate solutions for large problem instances in a reasonable execution time. Keywords: Combinatorial Optimization, Scheduling problem, Sequence-dependent setup, Mathematical formulation, Hybrid heuristic method. LISTA DE FIGURAS Figura 1 - Ambientes de máquina............................................................................. 24 Figura 2 - Gestão da produção da empresa em estudo.............................................. 40 Figura 3 - Sequenciamentos obtidos com o Modelo III.......................................... 67 Figura 4 - Comportamento de heurística de refinamento (Fonte: Souza, 2008).... 69 Figura 5 - Heurística VND........................................................................................ 70 Figura 6 - Algoritmo ILS.......................................................................................... 71 Figura 7 - Processo de perturbação (Fonte: Souza, 2008)........................................ 71 Figura 8 - Algoritmo proposto.................................................................................. 72 Figura 9 – Representação de solução ...................................................................... 72 Figura 10 – Representação de solução viável ........................................................ 73 Figura 11 - Criação da solução inicial...................................................................... 73 Figura 12 - Procedimento VND................................................................................ 74 Figura 13 - Metaheurística ILS................................................................................. 75 Figura 14 - Sequenciamentos obtidos com o algoritmo heurístico........................... 77 LISTA DE TABELAS Tabela 1 - Base de dados para o Teste 1................................................................... 46 Tabela 2 - Tempos de setup de uma peça para outra para o Teste 1......................... 46 Tabela 3 - Sequenciamento obtido no Teste 1.......................................................... 46 Tabela 4 - Resultados obtidos no Teste 1.................................................................. 47 Tabela 5 - Sequenciamento obtido no Teste 2.......................................................... 49 Tabela 6 - Resultados obtidos no Teste 2.................................................................. 49 Tabela 7 - Sequenciamento obtido no Teste 3.......................................................... 50 Tabela 8 - Resultados obtidos no Teste 3.................................................................. 51 Tabela 9 - Sequenciamento obtido no Teste 4.......................................................... 51 Tabela 10 - Resultados obtidos no Teste 4................................................................ 52 Tabela 11 - Resultados obtidos no Teste 5................................................................ 53 Tabela 12 - Parâmetros das peças............................................................................. 54 Tabela 13 - Tempo de setup...................................................................................... 54 Tabela 14 - Incompatibilidade entre peças................................................................ 54 Tabela 15 - Sequenciamento obtido no Teste 5........................................................ 55 Tabela 16 - Resultados obtidos no Teste 5................................................................ 55 Tabela 17 - Comparativo Xpress versus CPLEX...................................................... 56 Tabela 18 - Comparação das características dos modelos........................................ 57 Tabela 19 - Conversão de variáveis.......................................................................... 58 Tabela 20 - Setup de uma peça para outra................................................................. 62 Tabela 21 - Demanda por peça.................................................................................. 62 Tabela 22 - Incompatibilidade entre peças................................................................ 62 Tabela 23 - Setup inicial por peça............................................................................. 62 Tabela 24 - Resultados obtidos com os Modelos I e II............................................. 62 Tabela 25 - Sequenciamentos obtidos com os Modelos I e II................................... 63 Tabela 26 – Resultados dos novos testes computacionais........................................ 63 Tabela 27 - Resultados obtidos com o Modelo III - Solver Xpress ........................ 66 Tabela 28 - Resultados preliminares obtidos com o algoritmo heurístico................ 76 Tabela 29 - Resultados obtidos com o algoritmo heurístico..................................... 78 SUMÁRIO 1. INTRODUÇÃO..................................................................................... 13 1.1 Justificativa............................................................................................ 14 1.2 Determinação dos objetivos.................................................................. 15 1.2.1 Objetivo geral........................................................................................ 15 1.2.2 Objetivos específicos............................................................................. 15 1.2.3 Classificação da pesquisa...................................................................... 15 1.2.4 Estruturação do trabalho........................................................................ 16 2. REVISÃO BIBLIOGRÁFICA.............................................................. 18 2.1 Gestão de produção............................................................................... 18 2.1.1 EDI – Electronic Data Interchange...................................................... 18 2.1.2 MRP – Material Requeriment Planning............................................... 19 2.1.3 JIT – Just in Time.................................................................................. 20 2.2 Problemas de produção......................................................................... 21 2.2.1 Sequenciamento de produção................................................................ 21 2.2.2 Modelos de sequenciamento de produção............................................. 23 2.2.3 Ambiente de máquina............................................................................ 23 2.2.4 Tempo de preparação de máquina......................................................... 25 2.2.5 Horizonte de planejamento.................................................................... 25 2.2.6 Número de produtos.............................................................................. 26 2.2.7 Restrição por capacidade....................................................................... 26 2.2.8 Deterioração de um produto.................................................................. 26 2.2.9 Demanda................................................................................................ 26 2.2.10 Falta de estoque..................................................................................... 27 2.3 Problemas de dimensionamento de lotes .............................................. 27 2.4 Estudos sobre dimensionamento de lote e sequenciamento.................. 28 2.5 Problemas de sequenciamento de lotes................................................. 30 3. MODELOS MATEMÁTICOS PROPOSTOS...................................... 38 3.1 Descrição do problema.......................................................................... 38 3.2 O processo produtivo............................................................................. 38 3.3 A Gestão da produção na empresa em estudo....................................... 39 3.4 Os modelos matemáticos ...................................................................... 42 3.5 Modelo I: minimização do tempo total de setup................................... 43 3.5.1 Testes computacionais com o Modelo I................................................ 46 3.6 Modelo II: minimização do tempo total de setup.................................. 57 3.7 Modelo III: minimização do makespan................................................. 65 4. HEURÍSTICA PROPOSTA.................................................................. 68 4.1 O algoritmo heurístico híbrido proposto............................................... 72 4.2 Testes computacionais........................................................................... 75 5. CONCLUSÃO....................................................................................... 79 Referências Bibliográficas.................................................................................. 82 Apêndice A: Modelo I formulado na linguagem Mosel..................................... 87 Apêndice B: Alterações implementadas no Modelo I........................................ 91 Apêndice C: Modelo II formulado na linguagem Mosel................................... 93 Apêndice D: Modelo III formulado na linguagem Mosel.................................. 97 Apêndice E: Dados utilizados nos testes computacionais do Modelo III......... 102 Apêndice F: Resultados para um exemplar real do problema............................ 106 13 1. INTRODUÇÃO O crescimento que vem ocorrendo nos últimos anos nas indústrias montadoras de automóveis, caminhões e tratores tem seu reflexo nas indústrias de autopeças. Esta, conforme site do Sindicato das Indústrias de Autopeças-Sindipeças, teve em 2009 um crescimento em seu faturamento de 11,8% sobre o de igual período de 2007. O principal segmento de mercado responsável por isso foram as montadoras, com participação de 70% nas vendas e o volume de faturamento em 2009 na casa dos 6 bilhões de reais. Dentro do cenário de globalização, a demanda de insumos exige tanto qualidade quanto prazo de entrega, atendendo às mais modernas práticas internacionais. No campo da gestão da produção, a metodologia JIT (Just-in-Time) vem evoluindo para o chamado JIS (Just-in-Sequence), sistema de abastecimento, capaz de atender não só os itens necessários, na quantidade necessária e no momento determinado, mas também na sequência certa (TROQUE e PIRES, 2003). Este tipo de prática faz com que o planejamento de produção tenha que ser ágil na geração e na revisão da sequência de produção. Neste trabalho considera-se um problema prático observado em uma fornecedora de peças estampadas para a indústria automobilística. A base da estrutura de um caminhão é composta de chassi e travessas, em que todo o caminhão é montado. Estas peças são feitas de chapas de aço estampadas ou dobradas, dependendo do formato da peça. Se a peça tiver maior complexidade em seu formato com curvas, esta deve ser feita em prensas; se ela não tiver grande complexidade poderá ser feita em máquinas que contorcem o metal. Aqui considera-se somente os processos em estamparia nos quais as prensas que realizam esse processo são de alta capacidade, variando de 3000 a 5200 toneladas. Neste trabalho são propostos modelos de Programação Matemática que exprimem a realidade deste processo de planejamento de produção. Apesar de estar analisando uma empresa em particular, atende-se a problemas vividos por inúmeras empresas, mesmo de outros setores. 14 1.1 - Justificativa O ambiente aqui descrito, máquinas paralelas, sequenciamento de produção e setup de máquina, ocorre em uma quantidade muito grande de empresas. A solução de problemas com essa característica tem sido estudada ao longo dos anos e diversos avanços vem sendo observados, tanto no campo da programação heurística quanto na melhora dos softwares de mercado como Xpress, Gams, CPLEX etc. Existe uma grande influência do processo em estudo no restante da empresa. Com este processo pode-se relacionar: Como realizado atualmente, o trabalho de programar a produção leva muito tempo e não existe a possibilidade de reprogramação, caso haja necessidade. Hoje em dia as solicitações dos clientes por alterações emergenciais ocorrem em grande quantidade. Na própria empresa a necessidade ocorre quando falta matéria prima ou quebra de algum equipamento que recai sobre esta célula de produção. Necessidade de se ter um aproveitamento maior dos recursos. Investir em novos equipamentos e ampliação de uma linha de produção é muito caro. Havendo a possibilidade de um melhor aproveitamento dos recursos atuais, isso deve ser feito. O cálculo atualmente é feito em planilhas, o que não assegura que a solução obtida é a melhor possível. 15 1.2 - Determinação dos objetivos 1.2.1 - Objetivo geral Desenvolver um algoritmo que proporcione ganhos reais na programação de prensas, buscando assim, a aplicação de metodologias de Pesquisa Operacional a problemas combinatórios de interesse prático. 1.2.2 - Objetivos específicos Os objetivos específicos deste trabalho são os seguintes: Evidenciar o potencial da modelagem matemática para resolver problemas comumente encontrados em processos industriais. Desenvolver e validar modelos matemáticos, comparando-os a outros obtidos em trabalhos já publicados. Desenvolver um método heurístico híbrido para obter uma boa solução do problema em estudo. Analisar comparativamente as soluções exatas obtidas pelas formulações matemáticas e as boas soluções obtidas pelo método heurístico proposto. 1.2.3 - Classificação da pesquisa Segundo Gil (1999), a pesquisa tem um caráter pragmático, é um processo sistemático de desenvolvimento do método científico e seu objetivo é descobrir respostas para problemas fazendo uso de procedimentos científicos. Existem várias classificações para as pesquisas. A classificação dessa pesquisa é a seguinte: Pesquisa Aplicada, pois objetiva gerar conhecimentos para aplicação prática dirigida a solução de problemas específicos. Envolve verdades e interesses locais; 16 Quantitativa, pois considera-se que tudo pode ser quantificado, o que significa traduzir, em números, opiniões e informações para classificá-las e analisá-las; Exploratória, pois visa proporcionar maior familiaridade com o problema com vistas a torná-lo explícito ou a construir hipóteses. Envolve levantamento bibliográfico; entrevista com pessoas que tiveram experiências práticas com o problema pesquisado; análise de exemplos que estimulem a compreensão. 1.2.4 - Estruturação do trabalho Este trabalho está organizado em 5 capítulos. O Capítulo 1 apresentou o contexto em que o trabalho se insere, a justificativa de porque abordar o problema em estudo, os objetivos do trabalho e o método de pesquisa utilizado. O Capítulo 2 apresenta a revisão bibliográfica, tendo como objetivo reunir as informações fundamentais para o entendimento dos conceitos aqui observados. Estes conceitos são, basicamente, a otimização no sequenciamento de produção e a gestão de produção, e visam caracterizar a relevância do problema no contexto da administração de produção. No Capítulo 3 é apresentado o desenvolvimento de um modelo matemático cujo objetivo é a minimização de todos os tempos de produção. Este modelo é testado em dois solvers: Xpress e CPLEX. Seus resultados são comparados para efeito de análise de desempenho e resultado. Após este teste o modelo criado é comparado a um outro, adaptado de uma solução já publicada. Na segunda parte deste capítulo, o modelo original é alterado para controlar o makespan e depois comparado a uma solução desenvolvida com base nas metaheurísticas ILS e VND. No Capítulo 4 apresenta-se um algoritmo heurístico híbrido para o problema estudado. Nesta etapa contou-se com a colaboração de um bolsista de Iniciação Científica que implementou o algoritmo proposto com base nos dados apresentados neste trabalho. 17 No Capítulo 5 são apresentadas a conclusão final do trabalho e algumas propostas para estudos futuros. 18 2. REVISÃO BIBLIOGRÁFICA 2.1 - Gestão de produção A gestão de produção é a principal função da empresa. Segundo Slack et al. (2002), ela consiste em buscar o objetivo principal da empresa, a razão pela qual ela existe. Ela é responsável por toda a cadeia produtiva, do fornecedor até a entrega ao cliente. Uma das etapas dessa gestão é o Planejamento e Controle da Produção (PCP). O PCP é o responsável pelo atendimento às demandas de longo prazo, que denota compras de matéria prima, e curto prazo, que é relativo à preparação de máquinas e alocações de mão de obra. Em apoio ao PCP duas ferramentas se destacam, o MRP (Material Requeriment Planning) e o EDI (Electronic Data Interchange) para planejamento de compras e programação de produção, respectivamente. A origem dos dados ocorre no cliente que envia, através de processos EDI, sua necessidade de consumo e sua programação de entrega. Esta por sua vez vai alimentar o MRP que gera ordens de compra de matéria prima e ordens de produção. 2.1.1 - EDI – Electronic Data Interchange O EDI é uma modalidade de troca de informações entre empresas atendendo a formatos padrões previamente acordados entre as partes (GOMES e RIBEIRO, 2004). O EDI foi adotado primeiramente nos Estados Unidos dentro das lojas de varejo e de empresas de transporte e, mais tarde, passou para as indústrias de automóveis e autopeças. Ao invés de emitir documentos em papel, a empresa pode transmiti-los eletronicamente direto de seu computador para o computador do fornecedor. Este tipo de processo aumenta em muito a produtividade devido a fatores como: 19 Não há necessidade de manuseio por nenhum usuário, consequentemente a informação que sai de um sistema alimenta o outro sem risco de erro de digitação; Rapidez no processo. Uma vez automatizado o processo, não existe mais demora, pois todo ele transcorre via redes e sistemas integrados; Registro confiável de toda a informação. Não há a possibilidade de que a informação seja perdida. Os processos de EDI mais usados pelas montadoras de automóveis e seus fornecedores são: Programação de entrega – Dá uma visão completa de longo prazo das necessidades do cliente; Programação diária – Visão de curto prazo das necessidades do cliente. Nesta modalidade se encaixam operações como JIT (Just in Time) e JIS (Just in Sequence). Aviso de embarque – Documento detalhado sobre a mercadoria expedida. Semelhante a uma nota fiscal eletrônica. Serve para agilizar a entrada da mercadoria na empresa receptora. 2.1.2 - MRP – Material Requeriment Planning Conforme Slack et al. (2002), o MRP (Material Requeriment Planning) é uma ferramenta para cálculo das necessidades de matéria prima. Sua base de informação são as solicitações dos clientes e as previsões de vendas. O sistema verifica a lista de materiais necessários à produção e leva em consideração o saldo dos estoques para gerar a lista de faltas. Em paralelo a todo este processo são considerados os tempos de reabastecimento de matéria prima, perdas em produção e compras já realizadas. Sua lógica é baseada no programa mestre de produção, na lista de materiais e na quantidade em estoque. O programa mestre de produção (MPS – Master 20 Production Scheduling) consiste na definição das quantidades de cada produto final que se deseja produzir em cada período (“time bucket”) dentro de um horizonte de planejamento EDI. A lista de materiais está baseada na estrutura dos componentes do produto final. No princípio da concepção, nos anos 1970, a utilização do MRP encontrava bastante dificuldade com relação ao custo de software e hardware, mas com o tempo, a superação desses problemas levou à necessidade de integrar a ele o controle sobre a capacidade de produção, o que implica em considerar roteiros de produção (sequência e tempos das diferentes tarefas das ordens de produção) e um cadastro dos centros de produção com as respectivas capacidades. Desta forma tornou-se possível verificar a capacidade dos centros ao longo do tempo e consequentemente a viabilidade dos programas de produção. Este novo modelo foi chamado de MRP II – Manufacturing Resources Planning. Uma das dificuldades do MRP está em trabalhar com “janelas de tempo” (time bucket) diferentes dos modelos de simulação por evento. Isto faz com que ele não consiga representar, em detalhes, as sequências das operações da fábrica. Os modelos matemáticos usando técnicas de sequenciamento e programação de produção obtêm bons resultados nesta área, mas não se encontra no mercado a integração destes com o MRP. 2.1.3 - JIT – Just in Time O JIT (Just in Time) surgiu logo após a segunda Guerra Mundial nas indústrias japonesas (CERRA e BONADIO, 2000). O objetivo dessa ferramenta é gerenciar o fluxo de peças (a peça necessária, na quantidade necessária, no instante e local necessário). Algumas características naturais do JIT fazem com que a pressão aumente no fornecedor de matéria prima. Uma delas é a produção puxada, o cliente diz quando quer uma mercadoria; outra é uma consequência da produção enxuta, que é o baixo estoque. 21 2.2 - Problemas de produção Dentro de uma empresa, a tomada de decisão sobre problemas de produção se dá em três possíveis níveis: operacional, tático e estratégico (ARAUJO e ARENALES, 2000; LAUDON e LAUDON, 2004). O nível estratégico é o mais alto na hierarquia e está ligado à decisões de longo prazo, metas, escolhas de produtos a produzir etc.; o nível tático, o segundo na hierarquia, tem como foco a visão de poucas semanas e a tomada de decisão de nível médio; e o nível operacional trabalha diretamente na linha de produção e seu período é de poucos dias. Um processo como o sequenciamento de produção e dimensionamento de lotes pode ser considerado entre os níveis operacional e tático. É importante para um melhor entendimento do planejamento e da programação de produção, o esclarecimento de uma série de termos e conceitos conforme faz-se a seguir. 2.2.1 Sequenciamento de produção Conforme Davis (1990) e Absi e Kedad-Sidhoum (2008), o processo de sequenciamento vem sendo estudado desde os anos 50. Sua aplicabilidade abrange desde transporte até produção de bens. Seu objetivo é a alocação de recursos ou atividades dentro de um período de tempo. É importante esclarecer que a palavra "sequenciamento" está sendo usada neste trabalho em referência à determinação da sequência e tempo inicial quando um processo é realizado por uma máquina. Em inglês este termo é denominado scheduling, diferente de sequence, que é somente a sequência de processamento. Os primeiros trabalhos de sequenciamento de produção, em sua maioria, eram voltados a sistemas baseados em máquinas simples. Alguns desses trabalhos 22 derivaram da regra da data de vencimento mais antiga (EDD - Early Due Data), na qual as tarefas (na literatura inglesa referenciadas como jobs) são sequenciadas na ordem cronológica da data de vencimento mais antiga para a mais nova. Outros derivaram da regra do tempo de processamento de menor peso (SWPT – Short Weighted Processing Time), na qual as tarefas são sequenciadas na ordem crescente de tempo de processamento (POTTS e KOVALYOV, 2000). Conforme Stoop e Wiers (1996), o planejamento de chão de fábrica costuma desviar-se do esperado devido a fatores imprevisíveis como: Quebra de máquina; Falta de material; Valores inexatos do tempo de produção. Quanto à quebra de máquina, o problema pode ter sua incidência reduzida por meio da manutenção preventiva. Outros fatores, como os relacionado à gerência de pessoas como férias, licença maternidade, podem ser controladas, mas acidentes e doenças não há como. O segundo tipo de problema refere-se a ordens emergenciais, atrasos na entrega pelo fornecedor, problemas externos impossíveis de se prever. O terceiro problema ocorre, entre outras causas, devido à especialização de um operador, mudança de produto, falta de avaliação de novo modelo. As pesquisas sobre problemas de sequenciamento reconhecem que o problema é complexo e classificam o problema como NP-difícil (NP-hard). A classificação de um problema como NP-difícil sugere que sua solução exige algoritmos, cujos tempos de execução crescem exponencialmente com o tamanho do problema, como por exemplo, os algoritmos branch-and-bound. Assim, em alguns casos, como em exemplares pequenos, esses algoritmos conseguem resolver os problemas de forma ótima. No entanto, na prática, os exemplares do problema são de grandes dimensões e deve-se aceitar o fato de se ter apenas soluções aproximadas para o problema. 23 2.2.2 - Modelos de sequenciamento de produção Um problema de sequenciamento pode ser definido como a forma de processar J tarefas em M máquinas. Uma solução para um problema de sequenciamento deve definir para cada máquina m e para cada tarefa j, os instantes de tempo em que a máquina m processa a tarefa j. Admite-se em problemas de sequenciamento que uma tarefa não pode ser executada em duas máquinas ao mesmo tempo, e que uma máquina não pode executar duas tarefas ao mesmo tempo. Além destas restrições gerais, para cada problema específico a solução deve satisfazer a uma série de restrições relativas ao problema. O tipo de problema é especificado pelo ambiente da máquina, as características da tarefa e o critério de otimalidade. 2.2.3 - Ambiente de máquina Com relação ao ambiente de máquina pode-se considerar que os ambientes são de estágio simples ou de multi-nível. A produção em estágio simples requer uma operação para cada tarefa, ao passo que na produção em ambiente multi-nível há tarefas que requerem operações em diferentes máquinas. O termo máquina pode ser substituído por centro de trabalho, unidade produtiva etc. A produção em estágio simples envolve ambientes com uma ou mais máquinas operando paralelamente. Para máquinas paralelas podem ser consideradas as seguintes características (MULLER et al., 2002): máquinas paralelas idênticas, quando existe um conjunto único contendo os tempos de execução das tarefas e esses tempos de execução permanecem constantes não importando para qual máquina a tarefa é atribuída; máquinas paralelas uniformes, quando existe um conjunto único contendo os tempos de execução das tarefas, mas os tempos de execução são alterados por um único fator uniforme dependendo da tarefa ser executada em uma máquina ou em outra; 24 máquinas paralelas não relacionadas, quando tem-se uma série de máquinas que diferem entre si na capacidade e no tempo, mas que, com alguma alteração podem realizar o mesmo trabalho. Considera-se como estágio, ou níveis dentro de uma linha de produção, a etapa pela qual um produto tem que passar. Diz-se que um produto é de estágio simples (single-level) quando este produto passa somente por uma etapa para ficar pronto. Quando um produto passa por vários níveis para ficar pronto, diz-se tratar de um produto multi-estágio (multi-level). Problemas multi-estágios são bem mais complexos do que os de nível simples. Segundo Arenales et al. (2007), um tipo de ambiente multi-estágio é conhecido como job shop, em que as máquinas estão dispostas em vários níveis e existe uma sequência pré-determinada de estágio a ser obedecida para a produção de um produto. Outra modalidade de ambiente multi-estágio é o flow shop, em que uma peça deve passar por várias máquinas, mas sem a necessidade de obedecer a uma sequência pré-estabelecida. A Figura 1 apresenta uma classificação de ambientes de máquina. Figura 1 – Ambientes de máquina 25 2.2.4 - Tempo de preparação de máquina Conforme Dauzère-Peres e Lasserre (2002), setup é o termo utilizado para designar o trabalho de preparar uma máquina ou processo para a produção. Isto inclui obter ferramentas, posicionar o material para o processamento, limpeza, inspeção etc. O setup foi considerado por algum tempo e para alguns autores como insignificante ou parte do tempo de processo. Apesar disso ser justificado para alguns problemas, em outros ele precisa ser considerado. O setup pode ser para um processamento em lote (batch) ou não (non-batch). O tempo de setup por lote ocorre quando as tarefas são produzidas em lote e um setup precede cada um desses lotes. Conforme notação de Dauzère-Peres e Lasserre (2002), neste caso, as tarefas são particionadas em F famílias, com F > 1. Segundo Allahverdi et al. (1999), um setup é dependente da sequência se sua duração (ou custo) depende tanto da tarefa corrente como da tarefa que a precede imediatamente. O setup é independente da sequência se sua duração (custo) depende somente da tarefa em execução. Allahverdi et al. (1999) destacam a importância da análise do tempo de setup dependente de sequência quando a ocupação da máquina está perto de sua capacidade total e a importância de se considerar o setup para um efetivo gerenciamento dos estoques e da capacidade produtiva, pois o controle do setup tem forte ação sobre a redução dos níveis de estoques. 2.2.5 - Horizonte de planejamento Para problemas de planejamento de produção o horizonte de planejamento é sempre finito e a demanda associada a ele pode ser dinâmica (pode se alterar no horizonte de planejamento) ou estática. Além disso, o horizonte de planejamento pode ser do tipo big-bucket, onde o período de tempo é grande o bastante para produzir vários itens, ou do tipo small-bucket, onde o período de tempo é tão pequeno, que somente um item pode vir a ser produzido. Também para o horizonte de planejamento, 26 um outro dado importante é a certeza ou não da data de entrega de um produto. Quando esta data não é certa, tem-se um horizonte rolante (rolling horizon). 2.2.6 - Número de produtos Uma linha de produção pode ser caracterizada como de produção de um único produto (single-item) ou de vários produtos (multi-item). A possibilidade de produção de vários produtos aumenta em muito a complexidade do problema, dada a possibilidade de variação dos tempos de produção, setups etc. 2.2.7 - Restrição por capacidade Um recurso necessário à produção pode ter uma capacidade limitada. Esse limite de capacidade aumenta em muito a complexidade do problema. Na literatura um recurso sem limite de capacidade é conhecido como não-capacitado (uncapacited) e um recurso com limite de capacidade é conhecido como capacitado (capacitated). O limite de capacidade pode ser o tempo limite de produção, uma restrição de mercado, o espaço de armazenagem, o tempo disponível de uma máquina, etc. 2.2.8 - Deterioração de um produto O tempo em que um produto pode ser mantido nos estoques é outro fator que deve ser levado em consideração no planejamento da produção. Alguns produtos têm validade de uso, ou alguma particularidade que pode vir a afetar sua qualidade final (ferrugem, deformação etc.). Este problema é pouco estudado pela literatura em geral e torna o problema bastante complexo. 2.2.9 - Demanda A demanda de um produto é uma importante entrada de dados para a solução de um problema de sequenciamento de produção (e de dimensionamento de lotes). 27 Atualmente, processos como o JIT (Just In Time), o JIS (Just In Sequence) e a venda sob uma modalidade em que o próprio cliente monta seu produto, fazem com que a demanda sofra alterações abruptas e tanto a sequência de produção quanto as quantidades a serem produzidas podem ser alteradas. Quando uma demanda não se altera com o passar do tempo é denominada estática; a demanda é dinâmica se esta é alterada o tempo todo. Se o valor da demanda é conhecido antecipadamente esta é denominada determinística; se a demanda é baseada em cálculos estatísticos ela é dita probabilística. Um produto pode depender de outro para sua produção e, neste caso, este produto é chamado de demanda dependente. Se um produto não depende de nenhum outro para sua produção, sua demanda é independente. 2.2.10 - Falta de estoque A falta ou não de estoque pode ser uma estratégia dentro do negócio. Na literatura a falta de estoques (shortage) é encontrada em vários casos, pois aceita-se a entrega futura ou pode-se perder a venda. O atraso de produção (backlogging) combinado com a perda de venda é possível conforme Wee (1999) apud Karimi et al. (2003). Problemas com falta de estoques são mais difíceis de resolver. 2.3 - Problemas de dimensionamento de lotes O planejamento de produção envolve o dimensionamento de lotes de peças a ser produzido. Para este problema, as principais variáveis são: horizonte de produção (que pode ser finito ou infinito) e a demanda de peças a produzir. Em Campbel (1992), os processos de sequenciamento e dimensionamento de lotes são considerados como níveis de decisão distintos devido às suas características tão diferentes. Além disso, o sequenciamento e dimensionamento de lotes são considerados dois dos mais importantes processos dentro da cadeia de suprimentos. 28 O dimensionamento de lotes, conforme Araújo e Arenales (2000), consiste em planejar a quantidade de itens a serem produzidos em várias ou em uma única máquina ao longo de um tempo finito, de modo a atender a uma certa demanda, sujeito a restrições de limitação de capacidade, tendo como objetivo a minimização do custo de produção ou a maximização da quantidade produzida. Conforme Feng e Cheng (1998), com o aumento da complexidade das técnicas de produção industrial, o dimensionamento de lotes de produção torna-se cada vez mais difícil. Para estes autores, os seguintes fatores são importantes: Disponibilidade limitada de recursos; A existência de vários produtos usando o mesmo recurso; Demanda variável período a período no horizonte de planejamento; Tempos de preparação; Custos de preparação. 2.4 - Estudos sobre dimensionamento de lote e sequenciamento O dimensionamento de lotes pode ser dividido em mono-estágio ou multi- estágio (ARAÚJO e ARENALES, 2000). Mono-estágio é a designação dada quando um item não depende da produção ou processamento de nenhum outro anterior a ele para começar sua produção. Multi-estágio ocorre quando um item depende da produção de outro para sua fabricação. Estudos sobre dimensionamento de lotes são antigos. Keachie e Fontana (1966) descrevem a importância de analisar o dimensionamento de lotes. Wortham e Mayyasi (1972) destacam o modelo de horizonte finito, falta de estoques (shortage) e ordens não atendidas (backorder). Segundo Meyer e Fleischmann (1997), um modelo realista de dimensionamento de lote deve ter capacidade de produção finita, vários produtos usando essa capacidade 29 e uma situação de planejamento dinâmica, que parte do estoque existente em um intervalo de tempo finito com demanda flutuante. Araújo e Arenales (2000), baseado em um modelo de Trigueiro et al. (1989), considerou o problema de dimensionamento de lotes mono-estágio com itens, restrição de capacidade, custos de produção, preparação e estoque. Para este modelo foi incluído o tempo de preparação para considerar o consumo dos recursos. Buschkühl e Tempelmeir (2008), desenvolveu para uma indústria de plásticos fornecedora da indústria automobilística, um modelo envolvendo preparação e dimensionamento proporcional de lote (PLSP – Proportional Lot Sizing and Scheduling Problem), proposto por Haase (1994). Em Sicilia et al. (2008), há uma consideração sobre um limite para o nível de estoques, que foca o problema através do dimensionamento dinâmico de lote. Neste modelo a demanda é conhecida e a falta de estoques não é permitida. A programação de produção deve designar qual tarefa deve ser executada em qual máquina (designação de tarefas) e quando cada uma das tarefas deve ser executada (scheduling). A variedade de ambientes existentes faz com que este assunto seja amplamente discutido. A quantidade de trabalhos a respeito é muito grande. As principais medidas de desempenho usadas nos problemas de programação da produção de acordo com (ARENALES et al, 2007) e (BARROS e MOCELIN, 2004) são as seguintes: Makespan – É o instante de término de todas as tarefas a serem processadas. Ele mede a eficiência operacional, informando o tempo necessário para se executar um conjunto de tarefas; Tempo total de fluxo - É a soma dos instantes de término de processamento das tarefas, que mede o estoque em processamento. 30 Atraso máximo – É a medida de atendimento ao cliente, que consiste na diferença entre o momento em que a tarefa é terminada e aquele em que ela supostamente seria concluída no prazo. Atraso total - Soma dos atrasos; está relacionada com uma data de entrega. Lateness – É a diferença entre o momento que uma tarefa deveria ter sido concluída e o momento em que ela foi concluída com atraso. Em Behnamian et al. (2009), é desenvolvido um algoritmo heurístico para um problema de setup dependente da sequência tendo como objetivo a minimização do makespan. Este algoritmo faz uso das meta-heurísticas ACO (Ant Colony Optimization), VNS (Variable Neighborhood Search) e SA (Simulated Annealing). Chen e Chen (2009), desenvolveram um algoritmo para máquinas paralelas não relacionadas e com setup dependente da sequência, visando minimizar o número de trabalhos atrasados. Neste algoritmo foram usadas as heurísticas de busca local de descida e busca tabu. Tahar et al. (2006), discutem uma solução para um problema de sequenciamento de um conjunto de jobs independentes com setup dependente da sequência de produção, objetivando minimizar o makespan. A característica mais interessante desse processo é a possibilidade de haver split de lotes, isto é, um lote pode ser dividido em tempos e máquinas diferentes. Como exemplo prático desse problema é apontado uma confecção, onde um lote de roupas pode começar a ser produzido em uma máquina e, se necessário, sua produção pode ser interrompida e recomeçar posteriormente. 2.5 - Problemas de sequenciamento de lotes Problemas com setup dependente da sequência e máquinas paralelas são analisados a seguir. 31 Omar et al. (2007), realizaram um estudo baseado em uma linha de produção de uma indústria química. O processo químico se caracteriza pela grande quantidade de setups dependentes da sequência, pois a contaminação entre produtos dividindo as mesmas máquinas é um fator crítico. O processo caracteriza-se por ter setup dependente da sequência, em lotes. Ainda neste trabalho foram construídos modelos tanto para atender à uma máquina simples quanto a máquinas paralelas. Abaixo segue o exemplo da formulação para máquinas paralelas. Parâmetros: m = número de famílias; r = número de linhas de produção; n = total número de jobs; fj = família do job j, j = 1, 2, ..., m; dj = data de entrega do job j; pjl = tempo de processamento do job j na linha l; ej = penalidade por adiantar a produção; tj = penalidade por atrasar a produção; sjk = tempo de setup da família j para a família do job k. G jk = sjk se fj fk 0 se fj = fk M = Número positivo muito grande. Variáveis de decisão: Ej = Atraso para o job j Tj = Adiantamento para o job j Cj = Tempo total da job j 32 jl = jk = 1 se o job j é o primeiro a ser processado na linha l 0 senão 1 se o job k é o próximo na sequência após o job j 0 senão jl = Variável contínua, restrita ao intervalo [0,1], denota que o job j foi sequenciado na linha l mas não na primeira posição. Formulação: Min n (e j E j j 1 t jT j ) 2.1 Sujeito a: r 2.2 ( jl l 1 jl ) 1 j 1,2,..., n jl n jl kl 1 jk j 1,2,..., n; k 1,2,..., n; l 1,2..., r 2.3 2.4 jl 1 j 1 r n l 1,2,..., r 2.5 jl l 1 n kj 1 k 1 j 1,2,..., n 2.6 jk 1 k 1 r j 1,2,..., n 2.7 Ck C j G jk r pkl kl M jk M l 1 j 1,2,..., n; k 1,2,..., n 2.8 C j p jl jl jl l 1 C j E j T j d j j 1,2,..., n j 1,2,..., n 2.9 33 d j jk dk jk C j , E j ,T 0 j 1,2,..., n j 1,2,..., n 2.10 2.11 A equação 2.1 determina o objetivo da formulação: minimizar a soma ponderada de atrasos e adiantamentos. Para isso, o número de atrasos e adiantamentos é multiplicado por uma penalização. A equação 2.2 assegura que um job deve ser atribuído a somente uma linha de produção de cada vez. A equação 2.3 assegura que um job e seu sucessor devem seguir na mesma linha. A equação 2.4 afirma que cada job, se for o primeiro a ser processado, só pode ser processado em uma linha de produção. A equação 2.5 garante que um job ou é o primeiro a ser processado ou sucede outro job na sequência de processamento. A equação 2.6 garante que um job sempre deve ser sucedido por outro, a menos que seja o último da sequência. A equação 2.7 garante que o instante de inicio de processamento de um job não pode ser menor que o instante de término de seu predecessor direto na sequência de processamento. A equação 2.8 garante que o tempo necessário para realizar um job deve ser maior ou igual que seu tempo de processamento. A equação 2.9 mede o grau de atraso ou antecipação de um job, ou seja, garante que o tempo total de uma tarefa somado aos atrasos e subtraído do que foi adiantado deve ser igual a data de entrega da tarefa. Na equação 2.10 certifica-se que a data de entrega de um job deve ser igual ou anterior à data de entrega de seu sucessor direto. A equação 2.11 garante a não negatividade das variáveis. Este modelo está preparado para controlar a data de entrega, não de uma maneira rígida, como um objetivo, mas como uma restrição, o que diminui a complexidade do modelo. A penalidade de atrasos e adiantamentos obriga o atendimento mais rígido a uma data. Outro modelo que contém importantes elementos para uma solução do problema de sequenciamento é o de Gupta e Magnusson (2005). Este modelo se caracteriza por ter sido feito para um ambiente de máquina simples e com tempo de setup dependente da sequência. O problema para o qual o modelo foi desenvolvido é conhecido na literatura como dimensionamento de lote capacitado e sequenciamento (CLSP – Capacitated Lot-sizing and Scheduling Problem). O modelo foi formulado 34 para um problema de uma indústria de abrasivos e o objetivo é determinar a sequência e tamanho do lote que minimize o custo de setup e os estoques. Uma característica desse tipo de produção é que dependendo do tipo de lixa (abrasivo) que se pretende produzir, é necessário um tipo de cola e um grão específico. Por isso, após a produção de um tipo de abrasivo, a limpeza de máquina é imprescindível para dar início à produção de outro tipo, devido à diferença no material necessário para a produção e aos resíduos restantes nas máquinas. Este tempo de preparação (limpeza) é muito grande e compromete a capacidade produtiva da empresa. O modelo criado é o seguinte: Parâmetros: P Número de períodos; o índice de períodos é t = {1, ..., P}; N Número de produtos; os índices de produtos são i,j = {1, ..., N}; Variáveis de decisão: Xit Quantidade de produto i no período t; Yit Variável binária associada a Xit; Yit = 1, se o produto i for produzido no período t; Caso contrário, Yit = 0; Tijt Variável binária; Tijt = 1, se houve mudança do produto i para o produto j no período t; Caso contrário, Tijt = 0; Dit Demanda do produto i no período t; Iit Saldo do produto i em estoque no período t; hi Custo do estoque do produto i; Cij Custo do setup do produto i para o produto j; Assume-se que Cij <= Cjk + Ckj para todos i, j e k; Para impedir subturnos considera-se Cii = ; sij Tempo de setup do produto i para o produto j; it Variável binária; it = 1, se o produto i for produzido no início do período t; Caso contrário, it = 0; it Variável binária; it = 1, se o produto i for produzido no final do período t; Caso contrário, it = 0; it Variável binária; it = 1 se a máquina está preparada (setup) para o produto i ao final do período t; Caso contrário, it = 0; 35 it Variável contínua entre 0 e 1; it > 0 se o produto i for produzido no período t; Caso contrário, it = 0; it Variável contínua; it = 0 se exatamente um produto i é produzido no período t; Caso contrário, it > 0. Modelo: P N N P N 2.12 Min CijTijt t 1 i 1 j 1 hi Iit t 1 i 1 Sujeito a: Iit 1 X it Iit Dit 2.13 X it N Yit 0 N N 2.14 2.15 X it i 1 Yit t N Tijt sij 1 i 1 j 1 t i, t 2.16 2.17 Yit i 1 1 N ( N 1) t t 2.18 t t it it it 1 i 1 N it 1 i 1 Yit Yit t .T t i, t i, t 2.19 2.20 2.21 it it 2 N t i, t 2.22 2.23 it 1 i 1 N t T 2.24 Tijt Yit j 1 N it i, t 2.25 Tijt Yit j 1 it i, t Tijt it 1 jt t 1 i j, t 2.26 36 T jit it jt 1 1 i j, t 2.27 Tijt it jt 1 i j, t 2.28 0 t 1 t 2.29 X it , Iit , t 0 i, t 2.30 T jit ,Yit , it , it , it {0,1} i, j, t 2.31 Características da formulação (2.12 – 2.31): O setup é preservado durante os possíveis períodos vazios; As restrições 2.13, 2.14 e 2.15 são típicas de controle de estoque; Devido às suas características, para considerar um setup seguido de produção que pode agrupar vários períodos, fez-se necessário o uso de variáveis de controle, como , e ; Restrições 2.16 a 2.23 controlam quando um setup ocorre, o início da produção de um produto e seu fim. Essas informações são necessárias porque precisa-se garantir que o setup ocorra antes do início de cada produção; As restrições 2.24 e 2.25 são sempre aplicadas quando mais do que um produto é produzido em um período simples. Eles forçam que pelo menos um Tijt seja igual a 1 para cada produto i, exceto quando este produto é o primeiro ou o último na sequência; Restrições 2.26 a 2.28 obrigam a existência de um setup sempre que houver mudança na produção de uma peça para outra; Restrições 2.29 a 2.31 determinam o escopo das variáveis (não negatividade); Este modelo mostrou-se eficiente para encontrar a solução de pequenos exemplares do problema, mas é impraticável para resolver problemas práticos de grandes dimensões. 37 Outro trabalho que merece destaque é o de Meyr (2002), que também associa o sequenciamento de produção e dimensionamento de lotes de vários produtos em máquinas paralelas não uniformes, com setup dependente da sequência. O objetivo nesse trabalho foi a minimização do setup e o estoque em mãos. A solução foi obtida pelo uso de duas heurísticas simultâneas Threshold Accepting (TA) e a Simulated Annealing (SA). Lee e Pinedo (1997) desenvolveram um trabalho em um ambiente de máquinas paralelas com data de entrega, setup dependente da sequência. Seu objetivo era a minimização do makespan. Para este cenário foi usada uma heurística de três fases, sendo a primeira, como um pré-processamento, estimando o makespan baseado na data de entrega; a segunda fase busca gerar uma sequência de entrega e na terceira fase é aplicada a metaheurística Simulated Annealing. 38 3. MODELOS MATEMÁTICOS PROPOSTOS 3.1 - Descrição do problema A fabricação de peças usando prensas de alta capacidade tem uma série de peculiaridades que afetam diretamente o planejamento da sequência de produção. A variação da demanda por parte do cliente é constante e pode ser feita dentro de um período curto (dias ou horas), exigindo revisão rápida de toda a sequência de ordens de produção. O tempo de setup é um fator fundamental quando este tem componentes variáveis. No caso em estudo o tempo de setup é um dos fatores mais importantes. Atrasos na entrega de matéria prima é outro fator que exige atenção, pois o tempo necessário para compra é grande e o pedido deve ser colocado com 90 dias de antecedência junto ao fornecedor. Assim, qualquer mudança na data de entrega compromete o planejamento pré-estabelecido e outro plano de produção precisa ser elaborado. Considera-se, neste trabalho, que o tamanho do lote econômico está pré- determinado. Neste estudo não se está considerando problemas de estocagem ou suprimentos de matéria prima, pois estes processos são independentes. 3.2 O processo produtivo A empresa em estudo produz peças estampadas específicas para caminhões, camionetes, automóveis e tratores, atendendo aos clientes somente sob contrato. Seu produto não atende à venda direta ao consumidor final nem à empresas distribuidoras de peças. O processo de produção tem início após o fechamento de um contrato que normalmente significa fornecer peça para uma linha de produção enquanto o veículo for produzido. A quantidade de diferentes modelos de peças que essa empresa pode produzir é muito grande e a linha onde este estudo se realiza, chamada internamente de prensaria pesada, é onde prensas grandes fazem a conformação das peças a partir de chapas de aço. Prensas desse tipo precisam de um dispositivo acoplado que confere a elas capacidade de dar à chapa formato, corte e furação necessário. Este dispositivo é conhecido como ferramental e sua montagem na prensa necessita de muito tempo e 39 extrema precisão. O setup de máquina aqui considerado começa no momento que esse ferramental é colocado na prensa até seu teste, quando uma peça é feita e medida com calibres específicos para verificar se atende ao desenho. O ferramental é dividido em estampo inferior, estampo superior e blocos. Um ferramental pode servir para a produção de mais do que um tipo de peça, pois, com algumas modificações na sua montagem, agregando peças ou tirando punções, pode servir para produzir um modelo diferente de peça. Este tipo de operação é bastante comum porque de um ano para o outro um modelo de caminhão pode sofrer alterações que, por menores que sejam, podem significar a alteração de uma furação, dimensão etc. Outro fator que faz com que haja alteração em uma peça é uma mudança na estrutura global do veículo para atender a alguma funcionalidade particular, como aumento da capacidade do tanque de combustível, aumento do comprimento da carroceria etc. Devido ao alto custo para confecção de um ferramental, ele é único, impedindo assim que duas prensas utilizem o mesmo ferramental ao mesmo tempo. 3.3 – A Gestão da produção na empresa em estudo Na empresa em estudo o processo de gestão da produção ocorre da seguinte maneira: as peças estampadas são produzidas com base em um cronograma de entrega de peças fornecido pelo cliente. Esta solicitação chega através de transmissão eletrônica de dados (EDI – Eletronic Data Interchange) sendo que uma programação para o curto prazo, de uma semana a vinte dias, dá subsídios para a programação da produção. A programação de peças para um longo prazo também chega via EDI. O ERP (Enterprise Resource Planning) da empresa executa as rotinas de programação de compra e emissão de ordens de produção através de rotinas do MRP (Material Requirement Planning). As ordens de produção criadas são agrupadas de acordo com o lote econômico de produção. Todo este cálculo feito pelo MRP não leva em consideração a capacidade de produção das máquinas disponíveis. 40 Os dados recebidos via EDI alimentam a carteira de pedidos da empresa. Outra base de dados, denominada previsão de produção é alimentada pela área comercial com base nas tendências de mercado. A intersecção dos dados dessas duas informações vai fornecer o Plano Mestre de Produção. As rotinas do MRP irão se basear nestes dados como demanda de produção. As rotinas do MRP precisam ainda da lista de materiais e saldo dos estoques para criar as ordens de produção necessárias e as ordens de compra de matéria prima necessária. O fluxo da gestão de produção pode ser visto na Figura 2. Figura 2 – Gestão da produção da empresa em estudo Com base no cronograma de entrega de peças de curto prazo fornecido pelo cliente, os planejadores elaboram o plano de produção para uma semana. Para isso, fazem uso de planilhas eletrônicas, ou seja, não fazem uso de nenhuma ferramenta de Programação Matemática. Este plano é passado para o setor de ferramentaria, que por sua vez prepara os ferramentais na ordem em que devem ser usados. O plano é também passado para o setor de fornecimento de matéria prima, que deve preparar a 41 chapa de aço para a produção. Esta preparação consiste no corte da chapa em um formato adequado para a produção, conhecido por blank. Em alguns casos, esse processo de corte da chapa no tamanho desejado é realizado por terceiros, pois a compra de aço é feita em forma de bobinas e para o desbobinamento dessa peça é necessário o uso de maquinário adequado. A vivência nesse ambiente de produção tem mostrado que a ocorrência de reprogramações nos clientes é um fator constante. Uma das causas disto é o uso de conceitos como o JIS e o JIT, que levam as montadoras a ter um estoque enxuto e suscetível a uma série de imprevistos. Isto exige dos fornecedores agilidade em atender às alterações na demanda. Com isso, todo o processo de planejamento precisa ser revisto rapidamente. A planta dessa linha de produção consiste de três prensas de alta capacidade de 3000 a 5200 toneladas. Uma relação de 2118 tipos diferentes de peças é possível ser produzida e 75 ferramentais são usados para a fabricação destas peças. O ferramental tem por característica servir, com algumas modificações, para produzir várias peças, conforme dito anteriormente, criando assim uma forte restrição na programação da produção, pois quando um ferramental estiver em uso para produção de uma peça, outras peças que utilizam o mesmo ferramental não poderão ser produzidas. A quantidade de modelos de peças produzidas por semana pode chegar a 150, sendo a produção unitária semanal de cerca de 3500 peças. O tempo de setup é muito longo, tornando-se um fator crítico na programação da produção. Além disso, a sequência do setup pode alterar seu tempo, pois, algumas partes de um ferramental podem ser compartilhadas para a produção de outras peças. Assim, a partir da produção de uma peça, pode-se agilizar a preparação para a produção da próxima peça. Portanto, neste estudo, o setup tem tempo variável, dependente da sequência de produção. 42 O planejamento feito com base em planilhas não garante que o caminho escolhido para produção das peças é o melhor. As variações acarretam grandes transtornos, uma vez que esta planilha é de difícil manutenção. 3.4 - Os modelos matemáticos O estudo do ambiente do problema mostra duas possíveis soluções para a programação da produção. A primeira delas tem como objetivo a redução do custo total de produção dentro de um período, levando-se em consideração principalmente o tempo de setup. A ideia é que, com o período total estabelecido, a redução de tempo gasto com o setup se converta em redução de custo para a empresa. A segunda alternativa para a programação da produção tem como objetivo minimizar o makespan. Para a minimização do tempo de setup são apresentados dois modelos. O Modelo I, criado especificamente para este trabalho, baseia-se no DLSP (Discrete Lotsizing Scheduling Problem). O Modelo II baseia-se no trabalho de Gupta e Magnusson (2005) para o CLSP (Capacitaded Lotsizing Scheduling Problem). Para a minimização do makespan criou-se o Modelo III, também estabelecido especificamente para este trabalho. Os resultados obtidos a partir deste modelo serão comparados com os resultados obtidos por um método heurístico híbrido, também desenvolvido para o mesmo objetivo e descrito no Capítulo 4. Os modelos propostos objetivam atender a um cenário de máquinas paralelas com tempo de setup dependente da sequência de produção em que estoques devem ser evitados, mas são aceitáveis tendo em vista a prática de lotes mínimos de produção. Atrasos devem ser evitados e a demanda deve ser atendida plenamente. O custo de produção não varia de acordo com a prensa e neste trabalho não é necessário controlar o dimensionamento de lotes pois este é feito através das políticas implementadas nas rotinas do MRP. Considera-se também que o tamanho do lote não altera o tempo de setup. 43 3.5 - Modelo I: minimização do tempo total de setup O Modelo I prevê a produção de um item por unidade de tempo (small bucket). Este tipo de modelo permite um maior controle sobre a produção das peças, pois sabe- se em que período cada peça será produzida. Este detalhe é de alta importância nesse modelo, devido à uma forte restrição que impede que algumas peças sejam produzidas em duas prensas ao mesmo tempo. Como explicado anteriormente, esta restrição ocorre porque um ferramental não pode ser usado ao mesmo tempo em duas prensas diferentes. Outras restrições consideradas no modelo são: o tempo máximo de produção é fixo, ou seja, a produção não pode exceder a este tempo máximo pré- estabelecido (programação finita). O modelo proposto nesta seção tem por objetivo resolver o problema descrito anteriormente de sequenciar as peças na linha de produção de modo a se obter uma otimização do tempo de produção a partir da redução dos tempos de setup das máquinas. Conforme comentado anteriormente, este tempo é muito alto devido à complexidade do ferramental necessário. Para validar o modelo desenvolvido foram conduzidos alguns testes computacionais. Apesar de ser baseado em um problema real, os valores dos parâmetros e os dados usados nestes testes foram gerados aleatoriamente, pois os dados da empresa referem-se a grandes quantidades, o que dificulta um teste preliminar. Os testes foram executados em um microcomputador com processador Pentium Dual Core, com 3 Gigabytes de memória, 120 Gigabytes de disco, sob o sistema operacional Windows Vista. Para a solução do modelo foram utilizados os solvers Xpress (versão 1.22.04) e CPLEX (versão 12). Como será apresentado a seguir, o desenvolvimento do Modelo I foi realizado paulatinamente. Alguns fatores que não foram considerados inicialmente, foram sendo incorporados ao modelo de modo a torná-lo cada vez mais realista com o problema encontrado na prática. Essa metodologia utilizada no desenvolvimento deste modelo 44 visa enriquecer a pesquisa e mostrar como novos estudos podem vir a ser feitos, uma vez que qualquer mudança na política de produção ou em algum fator como matéria prima, disponibilidade de máquina, ferramental etc., terá que ser incorporada ao modelo como se fez, neste caso, com a metodologia adotada. Os elementos que compõem o Modelo I são apresentados a seguir. Parâmetros: I Número de produtos; os índices i e j são usados para representar uma peça em produção ou uma peça predecessora; K Número de prensas; o índice k {1, .., K} é usado para representar uma prensa; O número de prensas pode variar, caso algum centro de trabalho seja dedicado a esta linha, ou alguma prensa ser paralisada para manutenção. P Número de períodos; o índice p {1, ..., P} é usado para representar um período. Dados: Di Demanda da peça i; Conforme descrição anterior deve ser atendida em sua totalidade. Pti O tempo de processamento da peça i; Sij Tempo de setup da peça i após a produção da peça j. Variáveis de decisão: tkp Tempo de início da produção de uma peça no período p na prensa k; zikp Variável binária tal que zikp = 1 se a peça i foi alocada no período p da sequência de produção da prensa k; zikp = 0, caso contrário. wijkp Variável binária tal que wijkp = 1 se a peça i foi alocada no período p e a peça j foi alocada no período (p+1) da sequência de produção da prensa k. 45 Formulação: Min Pti zikp Sij wijkp 3.1 i I k K p P i , j I i j k K p P Sujeito a t k ( p 1) t kp Pti zikp Sij wijkp 0 p P 3.2 i I k K i , j I i j k K zikp 1 i I zikp Di k K p P p P, k K i I 3.3 3.4 wijkp zikp z jk ( p 1) 1 i, j I ; i j; k K ; p P 3.5 tkp 0 k K ; p P 3.6 wijkp {0,1} i, j I ; k K ; p P 3.7 zikp {0,1} i I ; k K ; p P 3.8 A função-objetivo 3.1 busca a minimização dos tempos de processamento e tempos de preparação das peças a serem produzidas. As restrições 3.2 indicam que o processamento no período (p+1) da sequência de produção da prensa k só pode ser iniciado depois que o processamento (incluindo preparação) no período anterior desta prensa tenha sido terminado. As restrições 3.3 indicam que em cada período p da sequência de produção da prensa k pode existir apenas uma peça. As restrições 3.4 indicam que a demanda de cada peça deve ser atendida plenamente. Estas restrições serão de igualdade, caso não se deseje estoque de peças produzidas. As restrições 3.5 indicam que peça i é alocada no período p e a peça j é alocada no período imediatamente seguinte (p+1) da sequência de produção da prensa k. As restrições 3.6, 3.7 e 3.8 determinam o domínio das variáveis. 46 3.5.1 - Testes computacionais com o Modelo I O Modelo I foi escrito na linguagem de modelagem Mosel (conforme Apêndice A) e submetido ao solver Xpress. O primeiro teste computacional (Teste 1) considerou 2 prensas e 3 peças. Os dados considerados no Teste 1 são mostrados na Tabela 1 (demanda, custo de produção e tempo de produção) e na Tabela 2 (tempos de setup entre peças). Tabela 1 – Base de dados para o Teste 1 Peça 1 2 3 Demanda 4 5 3 Custo 2 3 4 Tempo de produção 3 3 3 Tabela 2 – Tempos de setup de uma peça para outra para o Teste 1 Peça 1 2 3 Pe ça 1 0 3 1 2 3 0 2 3 1 2 0 A Tabela 3 mostra o gráfico de Gantt correspondente à sequência de produção em cada uma das prensas, correspondente à solução ótima obtida. A Tabela 4 mostra os valores obtidos para os tempos de produção e de preparação relativos à solução ótima do problema. Tabela 3 – Sequenciamento obtido no Teste 1 Período 1 2 3 4 5 6 7 8 9 10 11 12 Prensa 1 3 3 3 3 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2 2 47 Neste ponto é interessante destacar a variável P, conforme descrito anteriormente, que representa a quantidade de períodos. Por isso ela deve ter um valor grande o bastante para conter toda a produção. Esta variável pode aumentar o processamento consideravelmente uma vez que ela é uma das dimensões das variáveis z e w. Tabela 4 – Resultados obtidos no Teste 1 Tempo total de produção 72 Tempo total de preparação 1 Como pode ser observado, a solução obtida considera uma distribuição de peças por todos os períodos. Entretanto, alguns problemas foram identificados neste modelo, os quais são comentados a seguir. Problema 1: Preparação inicial O modelo não considera o tempo de setup para a preparação inicial, ou seja, para a produção da primeira peça da sequência para cada prensa. O setup inicial deve existir, pois a preparação consiste em colocar um ferramental na máquina, específico para uma peça, por isso a prensa nunca fica previamente montada. Para resolver este problema, verificou-se que as restrições (3.5) não atenderam à necessidade de existir um setup para cada inicio de produção. A alternativa para isso foi a imposição de que se há produção no primeiro período o setup deve existir. Para isso foram criadas as restrições (3.9): prep _ ini Stii i N k K * zik1 3.9 em que Stii corresponde ao tempo de setup inicial da peça i, que será considerado sempre que esta peça for produzida no período 1. A implementação na linguagem Mosel de todos os modelos pode ser vista no Apêndice B. 48 Problema 2: Atendimento da demanda O Modelo I também não considera um tratamento adequado para a demanda. Uma quantidade muito maior que o previsto foi programado. A produção excede à necessidade porque a restrição 3.4 impõe um limite mínimo e nenhuma outra restrição limita a produção. Além disso, a solução adotada inicialmente foi a inclusão do custo de produção na função objetivo. Deve-se observar que, neste trabalho, o custo de preparação (cp) de uma peça não está relacionado com a máquina onde esta peça será produzida. A função objetivo acrescida do custo de produção para resolver esse problema fica da seguinte maneira: Min Pti zikp Sij wijkp cpi zikp 3.10 i I k K p P i , j I i j k K p P i I k K p P Conforme comentado anteriormente, a demanda deve ser atendida plenamente e a produção em excesso deve ser evitada, pois os produtos aqui abordados são específicos para alguns veículos e, caso a fabricação deste veículo seja descontinuada, qualquer estoque vai significar perda de produção e material. A restrição usada primeiramente como uma desigualdade do tipo "maior ou igual", condicionada pela minimização dos custos deveria bastar. Entretanto, ao incluir esta restrição no modelo o problema tornou-se inviável. Verificou-se então que as restrições 3.3 obrigam a existência de produção em todos os períodos. Para resolver este conflito optou-se pela eliminação das restrições 3.3 e a troca das restrições 3.4 pela 3.11 conforme abaixo: zikp k K p P Di i I 3.11 49 Problema 3: Produção simultânea de peças O modelo, da forma como se encontra, apresenta uma falha no tratamento de uma restrição muito forte do problema: uma peça não pode ser produzida em duas prensas ao mesmo tempo. Isso não é possível, pois o ferramental associado a uma peça é único, como já explicado anteriormente. Portanto quando uma peça está sendo produzida em uma prensa, ela não pode ser produzida em outra prensa no mesmo período. Para assegurar essa restrição foram incluídas as restrições 3.12 e 3.13: zikp 1 i I zikp 1 k K p P, k K p P, i I 3.12 3.13 Este novo modelo, com o acréscimo das restrições 3.9, 3.10, 3.11, 3.12 e 3.13, menos as restrições 3.3 e 3.4 foi executado para os mesmos dados e os resultados obtidos estão mostrados nas Tabelas 5 e 6. Tabela 5 – Sequenciamento obtido no Teste 2 Período 1 2 3 4 5 6 7 8 9 10 11 12 Prensa 1 3 1 1 3 1 2 2 2 2 2 2 1 3 Tabela 6 – Resultados obtidos no Teste 2 Tempo total de produção 12 Tempo total de preparação 0 Tempo de setup inicial 0 Custo de produção das peças 35 Embora o modelo modificado representa melhor a realidade da empresa, alguns outros problemas ainda foram identificados. 50 Problema 4: O setup é obrigatório O modelo atual não considera a obrigatoriedade dos setups. A análise da solução apresentada mostra que a falta de setup foi criada pelo programa como uma maneira de evitar a agregação de custo ao resultado final. Na prática, os espaços entre a produção de peças não existem, pois toda a produção é tratada de maneira ininterrupta. As paradas resumem-se a eventos programados como hora para o almoço, manutenção etc. Para resolver essa deficiência da formulação foram acrescentadas mais algumas restrições ao modelo. Um primeiro conjunto de restrições força a realização de setup sempre que houver a mudança na produção de uma peça para outra. Outras restrições forçam a existência de um setup apesar de haver intervalos entre as peças a serem produzidas. A obrigatoriedade de setup é identificada sempre que uma peça ocupa uma posição do período de produção e na posição seguinte tem-se uma outra peça diferente. Quando isso ocorre, necessariamente neste intervalo deve ocorrer um setup. Para isso, foram acrescentadas ao modelo as restrições 3.14 e 3.15. Estas restrições obrigam a variável w assumir o valor 1 (restrição 3.14) se houver produção de peças diferentes em posições consecutivas, ou a assumir o valor 0 (restrição 3.15) se não houver. Dessa maneira as restrições 3.5 e 3.6 podem ser eliminadas, pois sua função já foi atendida por estas duas novas restrições. zi ,k , p z j ,k , p 1 2 * wi , j ,k , p 0 zi ,k , p z j ,k , p 1 2 * wi , j ,k , p 1 i, j I , i i, j I , i j; k K , p P j; k K , p P 3.14 3.15 Com a inclusão das restrições 3.14 e 3.15 e a eliminação das restrições 3.5 e 3.6, obtém-se a solução mostrada nas Tabelas 7 e 8. Tabela 7 – Sequenciamento obtido no Teste 3 Período 1 2 3 4 5 6 7 8 9 10 11 12 Prensa 1 3 3 1 3 1 2 2 2 1 1 2 2 2 51 Tabela 8 – Resultados obtidos no Teste 3 Tempo total de produção 12 Tempo total de preparação 0 Tempo de setup inicial 0 Custo de produção das peças 35 Mesmo com essas novas restrições, observa-se que o modelo deixa espaços (posições vazias no período de produção) entre a produção de duas peças diferentes, como forma de evitar a inclusão de setup entre elas. Para impedir que isso ocorra, criou-se a variável kp para controlar o conteúdo de cada período p em cada prensa k. Se no período p, a prensa k produz alguma peça então kp = 1; senão kp = 0. Assim, foram acrescentadas as seguintes restrições: I kp zi ,k , p i k , p k , p 1 3.16 3.17 As restrições 3.16 garantem que o valor da variável será 1 sempre que houver produção de alguma peça. As restrições 3.17 fazem com que não seja possível a existência de espaços vazios entre a produção de duas peças diferentes. Com isso, tem- se uma nova formulação para o Modelo I. Para essa nova formulação, com a inclusão das restrições 3.16 e 3.17 o teste realizado obteve a solução mostrada nas Tabelas 9 e 10. Tabela 9 – Sequenciamento obtido no Teste 4 Período 1 2 3 4 5 6 7 8 9 10 11 12 Prensa 1 1 1 1 1 3 3 3 2 2 2 2 2 2 52 Tabela 10 – Resultados obtidos no Teste 4 Tempo total de produção 12 Tempo total de preparação 1 Tempo de setup inicial 2 Custo de produção das peças 35 Observa-se que, finalmente, a solução obtida atende aos requisitos impostos ao problema: as peças são produzidas continuamente, não havendo intervalos no período de produção; tem-se, obrigatoriamente, um setup inicial e um setup sempre que ocorre mudança de produção de peças. Deve-se observar que nesta formulação, o parâmetro P (número de períodos) assume um papel muito importante. Considerando a restrição de que uma peça não pode ocupar a mesma posição em duas prensas ao mesmo tempo, o valor de P pode ser estimado da seguinte forma: P não pode ser menor do que o tempo total necessário para fazer a peça que demora mais períodos e nem pode ser menor do que a soma de todos os períodos necessários para a produção de todas as peças. Novos testes computacionais foram realizados com esta formulação do Modelo I, utilizando o solver Xpress. A Tabela 11 mostra os resultados obtidos nestes novos testes computacionais. As legendas utilizadas nas colunas desta tabela são as seguintes: NM - Número de máquinas (prensas); NP - Número de peças; NL - Número de linhas (restrições) do modelo; NC - Número de colunas (variáveis) do modelo; CPU – Tempo necessário para resolver o modelo (em segundos). Produção - Tempo gasto para produzir o item; Custo - Custo resultante da produção das peças; Setup - Tempo de setup utilizado durante a produção; 53 Inicial - Tempo gasto com o setup no início da produção (momento 0); Tabela 11 – Resultados obtidos no Teste 5 NM NP NL NC CPU Produção Custo Setup Inicial 2 3 141 132 0,3 8,76 51 210 260 3 3 306 306 1,0 17,04 88 0 390 4 3 306 408 1,1 18,00 89 0 390 2 4 458 456 7,8 16,44 84 90 390 3 4 333 348 8,0 11,88 62 190 390 4 4 432 464 7,3 12,24 63 0 520 2 5 453 460 87,2 10,44 52 280 260 3 5 581 615 203,0 13,32 71 120 390 4 5 572 620 310,5 14,88 79 250 520 Os testes foram feitos com uma sequência de 3, 4, 5, 10, 15 e 20 peças. A partir de 10 peças, a execução do modelo torna-se demasiadamente lenta e após 1 hora de processamento o sistema encerrou a execução por falta de recurso (memória). Pelos resultados da Tabela 11, pode-se observar que o tempo de execução é alto, mesmo para um número pequeno de peças. Isto inviabiliza a utilização desta formulação para exemplares do problemas mais próximos do real, com 3 prensas e 180 peças. Esta formulação, no entanto, ainda não inclui uma restrição importante do problema real: duas ou mais peças que dividem o mesmo ferramental, ou parte dele, não podem ocupar a mesma posição no período de produção, em prensas diferentes. Tais peças são denominadas, neste trabalho, como peças incompatíveis e uma nova variável Rij foi criada para indicar se as peças i e j são incomparáveis (Rij = 1) ou não (Rij = 0). Para isso, a seguinte restrição foi inserida no Modelo I: zikp z jmp Ri , j 2 i, j I ; i j; k , m K ; k m; p P 3.18 Com isso, as restrições 3.2 podem ser retiradas deste modelo porque ele está ocupando todas as posições na linha do tempo e caracterizando esta posição de maneira que a variável t não precisa mais ser controlada. Além disso, a função de custo se mostrou ineficiente na função-objetivo, além de comprometer seu resultado, 54 uma vez que este custo não está relacionado com o tempo como as duas outras parcelas. Para isso introduz-se a função objetivo 3.19 no lugar da 3.1. 3.19 Para esta nova formulação, acrescentando à anterior as restrições 3.18 e 3.19, e retirando as restrições 3.1 e a 3.2, foram realizados testes computacionais considerando os dados mostrados nas Tabelas 12, 13 e 14. Os resultados obtidos são mostrados nas Tabelas 15 e 16. Tabela 12 – Parâmetros das peças Peça 1 2 3 Demanda 4 5 3 Custo 2 3 4 Tempo de produção 3 3 3 Tabela 13 – Tempo de setup Peça 1 2 3 Pe ça 1 0 3 1 2 3 0 2 3 1 2 0 Tabela 14 – Incompatibilidade entre peças Peça 1 2 3 Pe ça 1 1 1 0 2 1 1 0 3 0 0 1 55 Tabela 15 – Sequenciamento obtido no Teste 5 Período 1 2 3 4 5 6 7 8 9 10 11 12 Prensa 1 2 2 2 2 2 2 3 3 3 1 1 1 1 Tabela 16 – Resultados obtidos no Teste 5 Tempo total de produção 12 Tempo total de preparação 3 Tempo de setup inicial 1 Custo de produção das peças 35 O modelo obtido final fica da seguinte maneira: (3.19) Sujeito a wijkp {0,1} i, j I ; k K ; p P (3.7) zikp {0,1} i I ; k K ; p P (3.8) (3.9) zikp k K p P Di i I (3.11) zikp 1 i I zikp 1 k K p P, k K p P, i I (3.12) (3.13) zi ,k , p z j ,k , p 1 2 * wi , j ,k , p 0 zi ,k , p z j ,k , p 1 2 * wi , j ,k , p 1 I z i, j I , i i, j I , i j; k K , p P j; k K , p P (3.14) (3.15) (3.16) kp i ,k , p i 56 k , p k , p 1 zikp z jmp Ri , j 2 i, j I ; i j; k , m K ; k m; p P (3.17) (3.18) O tempo excessivo gasto pelo solver Xpress versão 1.22.04 motivou a utilização do solver CPLEX versão 12. A Tabela 17 compara os resultados obtidos pelos dois solvers para alguns exemplares do problema. Nesta tabela as legendas das colunas são as seguintes: NM - Número de máquinas (prensas); NP - Número de peças; FO - Valor da função-objetivo; NL - Número de linhas (restrições) do modelo; NC - Número de colunas (variáveis) do modelo; CPU - Tempo de execução (em segundos); XP – Solver Xpress; CP – Solver CPLEX. Tabela 17 – Comparativo Xpress versus CPLEX FO NL NC CPU NM NP XP CP XP CP XP CP XP CP 3 3 18 18 844 867 526 531 2,1 0,34 3 4 26 26 1549 1572 930 935 7,9 49,4 3 5 32 32 2582 2625 1449 1454 1670 440,6 3 6 49 41 3744 3786 2582 2086 7200 7200 3 7 ** 54 5133 5175 2827 2833 7200 7200 O tempo máximo de execução foi estabelecido em 7200 segundos. A partir desse limite os resultados não são ótimos. O modelo submetido ao CPLEX foi obtido a partir do modelo submetido ao Xpress. O Xpress faz, por padrão, uma otimização dos dados de entrada, eliminando equações que não terão função na execução do modelo. Esta otimização é conhecida por presolve e tem influência direta nos dados gerados para o CPLEX. Os resultados mostraram que o CPLEX é mais rápido para a maioria 57 dos exemplares; a exceção ocorreu para o exemplar com NP = 4 . Para 7 peças o Xpress não obteve sequer uma solução viável no limite de tempo estabelecido. 3.6 - Modelo II: minimização do tempo total de setup O alto tempo de execução do Modelo I, tanto pelo Xpress como pelo CPLEX, motivou a busca por outros modelos para a solução do problema. O modelo desenvolvido por Gupta e Magnussom (2005), detalhado na seção 2.5, para controle de máquinas paralelas com tempos de setup dependentes da sequência de produção, foi adaptado para o problema em estudo. Isto foi possível devido ao fato do modelo de Gupta e Magnussom controlar os momentos inicial e final de cada lote produzido, o que permite controlar, a cada instante, qual produto está sendo produzido, permitindo, portanto, implementar a restrição que impede que duas peças que utilizem o mesmo ferramental sejam produzidas no mesmo momento em prensas diferentes. A Tabela 18 compara as características do modelo original de Gupta e Magnusson (Modelo GM) em relação ao Modelo II proposto nesta seção. A Tabela 19 mostra as conversões realizadas nas variáveis e parâmetros do modelo de Gupta e Magnusson para atender ao problema em estudo. Tabela 18 – Comparação das características dos modelos Modelo GM Modelo II Quantidade de estágios Estágio simples Estágio simples Ambiente de máquinas Paralelas / idênticas Simples Setup Dependente da sequência Dependente da sequência Parâmetros de setup Somente tempos Tempos e custos Preserva setup por períodos Não Sim Restrição de capacidade Capacitado Capacitado Considera os estoques Não Sim Período de produção Small bucket: um item é Big bucket: vários itens são 58 produzido por período produzidos em um período Número de produtos Vários itens Vários itens Deterioração de produto Não considera Não considera Demanda Estática Estática Falta de estoque Não permitida Não permitida Dimensionamento de lote Não Sim Divisão de lote Não é permitido Permitido Tabela 19 – Conversão de variáveis Variável Modelo GM Variável Modelo II Número de períodos, tendo como índice t = {1,..., T} P Número de períodos, tendo como índice t = {1,..., P} N Quantidade de produtos N Sem mudança xit Quantidade de produção do produto i no período t xikt Quantidade de produção do produto i na máquina k no período t Yit Igual a 1, se o produto i for produzido no período t; igual a 0, caso contrário Yikt Igual a 1, se o produto i for produzido na máquina k no período t; igual a 0, caso contrário Tijt Igual a 1, se o setup ocorreu da peça i para j no período t; igual a 0, caso contrário Tijkt Igual a 1, se o setup ocorreu da peça i para j na máquina k no período t; igual a 0, caso contrário Dit Demanda do produto i ao final do período t Dit Sem mudança Iit Estoque do produto i ao final do período t Não utilizada Hi Custo do estoque do produto i Não utilizada Cij Custo do setup do produto i para o produto j Cij Sem mudança Sij Tempo de setup do produto i para o produto j Sij Sem mudança it Igual a 1, se o produto i for o primeiro a ser produzido no período t; igual a 0, caso contrário ikt Igual a 1, se o produto i for o primeiro a ser produzido no período t na máquina k; igual a 0, caso contrário 59 it Igual a 1, se o produto i for produzido por último no período t; igual a 0, caso contrário ikt Igual a 1, se o produto i for produzido na máquina k por último no período t; igual a 0, caso contrário it Igual a 1, se a máquina está preparada para o produto i no período t; igual a 0, caso contrário ikt Igual a 1, se a máquina k está preparada para o produto i no período t; igual a 0, caso contrário t Positivo quando pelo menos um produto é produzido no período t kt Positivo quando pelo menos um produto é produzido no período t na máquina k t Igual a zero, se exatamente um produto é produzido no período t; qualquer valor positivo, caso contrário kt Igual a zero, se exatamente um produto é produzido no período t na máquina k; qualquer valor positivo, caso contrário Apresenta-se a seguir a formulação do Modelo II. O Apêndice D apresenta esta formulação escrita na linguagem de modelagem Mosel do solver Xpress. Min Sij * Tijtk i , j N k K t T xikt i N k K t T 3.20 Sujeito a: xikt k K Di i, t 3.21 xikt yikt 0 i, k , t 3.22 3.23 yit i N 1 t, k yikt kt i, k , t 3.24 3.25 yikt i N 1 ( N 1) kt k , t 3.26 kt kt ikt 1 k , t i N ikt 1 k , t i N 3.27 60 ikt ikt yikt yikt i, k , t i, k , t 3.28 3.29 ikt ikt 2 kt i, k , t 3.30 3.31 ikt 1 t, k i N Tijkt ikt 1 jkt kt 1 i j, kt 3.32 Tijkt ikt jkt 1 1 i j, k , t 3.33 0 kt 1 t, k 3.34 0 xikt 1 0 kt 1 i, t, k t, k 3.35 3.36 T jit ,Yit , it , it , it Tiikt 0 i, k , t {0,1} i, j, k , t 3.37 3.38 yikt yik 't Rij 2 i j, k k ' , t 3.39 3.40 ikt 1 k , t i N ikt 1 k , t i N 3.41 kt k ,t 1 prep _ ini Stii i N k K k , t * yik1 k , t 3.42 3.43 A função-objetivo 3.20 busca minimizar o tempo de setup realizado e a quantidade de peças produzidas. As restrições 3.21 obrigam o atendimento à demanda. Nelas foram desconsideradas o controle de estoque, pois o modelo em estudo não necessita do dimensionamento de lote conforme comentado anteriormente, mas é necessário considerar a quantidade de peças a produzir, uma vez que isto está relacionado diretamente com o planejamento do setup. As restrições 3.22 garantem que sempre que houver uma produção xikt > 0, o valor de y será automaticamente igual a 1. A variável y é usada para identificar a 61 necessidade de setup. As restrições 3.23 impõem o limite de uma peça por período. Esta mudança caracteriza a alteração do modelo original de várias peças por período para uma peça por período. O controle de uma peça por período cria a possibilidade de saber quando uma peça está sendo feita, impedindo assim que a mesma ocupe outra máquina durante o mesmo período, que é uma restrição forte do problema. Note-se que no modelo proposto muda-se o controle da variável x, quantidade de peças, para a variável y, status se uma peça é produzida no período t. Nas restrições 3.24 o é forçado a ser 1 se algum item for produzido no período t. As restrições 3.25 garantem que se mais do que um produto for produzido no período, então será positivo. As restrições 3.26 e 3.27 garantem qual produto foi produzido primeiro e em último em cada período. As restrições 3.28 e 3.29 fazem com que e sejam exatamente iguais a 1 se um produto for produzido em um período. As restrições 3.30 garantem que seja igual a zero quando somente um produto é produzido no período t. As restrições 3.31 fazem com que somente uma máquina esteja preparada para uma peça em um período t. As restrições 3.32 e 3.33 são aplicadas quando mais do que um produto for produzido em um período. Estas restrições forçam que ao menos um Tijkt seja 1, para cada i, exceto quando este produto for o primeiro ou o último na sequência. As restrições 3.34 a 3.37 definem o domínio das variáveis. As restrições 3.38 garantem que não haverá setup quando uma máquina continuar preparada para uma mesma peça. As restrições 3.39 atendem à restrição de que existem peças que não podem ser produzidas ao mesmo tempo (peças incompatíveis), mesmo em máquinas diferentes. Esta restrição é representada pela variável Rij tal que Rij = 1, se as peças i e j não podem ser produzidas ao mesmo tempo, e Rij = 0, caso contrário. As restrições 3.40 e 3.41 garantem que não haverá mais do que uma peça produzida em um mesmo período. As restrições 3.42 evitam que exista espaços vazios no programa de entrega. As restrições 3.43 obrigam a ocorrência do setup inicial. 62 Para os testes computacionais com o Modelo II foi utilizado o solver Xpress com os dados mostrados nas Tabelas 20, 21, 22 e 23. Para estes testes foram consideradas 3 prensas. Tabela 20 – Setup de uma peça para outra Peça 1 2 3 Pe ça 1 0 3 5 2 3 0 4 3 5 4 0 Tabela 21 – Demanda por peça Peça 1 2 3 2 2 2 Tabela 22 – Incompatibilidade entre peças Peça 1 2 3 Pe ça 1 1 1 0 2 1 1 0 3 0 0 1 Tabela 23 – Setup inicial por peça Peças 1 2 3 7 8 9 Os resultados obtidos podem ser verificados nas Tabelas 24 e 25. Tabela 24 – Resultados obtidos com os Modelos I e II Modelo I II Setup inicial 16 16 Setup intermediário 3 3 Tempo de execução(s) 0,1 0,8 63 Tabela 25 – Sequenciamentos obtidos com os Modelos I e II Modelo I Modelo II Período Período 1 2 3 4 1 2 3 4 Pr en sa 1 1 1 2 2 1 1 2 2 2 3 3 3 3 3 Os resultados deste teste mostram que o tempo de execução do Modelo II é 8 vezes maior do que o do Modelo I. O sequenciamento mostrado na Tabela 25 foi idêntico para os dois modelos e respeita a restrição que impede que as peças 1 e 2 sejam produzidas ao mesmo tempo. A peça 1 foi colocada em primeiro lugar na sequência pois seu setup inicial é menor do que o da peça 2. Após este teste inicial uma nova bateria de testes foi realizada. Nestes testes fixou-se o tempo limite de execução em 7200 segundos. Isso se deve ao fato de que o tempo para solução de instâncias maiores é muito alto. A Tabela 26 apresenta os resultados dos testes realizados. NM - Número de máquinas; NP - Número de peças; NL - Número de linhas do modelo; NC - Número de colunas do modelo; Gap - Valor percentual do gap de dualidade (retornado pelo solver ); Setup - Tempo total de setup necessário; FO - Valor da função-objetivo; CPU – Tempo de execução (em segundos). Tabela 26 – Resultados dos novos testes computacionais Modelo I Modelo II NM NP NL NC Gap Setup FO CPU NL NC Gap Setup FO CPU 3 3 804 318 0 9 22 0,7 1614 690 0 7 20 1,0 3 4 1499 546 0 9 27 1,6 2509 1020 0 9 27 7,7 3 5 2422 840 0 11 33 2,8 3632 1410 0 11 33 40,8 3 6 3573 1200 0 14 41 58,6 4983 1860 0 14 41 321,4 64 3 7 5992 1926 7,16 19 50 7200 7924 3075 17 16 47 7200 3 8 7937 2508 9,68 24 60 7200 10109 3792 32,65 28 64 7200 3 9 11922 3660 6,7 19 78 7200 15819 5733 20,69 18 58 7200 3 10 19249 5724 10,81 27 72 7200 19267 6810 34,49 33 78 7200 3 11 23648 6918 12,98 33 82 7200 27806 9579 24,66 24 73 7200 3 12 28107 8226 8,25 26 80 7200 32805 11088 39,98 46 100 7200 3 13 36954 10668 13,33 42 100 7200 42574 14121 33,33 38 96 7200 3 14 54094 15321 15,85 53 116 7200 59111 19254 37,15 45 106 7200 3 15 62352 17580 15,63 56 123 7200 70377 22605 30,93 30 97 7200 3 20 135407 37230 12,77 59 149 7200 148037 45120 32,39 52 142 7200 3 25 285782 76920 16,11 92 204 7200 306622 90165 41,71 89 201 7200 Pela análise dos resultados obtidos, verifica-se que com 3 peças e 3 máquinas o Modelo II obtém um resultado melhor que o Modelo I. Isto se deve ao fato de que o Modelo II tem a capacidade de preservar a preparação de máquina mesmo sem obrigatoriamente ter uma produção, enquanto que no Modelo I esta característica não existe. Tal fato é inerente aos problemas que originaram estes dois modelos: o Modelo I teve origem em um DLSP enquanto que o Modelo II teve origem em um CLSP. O CLSP preserva o setup da máquina, enquanto que o DLSP obrigatoriamente precisa produzir em todos os períodos. A partir de 7 peças, ambos os modelos não conseguem obter a solução ótima dentro do tempo máximo programado para execução, por isso o gap de dualidade é não nulo. Segundo Rosa e Souza (2011), o gap mostrado pelo solver é a diferença percentual entre o valor da melhor solução viável encontrada (limite superior) e o limite inferior encontrado, é ou seja: Gap = 100% x (Limite superior - Limite inferior)/(Limite inferior) Deve-se observar, no entanto, que para a comparação dos Modelos I e II, o Gap não é uma boa medida, visto que as funções-objetivo não são as mesmas. 65 3.7 - Modelo III: minimização do makespan Lenstra et al. (1977) demonstram que o problema de minimização do makespan em máquinas paralelas é NP-difícil. Este problema pode ser considerado como o problema do caixeiro viajante e sua solução exata só é possível às custas de um grande esforço computacional. Alguns trabalhos serviram de base para o desenvolvimento do modelo proposto nesta seção. Tahar et al. (2006) apresentam um modelo matemático para a solução de um problema com máquinas paralelas idênticas com setup dependente da sequência e split de tarefas. Dastidar e Nagi (2005) desenvolveram um modelo para problema com máquinas não relacionadas e com setup dependente da sequência. Este modelo serviu como base para métodos de relaxação, visando encontrar soluções aproximadas para exemplares de médio e grande porte. Rocha et al. (2008) também apresentam um modelo para máquinas paralelas não relacionadas com setup dependente da sequência. Nenhum destes trabalhos, no entanto, trata da restrição de produção de peças que dividem o mesmo recurso. Com base nas idéias destes trabalhos, procurou-se modificar o Modelo I visando a minimização do makespan. Duas alterações foram necessárias. A primeira é na função objetivo, que deve ser mudada de uma minimização dos tempos de setup e produção para a minimização do makespan. O makespan é representado no modelo por meio de uma nova variável, Cmax. Mínimizar Cmax 3.44 Cmax Pti zikp Sij wijkp Sti zik1 3.45 i I k K p P i , j I i j k K p P i I k K A função objetivo 3.44 passa então a ser o máximo da soma do tempo de produção mais os tempos de setup entre as peças e o setup inicial. Mas apenas esta mudança não basta, a condição de min