Alfredo Carvalho de Castro Tamanhos de lotes capacitados com preparação de máquina em sistemas produtivos ininterruptos Dissertação apresentada a Escola de Engenharia da Universidade Federal de Minas Gerais para obtenção do título de Mestre em Engenharia de Produção Orientador: Professor Doutor Maurício Cardoso de Souza Belo Horizonte – MG Março de 2007 Programa de Pós Graduação em Engenharia de Produção – UFMG - ii - Alfredo Carvalho de Castro Tamanhos de lotes capacitados com preparação de máquina em sistemas produtivos ininterruptos Dissertação apresentada a Escola de Engenharia da Universidade Federal de Minas Gerais para obtenção do título de Mestre em Engenharia de Produção Orientador: Professor Doutor Maurício Cardoso de Souza MESTRADO EM ENGENHARIA DE PRODUÇÃO DEPARTAMENTO DE ENGENHARIA DE PRODUÇÃO ESCOLA DE ENGENHARIA UNIVERSIDADE FEDERAL DE MINAS GERAIS Belo Horizonte – MG Março de 2007 Programa de Pós Graduação em Engenharia de Produção – UFMG - iii - Resumo Este trabalho trata o problema de tamanho de lote econômico capacitado. Esta classe de problemas é abordada no caso específico dos sistemas produtivos em que os custos e tempos de preparação da máquina podem ser aproveitados em períodos consecutivos e que a produção não entre imediatamente em ritmo após seu início. O tipo de instalação abordada possui máquinas paralelas com única operação e vários produtos. Os custos, as demandas e capacidades são dinâmicos e o tempo é tratado como discreto. Este estudo é justificado pela freqüência deste tipo de problema e pelo impacto de um bom planejamento no resultado operacional. Como exemplo temos as indústrias de conformação mecânica (forjarias e estamparias), fundição sob-pressão e injeção de plástico. Nestes casos temos produtos fortemente associados a commodities, com valor agregado relativamente baixo, onde o custo de estoque impacta fortemente no resultado operacional. É freqüente também nestas indústrias o elevado custo imobilizado em máquinas e ferramentas onde a racionalização do plano de produção afeta fortemente o custo fixo operacional. A principal contribuição deste trabalho é a forma de se tratar o caso da precedência em ambientes com tempo discreto onde mais de um produto é produzido por período. O trabalho está organizado da seguinte forma: Inicialmente é feita uma introdução para possibilitar a contextualização do problema abordado no ambiente corporativo. No primeiro capítulo é feita uma revisão bibliográfica sobre os principais trabalhos encontrados que abordam o tema. No segundo capítulo é apresentado o problema da indústria automotiva de fundição sob-pressão de alumínio e desenvolvido o modelo que trata todas as particularidades observadas neste problema. O terceiro capítulo mostra o desempenho obtido na resolução de instâncias reais e de instâncias adaptadas das encontradas na literatura. No quarto capítulo é apresentada uma proposta de heurística construtiva para o problema. E no final é feita uma conclusão do trabalho. Palavras-chave: Set-up, Tamanho de Lotes, Fundição, Programação Inteira Mista, Planejamento de Produção. Programa de Pós Graduação em Engenharia de Produção – UFMG - iv - Abstract This work deal with the economic capacitated lot-sizing problem. It is focused on the problems that has setup times and costs with production ramp-up. The type of industry studied has parallel uni-mode machines in a multi-product dynamic demand. The costs and capacity are dynamic and time discrete. This effort is justified by the frequency of this type of problem and the impact of the production plan on the gross margin. This case can be found on material conforming industries, high-pressure die casting and injection mold facilities. In these cases the costs are mostly associated to commodities, in a lower added value situation were storage costs strongly affects the overall costs. Also in this type of industry the capital invested on machinery, installations and tooling demand a great share of the total costs. The main contribution of this work is the development of a method to treat the precedence factor when more the one product is produced on the same time period. This dissertation is organized as follows: Initially it is presented an introduction focusing the application this work on the corporate context. On the first chapter is presented a literature research around the main authors that have publish about Lot-Sizing. The second chapter the main problem of this dissertation is presented and a model is developed to treat this problem. On the third chapter the model performance is analyzed on real world instances and other ones developed based on the literature. The fourth chapter is presented a constructive heuristics approach to the problem. And at the end this work is concluded. Key-words: Lot-sizing, Set-up, Foundry, Mixed Integer Programming, Production Planning. Programa de Pós Graduação em Engenharia de Produção – UFMG - v - Sumário Introdução 1 Capítulo 1 – Problemas de tamanho de lote 5 1.1 Classificação e notação dos modelos de tamanho de lote 6 1.2 Modelos de lote econômico não capacitados 8 1.3 Modelos de lote econômico capacitados 11 1.4 Modelos de lote econômico capacitados com preparação (setup) 12 1.5 Artigos que tratam modelos de tamanho de lote 15 Capítulo 2 – Modelagem matemática 19 2.1 Apresentação do problema 21 2.2 Classificação 26 2.3 Notação 27 2.4 Formulação 30 2.5 Observações gerais 35 2.6 Avaliação preliminar dos resultados 36 Programa de Pós Graduação em Engenharia de Produção – UFMG - vi - 2.6.1 Apresentação dos problemas teste 36 2.6.2 Avaliação qualitativa 37 2.6.3 Avaliação quantitativa 39 Capítulo 3 – Avaliação de desempenho 42 3.1 Desempenho do modelo em casos reais 42 3.2 Desempenho do modelo em problemas encontrados na literatura 45 Capítulo 4 – Proposta de heurística construtiva 47 4.1 Elaboração da heurística 47 4.2 Pseudo-código 48 Conclusão 53 Referências 55 Programa de Pós Graduação em Engenharia de Produção – UFMG - vii - Lista de Figuras Figura 1 - Esquema de operações de uma organização 1 Figura 2 - Hierarquização da tomada de decisões 2 Figura 3 - Curva do custo total de Harris - EOQ 9 Figura 4 - Representação de uma máquina de injeção de alumínio (Fundição sob- pressão) 20 Figura 5 - Esquema do fluxo produtivo 21 Figura 6 - Demonstração da influência da seqüência de produção na preparação 23 Figura 7 - Regime normal de variação de demanda na indústria automobilística 24 Figura 8 - Gráfico do aproveitamento de peças após preparação 25 Figura 9 - Demonstração da modelagem da rampa de início de produção 29 Programa de Pós Graduação em Engenharia de Produção – UFMG - viii - Lista de Tabelas Tabela 1 - Classificação dos problemas de tamanho de lote conforme POCHET(2001) 7 Tabela 2 - Desempenho do modelo na resolução de problemas reais 44 Tabela 3 - Desempenho do modelo na resolução de problemas da literatura 46 Programa de Pós Graduação em Engenharia de Produção – UFMG - ix - Abreviaturas OEE – Overall Equipment Effectiveness / Efetividade total do equipamento CNC – Comando numérico computadorizado EOQ – Economic Order Quantity EPQ – Economic Production Quantity ELSP – Economic Lot sizing and Scheduling Problem CLSP – Capacitated Lot Sizing Problem CSLP – Continuous Setup Lot sizing Problem DLSP – Discrete Lot sizing and Scheduling Problem Programa de Pós Graduação em Engenharia de Produção – UFMG - x - Terminologia Backlogging Entrega futura de pedido com o consentimento do cliente Backorder Postergação da entrega do pedido sem o consentimento do cliente Capacidade Quantidade de tempo e recursos disponíveis para uma tarefa Demanda Quantidade de peças solicitadas por um cliente em um período OEE Fator de efetividade operacional de uma planta onde são agrupados os índices de qualidade, produtividade e disponibilidade. Precedência Condição onde uma peça permanece em produção na passagem de um período a outro. Ramp-up Curva de aquecimento que ocorre no momento do início da produção de uma peça Setup Tempo gasto na preparação de uma máquina para início de produção de uma peça Startup Tempo gasto para troca de produção entre duas peças distintas Tamanho de lote Quantidade de peças a serem produzidas em um determinado período e máquina Programa de Pós Graduação em Engenharia de Produção – UFMG - 1 - Introdução Diversas competências atuam no mundo empresarial na busca da melhoria de competitividade. Nas cadeias produtivas um grande tema de estudos é a gestão de operações, amplamente suportada pela pesquisa operacional. Esta é relacionada à sistematização das ações de controle e direcionamento dos processos que, conforme KRAJEWINSK e RITZMAN (1993), transformam as entradas (mão-de-obra, ativos, materiais, energia e capital) em saídas (produtos e/ou serviços) buscando maximizar os resultados da organização. A Figura 1, esquematiza o contexto organizacional onde as informações do cliente (demanda) e de performance (OEE) são os fatores direcionadores da atividade produtiva. Figura 1: Esquema de operações de uma organização Conforme estes autores, para a maximização do resultado operacional, as boas práticas de gestão consideram que uma empresa deve estar em sintonia desde o mais alto nível hierárquico até o chão de fábrica partindo do planejamento estratégico definido. Para isto Operações e Transformações Saídas Entradas Informações dos clientes Informações de desempenho Programa de Pós Graduação em Engenharia de Produção – UFMG - 2 - faz-se necessário uma hierarquização na tomada de decisões partindo do nível estratégico passando pelo tático e chegando ao operacional. Desta forma os problemas de programação da produção são escalonados em três níveis conforme ilustra a Figura 2. Figura 2: Hierarquização da tomada de decisões O “business plan” (ou plano de negócios) é uma projeção de demanda, custos e lucros geralmente acompanhada por um orçamento, balancete e fluxo de caixa projetado que indica as fontes e alocações de recursos. Ele é executado em um grande horizonte de tempo onde os resultados finais devem satisfazer os acionistas. O planejamento agregado é aquele que operacionaliza o “business plan” em forma de um plano generalizado agrupando recursos e produtos. Ele permite ao planejador derivar o plano de produção consistentemente com a estratégia adotada de forma macro, sem se preocupar com detalhes do chão de fábrica. Este tipo de planejamento parte de quantidades agregadas de produtos ou serviços, mão de obra ou tempo. A agregação de produtos ou serviços pode ser feita em famílias de produtos com similares requisitos de demanda ou produção. A agregação por mão de obra ocorre em função da flexibilidade de produção dos colaboradores em todas as famílias de produtos ou em produtos específicos. Conforme CARVALHO (1998), existem basicamente duas estratégias de planejamento agregado. A primeira é a de acompanhar a demanda, nela a empresa se adapta à demanda Programa de Pós Graduação em Engenharia de Produção – UFMG - 3 - mudando os volumes de produção mensais pela alteração da utilização dos recursos, gerando custos decorridos do aumento do “turn-over” e variação nos níveis de mão de obra. A segunda é a de nivelar a produção, onde os volumes de produção e mão de obra são mantidos e o estoque é utilizado para atender às alterações na demanda, gerando um elevado custo de estoque. O plano mestre de produção é o desdobramento do plano agregado em produtos específicos. Ele mostra as quantidades de cada produto a serem fabricadas em cada período no tempo. De acordo com HAX e CANDEA (1984), em função do mercado e produto as demandas no tempo podem ser constantes ou variáveis aceitando adiantamento ou atraso de entregas. Além disto, devido às características do chão de fábrica podem surgir restrições de capacidade máxima de produção, perdas de tempo com a preparação de máquina entre produtos diferentes. Neste ambiente, as boas práticas gerenciais atuam de forma a encontrar soluções que tratam os custos envolvidos em produção, estocagem e preparação de máquina de forma a se obter o melhor resultado operacional. O plano mestre de produção deve determinar quanto produzir de qual produto a partir de quando para o atendimento das necessidades dos clientes. Em função das características do problema de programação de produção existem mais de uma opção de alocação de recursos para atender a demanda do cliente. No entanto poucas delas ou somente uma é a solução ótima onde o máximo do resultado operacional é atingido. A pesquisa operacional, não se limitando a isto, é a disciplina que dá suporte a tomada de decisão na busca do melhor plano de produção por meio da modelagem matemática. Dentro desta disciplina temos dois tipos de modelos, os prescritivos e os descritivos. Nos modelos prescritivos, as variáveis são relacionadas a parâmetros através de relações matemáticas e um objetivo é posto para otimizar o resultado. Já os modelos descritivos são utilizados para avaliar o desempenho quantitativo de soluções propostas, eles não geram uma solução. Entre os modelos descritivos temos modelos de alocação estática, análise de filas, simulação e rede Petri. Programa de Pós Graduação em Engenharia de Produção – UFMG - 4 - Nesta dissertação é tratada a modelagem matemática para otimização do plano mestre de produção. O ambiente de produção é mono-estágio ininterrupto, considerando capacidade e necessidade de preparação. Um caso particular deste tipo de ambiente é encontrado na indústria de fundição automobilística. Buscamos um modelo de tamanho de lote (“Lot Sizing”) descritivo que maximiza o resultado operacional da planta. São considerados limites de capacidade dinâmicos e ocorrência de preparação em períodos ininterruptos de tempo onde os sistemas são de única operação com vários produtos. São avaliados os custos de estoque e preparação frente a margem de contribuição de cada produto na busca do melhor resultado. A organização deste trabalho foi feita da seguinte forma: Inicialmente é apresentada uma introdução que permite ao leitor se situar no ambiente empresarial e nos problemas de decisão enfrentados pelos gerentes. Em seguida o Capítulo 1 mostra trabalhos de pesquisadores encontrados na bibliografia que abordam este tipo de problema. No Capítulo 2 é feito o desenvolvimento do modelo de programação inteira para o problema tratado. São apresentados também testes de funcionamento com o software GLPK. No capítulo seguinte é feita uma análise sobre os resultados obtidos em problemas teste baseados em situações reais das indústrias de três portes distintos e problemas encontrados na bibliografia. E finalmente no Capítulo 4 é apresentada uma heurística construtiva desenvolvida para resolução deste problema Programa de Pós Graduação em Engenharia de Produção – UFMG - 5 - Capítulo 1 – Problemas de tamanho de lote O problema de tamanho de lote de produção consiste em determinar quais produtos e em que quantidades produzir e estocar em cada período dentro de um horizonte de planejamento de modo a atender demandas pré-estabelecidas. Os modelos que tratam este problema buscam principalmente otimizar os custos para permitir a obtenção do melhor resultado operacional, desta forma são nomeados Problemas de Lote Econômicos. Os três principais custos envolvidos nos processos fabris que alteram o resultado operacional da instalação são: • Custo de produção de uma peça - é aquele composto pelos custos variáveis de materiais diretos ou insumos, mão de obra, energia e materiais indiretos e o custo fixo geral da instalação quantificada de acordo com o critério de rateio definido pela empresa e custo de oportunidade. • Custo de estocagem - corresponde à soma de todos os custos de manutenção do estoque em um determinado período de tempo como o custo financeiro, de seguro, de manutenção entre outros. • Custo de início de produção, preparação ou setup - inclui o montante envolvido na preparação como mão de obra, materiais indiretos e custos logísticos entre outros. Neste capítulo é apresentada a revisão da literatura sobre este tema. Inicialmente é observada a classificação dos problemas de tamanho de lote. Em seguida são apresentados os modelos clássicos encontrados na literatura estudada, os modelos de lotes econômicos não capacitados, capacitados e os que consideram as perdas com preparação. No final Programa de Pós Graduação em Engenharia de Produção – UFMG - 6 - apresentamos artigos recentes que tratam problemas similares ao problema que focamos neste trabalho. 1.1. Classificação e notação dos modelos de tamanho de lote Conforme POCHET (2001), a classificação dos problemas de tamanho de lote pode ser feita em função das características principais do problema. Estas características variam em função da demanda, quantidade de itens ou produtos e restrição de capacidade. A demanda pode ser constante ou não em função das características mercadológicas do produto final. Por exemplo, temos a produção de sal para culinária que pode ser enxergada como demanda constante, pois não sofre variações sazonais partindo do princípio que a taxa de consumo de sal per capita não varia bruscamente. Em contrapartida temos a indústria farmacêutica onde os volumes de produção de cada medicamento variam em função das enfermidades mais freqüentes em períodos diferentes do ano, desta forma caracterizando uma demanda flutuante. A quantidade de itens que podem ser produzidos em um único meio produtivo também afeta em muito a formulação matemática necessária para otimização. Em alguns casos, uma instalação ou máquina só pode produzir um único produto, por exemplo, uma plataforma de petróleo que não possui fim produtivo alem de extração. Em outros casos temos meios produtivos altamente flexíveis como centros de usinagem CNC’s que podem usinar uma peça diferente a cada instante. E por último a restrição de capacidade. Em alguns casos a limitação de capacidade produtiva não é relevante para a tomada de decisão. Isto pode ocorrer em casos onde as demandas são relativamente baixas frente às capacidades ou quando se tem uma linha de produção onde o processo a ser modelado não é gargalo. Porém são muito freqüentes os casos onde a capacidade disponível impacta fortemente no plano de produção. A Tabela 1 mostra os principais problemas de tamanho de lote de acordo com a classificação de POCHET (2001). Programa de Pós Graduação em Engenharia de Produção – UFMG - 7 - Não capacitado Capacitado Único item EOQ – Economic Order Quantity (matéria prima) EPQ – Economic Production Quantity (produção) Demanda constante Multi- item Problemas de tamanho de lote de produção seriada e de linha de montagem Seqüênciamento de lote econômico Único item Problemas de tamanho de lote não capacitados Problemas de tamanho de lote capacitados Demanda dinâmica Multi- item ELSP – Economic Lot sizing and Scheduling Problem CLSP – Capacitated Lot Sizing Problem CSLP – Continuous Setup Lot sizing Problem DLSP – Discrete Lot sizing and Scheduling Problem Tabela 1: Classificação dos problemas de tamanho de lote conforme POCHET(2001) Sendo mais específico, SALOMON (1991) apresenta a notação comumente utilizada na bibliografia que aborda os problemas de tamanho de lote. Esta notação caracteriza o problema através do sistema se seis campos mostrados abaixo para descrever as variantes do “Discrete Lotsizing and Scheduling Problem”. L/M/N/SC/PC/ST Cada campo é preenchido conforme o problema que se está querendo especificar, sendo: L Layout da linha de produção que pode ser paralela idêntica (PI), paralela uniforme (PU) e paralela sem relação (P) M A quantidade de máquinas presentes no problema Programa de Pós Graduação em Engenharia de Produção – UFMG - 8 - N A quantidade de peças presentes no problema SC A forma de incidência do custo de preparação, que pode ser inexistente (A), dependente da seqüência (SD), independente da seqüência (SI) e dependente do tempo (TD), PC A forma de incidência dos custos de produção que pode ser constante (C) ou variável (G) ST A forma de incidência do tempo de preparação como ausente (A), dependente da seqüência (SD) ou independente da seqüência (SI) 1.2. Modelos de lote econômico não capacitados Abaixo faremos uma revisão sobre os modelos clássicos de Tamanho de Lote Econômicos não capacitados, ou seja, com recursos ilimitados para produção. O primeiro trabalho encontrado na literatura que aborda este tema é o de HARRIS (1913). Conhecido como EOQ – Economic Order Quantity, ele apresenta a formulação para o problema de tamanho de lote econômico não capacitado com demanda constante. Neste trabalho, Harris desenvolve a formulação derivando a curva formada pela soma da reta do aumento do custo de estocagem em função do tamanho de lote estocado e a curva de redução do custo de colocação do pedido em função do tamanho do lote pedido. A derivação da curva obtida permite encontrar o ponto de menor custo, o EOQ. A Figura 3 mostra este raciocínio. Programa de Pós Graduação em Engenharia de Produção – UFMG - 9 - Figura 3: Curva do custo total de Harris - EOQ Com este raciocínio Harris chegou na seguinte formulação: h ds EOQ 2 = Onde EOQ é o lote econômico de produção, d é a demanda anual, s é o custo de colocação do pedido (set-up) e h é o custo de manutenção do estoque. A partir do modelo de Harris, WAGNER e WHITIN (1958) desenvolveram uma formulação que considera demandas dinâmicas. Esta formulação é baseada em dois teoremas principais sendo capaz de encontrar a solução ótima. O primeiro teorema diz que existe uma solução ótima em que, para todo período o produto do estoque resultante do período anterior e da quantidade produzida no período é zero. Ou seja, a hipótese de “completar um pouquinho” para atender uma demanda não é ótima. O segundo teorema afirma que podemos dividir o 0 500 1000 1500 2000 2500 3000 3500 0 50 100 150 200 250 300 Tamanho de Lote, Q [pçs] Custo de Estocagem = (Q/2)H Custo de Colocação do Pedido = (D/Q)S Custo Total = (Q/2)H+(D/Q)S Ponto de Menor Custo EOQ = 55 pçs C u s to [ $ ] Programa de Pós Graduação em Engenharia de Produção – UFMG - 10 - problema principal em sub-problemas independentes, desta forma fracionando a resolução. Com estes teoremas provados o modelo final ficou da seguinte forma: ∑ = + T t tt hexp 1 ))((min (1) s.t. tttt dexe =−+−1 para todo t = 0 , ... , T (2) 00 == Tee para todo t = 0 , ... , T (3) tx , te ≥0 para todo t = 0 , ... , T (4) Onde d é a demanda, p e h são respectivamente o custo fixo de produção e o custo de manutenção do estoque, e é o estoque e x a produção cada qual no período t. A função )( txp retorna uma constante se x é maior que zero e zero caso contrário. Neste modelo a função objetivo busca a redução do custo total obtido pela soma do custo de estoque e de preparação de máquina. A restrição (2) é a que trata o equilíbrio de massa entre estoque, demanda e produção. A restrição (3) força o estoque inicial e final iguais a zero e a restrição (4) é a de não negatividade para as variáveis. Outro modelo de lote econômico não capacitado encontrado na literatura é o de HANSSMANN (1962) que trata o problema ELSP – Economic Lot sizing and Scheduling Problem. Este problema é caracterizado por vários produtos sendo produzidos em uma única máquina onde existe custo de preparação e estoque. O modelo apresentado por eles considera o tempo como contínuo e finito, e a demanda, taxa de produção, custo de preparação e estocagem constantes. O modelo busca em cada período o seqüenciamento que minimiza a soma do custo de preparação e estoque. ∑ = ∈        − + N i iiiii i i Ftt trddh t s N 1 ),...,( 2 )/1( min 1 Programa de Pós Graduação em Engenharia de Produção – UFMG - 11 - Onde N é o conjunto de itens, F é o conjunto de períodos onde o seqüênciamento é viável, is é o custo de preparação do produto i, ih é o custo unitário de estocagem do produto i, id é a demanda do produto i no período t, ir é a taxa de produção da peça i e it é o tempo de ciclo de i. 1.3. Modelo de lote econômico capacitado O CLSP “Capacitated Lot Sizing Problem” determina os tamanhos de lotes de vários produtos a serem produzidos em uma única máquina de forma que a soma dos custos de estoque e produção sejam minimizado. A demanda dos produtos varia em cada período de tempo e a postergação da entrega sem o consentimento do cliente (backorder) não é permitido. O limite de produção é determinado por uma capacidade máxima disponível. Formulação básica do CLSP conforme SALOMON (1991) sem a preparação ( )∑∑ = = + N i T t tititii xpeh 1 1 ,,,min (1) s.t. itititti dexe =−+−1, para todo i, t (2) t N i tii cxb ≤∑ =1 , para todo t (3) itx , 0≥ite para todo i, t (4) Onde N é o conjunto de itens ou produtos, T é o conjunto de períodos, ith é o custo unitário de estocagem do produto i no período t, itp é o custo unitário do produto i no período t, ib é a unidade de capacidade utilizada para produção de i, itd é a demanda do produto i no período t, itx é a produção de uma unidade de i no período t, it e é o estoque de i no final do período t e tc é a capacidade disponível para produção no período t. Programa de Pós Graduação em Engenharia de Produção – UFMG - 12 - Neste modelo observamos a função objetivo (1) minimizando o custo de estoque somado ao custo de produção. Nas restrições (2) o balanço de materiais e (3) a imposição da capacidade de produção. A restrição (4) é a de não negatividade. 1.4. Modelos de lote econômico capacitados com preparação (setup) Continuando com os modelos de lote econômico capacitados apresenta-se aqui os modelos que consideram a preparação. Em primeiro temos o mesmo CLSP “Capacitated Lot Sizing Problem” apresentado anteriormente porém neste com a restrição de preparação, conforme se observa abaixo. ( )∑∑ = = ++ N i T t tititiitii xpehys 1 1 ,,,,min (1) s.t. itititti dexe =−+−1, para todo i, t (2) t N i ititii cyaxb ≤+∑ =1 , )( para todo i, t (3) 0,, ≤      − ∑ = ti T t tiit ydx τ para todo i, t (4) { }1,0∈ity para todo i,t (5) itx , 0≥ite para todo i, t (6) Onde its é o custo de preparação do produto i no período t, ity é a variável binária que determina a ocorrência de preparação de i no período t, ia é o tempo de preparação para a peça i e o restante da notação é a mesma utilizada para o CLSP. Nesta versão temos a função objetivo (1) alterada com a inclusão do custo de preparação associada à variável binária de preparação ity , a restrição (3) considera a perda com Programa de Pós Graduação em Engenharia de Produção – UFMG - 13 - preparação na capacidade, a (4) que faz ity = 1 quando necessária produção para atender a demanda e a (5) a que estabelece ity como binária. Observa-se que como formulada a restrição (4) ocorrerá preparação sempre que existir produção, independente da máquina já estar preparada para produção ou não. Outro modelo encontrado nesta classe é o CSLP “Continuous Setup Lot sizing Problem”. Apesar de similar ao CLSP, neste o custo da preparação existe somente no início da produção ininterrupta de uma peça. No entanto este modelo permite a produção somente de uma peça por período enquanto o outro permite a produção de várias peças no mesmo período. Formulação do CSLP indicada por SALOMON (1991) ( )∑∑ = = ++ N i T t itititiiti xpehzs 1 1 min (1) s.t. itititti dexe =−+−1, para todo i, t (2) 1, −−≥ tiitit yyz para todo i, t (3) ∑ = ≤ N i ity 1 1 para todo t (4) itititi ycxb ≤ para todo i, t (5) itx , 0≥ite para todo i, t (6) { }1,0, ∈itit zy para todo i, t (7) Onde itc é o limite de capacidade de produção de i no período t, itz é uma variável que indica a ocorrência da preparação do produto i em t e o restante da notação é a mesma utilizada para o CLSP. Programa de Pós Graduação em Engenharia de Produção – UFMG - 14 - Neste modelo a restrição (3) promove a alocação do custo de preparação na função objetivo somente na retomada da produção da peça. A equação (4) garante que a produção de apenas um produto i ocorra no período t. As demais equações são similares ao CLSP. Além destes dois encontra-se na literatura também o DLSP “Discrete Lot sizing and Scheduling Problem” cuja formulação é similar ao CSLP. No entanto no DLSP a quantidade produzida é ou zero ou a capacidade máxima de produção (ou tudo ou nada – “all or nothing”). A versão genérica sugerida por FLEISCHMANN (1990) em programação inteira mista é a seguinte: Formulação do DLSP ( )∑∑ = = ++ N i T t tiititiiiti yrpehzs 1 1 ,,,min (1) s.t. tititiiti deyre ,,,1, =−+− para todo i, t (2) 1, −−≥ tiitit yyz para todo i, t (3) ∑ = ≤ N i tiy 1 , 1 para todo t (4) 0≥ite para todo i, t (5) { }1,0, ∈itit zy para todo i, t (6) Onde ir é a taxa de produção de i e o restante da notação é a mesma utilizada para o CSLP. A diferença básica desta formulação frente a do CSLP é a ausência da variável itx . Ela é substituída pela componente tii yr , , isto caracteriza a condição “ou tudo ou nada”. Programa de Pós Graduação em Engenharia de Produção – UFMG - 15 - 1.5. Artigos que tratam modelos de tamanho de lote Além dos modelos clássicos mostrados anteriormente, aqui são mostrados trabalhos publicados que abordam o tipo de problema estudado. POCHET (2001) classifica o problema que estamos abordando em “Small buckets capacitated Lotsizing with setup times model”. Nesta classificação, small bucket caracteriza os problemas onde a preparação gera grandes impactos em capacidade e custos. No seu trabalho ele diferencia dois tipos de preparação presentes na alternância de produtos, o start- up e a troca. A troca ou Change-over ocorre quando o tempo e custo de preparação variam em função da seqüência de produtos. O Start-up ocorre quando os tempos e custos de preparação são independentes da seqüência de produção. O pesquisador apresenta o conjunto de equações abaixo que permitem a diferenciação das duas variáveis binárias, uma para Start-up e outra para troca. ∑ = i ity 1 para todo t, (1) 1, −−≥ tiitit yyz para todo i, t (2) 11, −+≥ −tiit j it yyw para todo i, j e t (3) ity , itz e j itw = 0 ou 1 para todo i, j e t (4) Neste ity é a variável binária de preparação do produto i no período t, itz é o binário de startup do produto i em t e j itw é o binário de troca de produto i para j em t. A equação (1) impõe somente uma preparação por período. A (2) força o startup quando o produto entra em produção no período 1=ity e 01, =−tiy . E a (3) força a troca quando um produto i vai ser alterado para j quando 11, == −tijt yy . Programa de Pós Graduação em Engenharia de Produção – UFMG - 16 - KARMARKAR e SCHRAGE (1985) publicaram o trabalho intitulado “Deterministic Dynamic Product Cycling Problem” onde tratam o problema de uma máquina com vários produtos e custo de preparação. Os autores apresentam duas reformulações do problema. A primeira considera o custo de start-up ou de troca. Este ocorre quando o tempo improdutivo entre produtos varia em função dos produtos que são alternados. Como exemplo temos o caso do tempo necessário para início de produção de tinta clara após a produção de tinta escura. A alteração de clara para escura é rápida enquanto de escura para clara é demorada. E a segunda reformulação considera o fator da precedência entre dois períodos quando um mesmo produto é produzido, sendo que no máximo um produto é produzido por período. Com esta no segundo período consecutivo de produção de uma mesma peça não é necessária preparação. O leitor também pode se referenciar no exame de literatura feita por DREXL A. e KIMMS A. (1997). Além deste existem também os problemas correlatos abordados por KARMARKAR indicados na Revisão Bibliográfica entre eles KARMARKAR (1987a) “Lot Sizes, Lead Times and In-Process Inventories”, KARMARKAR (1987b) “Lot Sizes and sequencing delays” e KARMARKAR, KEKRE SHAM e KEKRE SUNDER (1986) “The dynamic Lot-sizing problem with startup and reservation costs”. TRIGEIRO, THOMAS e McCLAIN (1989) abordaram o problema “Capacitated Lot Sizing with Setup Time”. Em seu artigo eles abordam o problema utilizando relaxação lagrangeana na restrição de capacidade do CLSP permitindo a decomposição em sub-problemas não capacitados de único item. Estes são tratados utilizando o modelo de Wagner e Whitin em uma heurística para construir soluções viáveis dentro das restrições de capacidade. Os custos e tempos de preparação são dinâmicos. Uma consideração que os autores fazem é que esta formulação não permite ordenar tarefas dentro do mesmo período dada a forma de aplicação da preparação. O modelo formulado considera tempos e custos de preparação. NABIL A. e SAFIA K. (2002) também abordaram este problema. Para o mesmo tipo de problema, JANS R. e DEGRAEVE Z. (2005) apresentam uma análise sobre as meta-heurísticas que tratam os problemas de tamanho de lote dinâmicos. VANDERBECK (1998) publicou seu artigo que trata o problema “Lot-Sizing with Start-Up Times”. No artigo ele trata o problema com preparação contínua, ou seja, a produção pode Programa de Pós Graduação em Engenharia de Produção – UFMG - 17 - variar de zero até a capacidade máxima uma vez a preparação concluída, ao contrário da preparação discreta, onde a produção é em plena capacidade quando concluído a preparação. Nesta condição o start-up ocorre toda vez que um item iniciar produção. Para resolver este problema é utilizado um algoritmo de geração de colunas em programação inteira e planos de corte para o poliedro. Um procedimento para o sub-problema de uma peça foi desenvolvido que trata o estoque inicial como variável de decisão. Desta forma é obtido um baixo tempo computacional para problemas tidos como grandes (750 segundos para o resultado ótimo em problemas com 36 períodos e 5 itens). CONSTANTINO M. e ANGRA A. (1999) também apresentaram um trabalho neste contexto, no entanto considerando o backlogging. Além destes existem também as publicações de WOLSEY como WOLSEY (2002) “Solving Multi-Item Lot-Sizing Problems with an MIP Solver Usinf Classification and Reformulation”, WOLSEY e BELVAUX (2001) “Modelling Practical Lot-Sizing Problems as Mixed-Integer Programs” e WOLSEY , TZUR e ANILY (2005) “Multi-item lot-sizing with a joint set-up cost”. AGGARWAL A. E PARK J. (1993) publicaram o artigo “Improved algorithms for economic lot size problems”, que mostra que a maioria dos problemas de lote econômico geram uma matriz similar que pode rapidamente ser resolvida por algoritmos. Eles tratam especificamente os problemas não capacitados. Em seguida TAYLOR, TAHA e CHOWNING (1997) apresentaram uma heurística para tratar o “Sequence-dependent Lot Scheduling Problem”. Apesar de apresentarem uma formulação de fácil aplicação considerando tempo e custo de preparação, a heurística apresentada considera o problema com demanda constante no tempo. DASTIDAR e NAJI (2005) apresentaram o artigo “Scheduling injection molding operations with multiple resource constraints and sequence dependent setup times and costs”, tratando um caso na indústria injeção em moldes similar ao abordado neste trabalho. Na modelagem abordada os autores consideram o problema de máquinas paralelas multi-itens capacitado com custos e tempos de preparação dependente da seqüência. O objetivo posto é atender a demanda minimizando os custos de estocagem e preparação com aceitação de backlogging. Em função da complexidade da formulação eles utilizam uma estratégia de resolução com Programa de Pós Graduação em Engenharia de Produção – UFMG - 18 - decomposição em duas fases baseados em centros de trabalho para conseguirem um tempo de resolução razoável. GOPALAKRISHNAN M., DING K., BOURJOLLY J.M. e MOHAN S. (2001) apresentam uma heurística (busca-tabu) formada de cinco etapas que dividem as decisões de seqüenciamento e de tamanho do lote. Eles apresentam um procedimento que calcula a qualidade da resposta e mostram que em 540 problemas testes os resultados obtidos ficaram a 12% do ótimo. Outro ponto importante que estes autores mostram é a redução de 8% no custo total em função da consideração da precedência nestes problemas teste. HAUGEN, OLSTAD e PETTERSEN (2005) mostram uma versão do CLSP onde a função objetivo foca a maximização do lucro. Para isto o modelo considera não só o custo de produção mas também o preço da peça. No artigo os autores tratam a demanda como uma função linear decrescente do preço da peça. Esta abordagem é específica em função do mercado consumidor da peça e garante uma resposta melhor e mais rápida quando comparada ao CLSP tradicional. Com base na bibliografia estudada observamos vários modelos que tratam o problema. No entanto a literatura não apresenta nenhuma abordagem completa para o problema específico aqui abordado, inclusive que considere o fator da precedência para multi-itens e multi- máquinas. O capítulo seguinte mostra o desenvolvimento do modelo que trata o problema central desta dissertação. Programa de Pós Graduação em Engenharia de Produção – UFMG - 19 - Capítulo 2 – Modelagem matemática Neste capítulo o problema central desta dissertação é modelado. Inicialmente é apresentado o problema indicando todas suas particularidades que devem ser consideradas no modelo. Em seguida inicia-se fase de modelagem do problema, começando de uma formulação básica inicial que é desenvolvida até o modelo final. E finalmente é apresentada a análise de alguns resultados em problemas pequenos com fins ilustrativos. O objetivo é desenvolver um modelo matemático prescritivo que cubra todas as particularidades deste problema e apresente uma solução ótima com o maior resultado operacional em um tempo computacional razoável para uma instância de porte das indústrias sujeitas a este sistema. Como solução ótima, deseja-se obter todas as informações a serem passadas para o nível operacional (quanto, de qual peça, em qual máquina e quando produzir) para atender à demanda do cliente. Este estudo é justificado pela ampla abrangência deste tipo de problema. Estas condições são encontradas em indústrias onde existe a relação máquina-ferramenta. Como mais freqüentes exemplos temos as de conformação mecânica (forjarias e estamparias), fundição sob-pressão e injeção de plástico. Nestes casos temos produtos fortemente associados a commodities, com valor agregado relativamente baixo, onde o custo de estoque impacta fortemente o resultado operacional. É freqüente também nestas indústrias o elevado custo imobilizado em máquinas e ferramentas onde a racionalização do plano de produção afeta fortemente o custo fixo operacional. Programa de Pós Graduação em Engenharia de Produção – UFMG - 20 - Um caso típico dos sistemas aqui tratados é o caso da indústria de fundição sob-pressão de alumínio. A Figura 4 mostra o esquema de montagem de uma ferramenta em uma máquina de injeção de alumínio. A ferramenta de injeção fica posicionada entre as placas da injetora. Consideramos ferramenta o molde ou estampo necessário para produzir (fundir ou conformar) um peça na máquina operatriz (injetora). Figura 4: Representação de uma máquina de injeção de alumínio (Fundição sob-pressão) O ciclo produtivo da máquina é formado pelas operações: 1) Fechamento das placas pelo cilindro de fechamento que movimenta as articulações e desloca a placa móvel e a parte móvel da ferramenta até o curso final de fechamento; 2) Vazamento da liga líquida dentro da bucha de injeção por um forno automático, robô de vazamento ou concha manual; 3) Injeção da liga líquida pelo pistão acionado pelo cilindro injetor para dentro da cavidade formada pelas duas partes da ferramenta; 4) Abertura da ferramenta pelo deslocamento da placa móvel executada pelo cilindro de fechamento; Acumulador Cilindro Injetor Pistão Bucha de Injeção Ferramenta Placas Articulação Colunas Cilindro de Fechamento Programa de Pós Graduação em Engenharia de Produção – UFMG - 21 - 5) Extração da peça, limpeza da ferramenta e aplicação da solução desmoldante manual ou automaticamente. Dentro desta cadeia produtiva existem operações anteriores, como preparação de liga, e posteriores, como rebarbação, inspeção e pré-usinagem. No entanto estas, na grande maioria dos casos, não são os gargalos da cadeia. Cada injetora possui características que definem sua capacidade de produzir peças de portes diferentes. Além disto existem diferentes graus de automação que afetam em muito os tempos de ciclo para produção de uma mesma peça. Por estes motivos cada máquina é única, tendo capacidade de produção de peças e tempos de ciclo distintos. 2.1. Apresentação do problema O problema possui as seguintes condições e restrições: • Ciclo produtivo constituído de uma única operação, relatado na bibliografia como mono-estágio ou “single-level”. No caso das indústrias de injeção estamos modelando somente a operação de injeção, pois esta é normalmente é o gargalo deste processo. Na Figura 5 apresentamos o esquema do fluxo produtivo, estaremos modelando a etapa ranhurada do fluxo. Figura 5: Esquema do fluxo produtivo Disponibilidade – Máquina / Ferramenta Matéria Prima Produção Estoque Cliente Pedido Programa de Pós Graduação em Engenharia de Produção – UFMG - 22 - • O layout comum das plantas é Multi-máquinas paralelas - Modelagem de várias máquinas produzindo independentemente umas das outras. As máquinas são heterogêneas, desta forma cada máquina tem capacidade de produzir apenas uma parte do mix de produção. Isto varia em função das limitações técnicas de cada máquina. • Limitação de capacidade de máquina - O limite máximo de horas disponíveis para produção em cada máquina e período é variável em função dos planos de manutenção e outros fatores externos ao problema. • A preparação é presente apenas no início da produção de cada peça - Caso a produção de uma peça em uma máquina se estenda por mais de um período, só existe perda de tempo com preparação no primeiro período de produção. A Figura 6 apresenta diversas condições de seqüenciamento. Nela podemos observar que o tempo total disponível para produção da máquina 1 é superior ao da máquina 3 em função da perda de tempo devido à quantidade de preparações necessárias para o cumprimento do plano. Pode-se afirmar que a redução do número de preparações contribui para a maximizar a utilização da capacidade. No entanto ele se torna necessário quando a quantidade a ser produzida não satura completamente uma máquina e não existem máquinas dedicadas a um único produto. Para melhor utilização dos recursos aplica-se o conceito de precedência. Definição: A precedência de uma peça em uma máquina ocorre quando na passagem de um período para outro a peça permanece em máquina. Desta forma, com a precedência não é necessário a realização de preparação para retomada de produção. Em outras palavras, quando a peça for a última a ser produzida em um período e a primeira a ser produzida no período seguinte não é necessária a realização da preparação. Como são os casos da máquina 1, e da peça 8 na passagem dos períodos 2 e 3 na máquina 3 apresentados na Figura 6. Programa de Pós Graduação em Engenharia de Produção – UFMG - 23 - Maquina 1 Peça 1 Peça 1 Peça 1 Maquina 2 Peça 2 Setup Setup Maquina 3 Peça 6 Setup Peça 7 Setup Peça 8 Setup Peça 9 Período 1 Período 2 Período 3 Peça 3 Peça 4 Peça 8 Figura 6: Demonstração da influência da seqüência de produção na preparação • O custo e tempo de preparação são variáveis - O custo e tempo de preparação variam para cada peça em cada máquina em função dos tempos gastos e materiais. Isto ocorre frequentemente associado ao grau de automação da máquina. Existem máquinas com sistema de extração de colunas hidráulico que consomem 2 minutos para extração, enquanto outras onde a extração é manual e pode demandar mais de 30 minutos. Além disto na mesma máquina uma ferramenta pode demandar a extração das duas colunas superiores, enquanto outra só demande a extração de uma. • Multi-itens - Na linha podem ser produzidos diversos produtos em máquinas paralelas ao mesmo tempo, desde que disponível ferramenta. • Uni modal - Uma máquina só pode ser utilizada por uma ferramenta de cada vez, sendo que cada produto pode ser produzido por uma ou mais ferramentas, desde que exista uma quantidade de ferramentas que possibilite isto. Em alguns casos, principalmente para peças de pequeno porte, uma mesma ferramenta pode possuir mais de uma matriz, possibilitando a produção de mais peças por ciclo. • Tempo discretizado e finito – O tempo é dividido em períodos (semanas). • Demanda variável com estabelecimento de máximo e mínimo - Em cada período é estabelecido um volume mínimo e máximo de demanda a ser atingida para cada produto. Esta condição é freqüente quando existe limitação de capacidade de outra planta que produz a mesma peça. Na indústria automobilística o mesmo motor pode Programa de Pós Graduação em Engenharia de Produção – UFMG - 24 - ser fabricado em mais de um local no mundo. Desta forma, quando existe uma limitação de capacidade de uma planta a outra planta pode cobrir a demanda não atendida. A variação da demanda no horizonte de planejamento obedece aos acordos logísticos firmados entre montadora e fornecedora. Na maioria dos casos, esses acordos adotam uma previsão de demanda atualizada semanalmente onde as primeiras duas semanas possuem demanda congelada, as duas seguintes podem variar até 15% e a partir da quinta semana a variação pode ser de até 100%. A Figura 7 abaixo ilustra este conceito. EDI - Montadora X Emissão: Semana 15 Produto A Semana 16 17 18 19 20 21 22 Demanda (pçs) 1.500 1.700 1.850 1.640 1.500 1.600 1.700 Demanda max 1.500 1.700 2.128 1.886 ∞ ∞ ∞ Demanda min 1.500 1.700 1.573 1.394 0 0 0 Demanda congelada Variação de +/- 15% Figura 7: Regime normal de variação de demanda na indústria automobilística • Tamanho de lote variável – Não existe tamanho de lote pré-definido. E não se impõe nenhuma restrição técnica à produção de qualquer tamanho de lote. • Número de ferramentas capacitado - Existe um número máximo de ferramentas de cada tipo de peça. A determinação da quantidade de ferramentas é uma decisão estratégica do cliente. Os critérios de definição estão associados à demanda mínima contratada, taxa de falhas, análise de risco e custo entre outros. A técnica de determinação da quantidade de ferramentas não é abordada neste estudo. • Capacidade de preparação limitada no período – Em função do conhecimento técnico demandado existe uma equipe especializada na preparação. Esta equipe tem uma Programa de Pós Graduação em Engenharia de Produção – UFMG - 25 - limitação de capacidade que deve ser observada no momento da determinação das mudanças de ferramenta nas máquinas. Uma particularidade tratada é o caso da rampa de aproveitamento. O conceito da rampa de aproveitamento consiste na idéia que durante o período inicial de produção após a preparação da máquina o aproveitamento das peças não está estável como quando decorrido um período maior de produção. Este caso é comum neste processo pois o efeito do aquecimento das ferramentas afeta diretamente a qualidade do produto produzido. A Figura 8 mostra um caso real, nele temos a relação existente entre a quantidade de peças boas produzidas e a quantidade de dias de produção após a preparação de uma peça. Podemos observar que nos primeiros dias após a preparação, o número de peças boas produzidas é inferior ao número após o quarto dia de produção. Vale observar que o tempo de ciclo é constante, ou seja, a capacidade diária de produção é constante desde o momento da preparação. Rampa de retomada de produção - SU Amazon y = 103,54Ln(x) + 462,13 R2 = 0,8905 300 350 400 450 500 550 600 650 700 750 1 2 3 4 5 6 7 8 9 Dia de produção após set-up P e ç a s b o a s p ro d u z id a s Figura 8: Gráfico do aproveitamento de peças após preparação Se analisarmos um sistema onde a produção utiliza os conceitos do JIT (Just In Time) onde estoques intermediários são baixos e a produção é puchada pela demanda, esta particularidade gera dois efeitos no sistema: Programa de Pós Graduação em Engenharia de Produção – UFMG - 26 - • Efeito um (aumento de capacidade): Quando há elevada saturação da produção, a redução da quantidade de preparações possibilita mais tempo disponível para produção, aumentando assim a capacidade de produzir peças boas e, por conseqüência, a probabilidade de atendimento das demandas. O não atendimento das demandas pode gerar parada nas linhas de montagem no restante da cadeia de suprimento, com multas e penalidades altas. • Efeito dois (impacto na qualidade): Outro aspecto importante a ser levado em consideração é a maior probabilidade de chegar uma peça defeituosa no cliente no início da produção. Isto ocorre porque a quantidade de peças defeituosas produzidas logo apos a preparação é grande. Isto aumenta não só o refugo, os custos da não qualidade e a insatisfação do cliente, como também o risco de um processo de recall. Vale salientar que estes possuem custos tão elevados que chegam a inviabilizar o negócio, podendo gerar um colapso na cadeia de suprimentos. 2.2. Classificação Com base no problema descrito é possível observar que estamos diante de um problema híbrido. Isto é, um problema CSLP onde é permitida a produção de quantas peças por período forem necessárias na mesma máquina respeitando-se a restrição de capacidade. Observando a notação de seis campos adotada por SALOMON (1991) para o DLSP temos: • Layout de linha de produção – Paralela (P) pois as máquinas estão configuradas em paralelo não uniformes, as taxas de produção variam de uma a outra. • Número de máquinas – Inteiro (*) irá depender da instância tratada. • Número de produtos – Inteiro (*) irá depender da instância tratada. • Custo de preparação – Independente da seqüência (SI). Porém neste caso em função da precedência o custo da preparação pode ser zero. Programa de Pós Graduação em Engenharia de Produção – UFMG - 27 - • Custo de produção – Variável (G) o custo de produção pode variar com o tempo em função das variações dos custos dos insumos. • Tempo de preparação – Independente da seqüência (SI). Da mesma forma que o custo neste caso particular pode ser zero em função da precedência. Desta forma podemos classificar este problema como um CSLP hibrido P/*/*/SD/G/SD. Onde os asteriscos denotam os números de máquinas e produtos que vão depender de cada instância abordada. 2.3. Notação Para a modelagem de um conjunto de P peças, em M máquinas em T períodos utilizamos os seguintes índices: p índice de peça, p = 1, 2, ..., P m índice de máquina, m = 1, 2, ..., M t índice de período, t = 1, 2, ..., T Os parâmetros utilizados foram: pma horas para produzir uma unidade da peça p na máquina m (inverso da produção horária da peça p na máquina m) 1 ptd demanda mínima da peça p no período t 2 ptd demanda máxima da peça p no período t mtw capacidade em horas da máquina m no período t pte custo do estoque de uma peça p no período t Programa de Pós Graduação em Engenharia de Produção – UFMG - 28 - ptρ margem de lucro da peça p no período t pmb tempo de preparação da peça p na máquina m tq disponibilidade da equipe para execução de preparação no período t pmc custo de preparação da peça p na máquina m pf quantidade de ferramentas disponíveis para produção da peça p 0ps estoque inicial da peça p Sendo as seguintes variáveis: ptmx quantidade a produzir da peça p no período t na máquina m pts estoque da peça p ao final do período t ptd demanda efetivamente atendida da peça p no período t 1 se existe produção da peça p no período t na máquina m =ptmδ 0 se não 1 se p for a última peça a ser produzida no período t na máquina m e continuar a ser produzida no período t + 1 na máquina m =ptmθ 0 se não Para tratar o problema da rampa de início de produção vamos considerar a perda de produção relativa ao período de início da produção como tempo a ser acrescido na preparação. Programa de Pós Graduação em Engenharia de Produção – UFMG - 29 - Para isto consideramos os seguintes fatores: • Tempo para entrada em ritmo = y hrs • Tempo de preparação real = x hrs • Quantidade de peças produzidas até entrada em ritmo = z pçs • Ritmo de produção = q pçs/hr • Período relativo à perda de produção pelo ramp up = z / q • Tempo de produção perdido no ramp up = y – ( z / q ) • Tempo de preparação com início de produção = x + [ y – ( z / q ) ] = x’ hrs Desta forma o tempo de preparação a ser utilizado no modelo considerando a perda produtiva no início de produção (ramp up) passa a ser x’. A consideração deste fator não alterará o modelo, somente fará um incremento no tempo de preparação a ser modelado. A Figura 9 abaixo permite uma melhor visualização desta formulação. Evolução da produção no tempo [pç/hr] 0 5 10 15 20 25 30 35 40 0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40 Horas corridas desde o inínio do set-up [hr] P ro d u ç ã o h o rá ri a [ p ç /h r] REGIME Tempo de set-up = x Tempo para entrada em ritmo = y Ritmo = q Tempo de set-ut com ramp-up = x' Figura 9: Demonstração da modelagem da rampa de início de produção 2.4. Formulação A metodologia adotada para formulação foi partir da modelagem tradicional da literatura onde ocorre preparação em todo período em que há produção, e em seguida desenvolver q Tempo para entrada em ritmo = y q Programa de Pós Graduação em Engenharia de Produção – UFMG - 30 - soluções para adaptação deste modelo ao problema real. Para isto foram preparados três modelos mostrados a seguir. O primeiro modelo não considera o fator da precedência. MODELO 1 – Multi-máquina, multi-ítem, capacitado, com demanda variável e preparação Função objetivo ∑∑ ∑ = = =       −− T t P p M m pmptmptptptpt csedMax 1 1 1 δρ (1) Sujeito a, 1 ptpt dd ≥ para p = 1, ... , P e t = 1, ... , T (2) 2 ptpt dd ≤ para p = 1, ... , P e t = 1, ... , T (3) ptpt M m m pttp dsxs =−+∑ = − 1 1, para p = 1, ... , P e t = 1, ... , T (4) ( ) mt P p pmptm m ptpm wbxa ≤+∑ =1 δ para m = 1, ... , M e t = 1, ... , T (5) 0≥− ptmptmp xB δ para m = 1, ... , M , t = 1, ... , T , p = 1, ... , P (6) ∑ = ≤ M m pptm f 1 δ para t = 1, ... , T , p = 1, ... , P (7) ∑∑ = = ≤ P p t M m ptmpm qb 1 1 δ para t = 1, ... , T (8) m ptx , pt s , pt d Ν∈ (9) Programa de Pós Graduação em Engenharia de Produção – UFMG - 31 - { }1,0∈ptmδ (10) Nesta formulação temos a função objetivo para maximizar a margem de cada peça multiplicada pelo volume entregue no período t subtraído do custo de estoque e preparação no período. As restrições (2) e (3) tratam as demandas inferior e superior a serem entregues de cada peça p no período t. A equação (4) garante o equilíbrio de massa onde o volume entregue tem que ser igual ao estoque inicial mais o volume produzido menos o estoque final. A equação (5) é a de capacidade que garante que a disponibilidade de máquina será respeitada levando em consideração as perdas por preparação. A restrição (6) é responsável por fazer a variável ptmδ = 1 se existir produção da peça p no tempo t na máquina m, o parâmetro auxiliar B é um número extremamente grande dado por: ∑ = = T t ptp dB 1 2 A restrição (7) é a que trata a quantidade de ferramentas disponíveis para produção. A (8) limita a capacidade de execução de preparação. E as restrições (9) e (10) são as que determinam os domínios das variáveis. Após a modelagem e teste experimental deste primeiro modelo, foram desenvolvidas as soluções para garantir a condição de precedência. As restrições acrescidas são apresentadas no modelo 2. MODELO 2 – Multi-máquina, multi-ítem, capacitado, com demanda variável e preparação com ocorrência de precedência Este problema é um ponto de suma importância nesta modelagem porque são poucos os casos reais onde só é produzida uma peça por período na máquina. A condição de precedência deve garantir que em um regime de produção ininterrupto, 7 dias por semana 24 horas por dia, se permanecer a produção de uma peça em uma máquina na passagem de um período para outro não é necessário preparação. Desta forma o modelo deve contabilizar uma economia de custo e tempo de preparação. Programa de Pós Graduação em Engenharia de Produção – UFMG - 32 - Função objetivo ( )∑∑ ∑ = = = −       −−− T t P p M m mtpptmpmptptptpt csedMax 1 1 1 ,1,θδρ (1) Sujeito a, 1 ptpt dd ≥ para p = 1, ... , P e t = 1, ... , T (2) 2 ptpt dd ≤ para p = 1, ... , P e t = 1, ... , T (3) ptpt M m m pttp dsxs =−+∑ = − 1 1, para p = 1, ... , P e t = 1, ... , T (4) ( )[ ] mt P p mtpptmpt m ptpm wbxa ≤−+∑ = − 1 ,1,θδ para m = 1, ... , M e t = 1, ... , T (5) 0≥− ptmptmp xB δ para m = 1, ... , M , t = 1, ... , T , p = 1, ... , P (6) ( )∑∑ = = − ≤− P p t M m mtpptmpm qb 1 1 ,1,θδ para t = 1, ... , T (7) 0,, ≥− mtpptm θδ para m = 1, ... , M , t = 1, ... , T , p = 1, ... , P (8) 0,1, ≥− − mtpptm θδ para m = 1, ... , M , t = 1, ... , T , p = 1, ... , P (9) 1 1 ≤∑ = P p ptmθ para m = 1, ... , M e t = 1, ... , T (10) ∑ = ≤ M m pptm f 1 δ para t = 1, ... , T , p = 1, ... , P (11) pts , ptd , ptmx Ν∈ para m = 1, ... , M , t = 1, ... , T , p = 1, ... , P (12) Programa de Pós Graduação em Engenharia de Produção – UFMG - 33 - { }1,0, ∈ptmptm θδ Neste modelo incluímos o termo da condição de precedência estabelecida pela variável ptmθ . Desta forma, se a mesma peça for produzida na mesma máquina no período seguinte não existe perda de tempo e custo de preparação. A equação (8) juntamente com a (9) garante que ptmθ só pode assumir o valor 1 se o produto p for alocado na máquina m em períodos consecutivos, ou seja se ptmδ e mtp ,1, +δ forem iguais a 1. A equação (9) evita que o termo )( ptmptm θδ − gere disponibilidade nas equações em (5) e (7) quando uma peça p produzida no período t-1 deixar de ser produzida na máquina m no período t, além de evitar a geração de resultado operacional na função objetivo. A equação (10) garante que somente ocorra precedência de uma peça por período e máquina. MODELO 3 – Multi-máquina, multi-ítem, capacitado, com demanda variável e preparação com ocorrência de precedência produzindo mais de uma peça por máquina e período Para garantir a consistência do modelo caso haja produção de mais de uma peça na mesma máquina em períodos consecutivos, consideramos a restrição abaixo. 3 1 ,1, ≤+++ ∑ ≠= − ptm P pjj jtm ptmmtp P θ δ δθ para m = 1, ... , M , t = 1, ... , T , p = 1, ... , P Pela interpretação da variável ptmθ , fixada uma mesma máquina m e peça p, se ocorrer precedência no período t ( 1=ptmθ ) então p é o primeiro produto a ser produzido no período consecutivo na mesma máquina. Isto implica que, para a mesma peça p e máquina m, se mpt 1+θ também for igual a 1 então p deve ser o único produto produzido em m em t+1. Programa de Pós Graduação em Engenharia de Produção – UFMG - 34 - O termo P P pjj jtm∑ ≠=1 δ garante que se ptmθ e mtp ,1, −θ forem ambas 1 o único produto a ser produzido no tempo t na máquina m seja p, pois neste caso este termo vale zero e 1=ptmδ . Se ocorrer produção de outro produto este termo forçará ptmθ a zero, impedindo a condição de precedência para o período posterior t+1. Com base no exposto o modelo final ficou da seguinte forma: Função objetivo ( )∑∑ ∑ = = = −       −−− T t P p M m mtpptmpmptptptpt csedMax 1 1 1 ,1,θδρ (1) Sujeito a, 1 ptpt dd ≥ para p = 1, ... , P e t = 1, ... , T (2) 2 ptpt dd ≤ para p = 1, ... , P e t = 1, ... , T (3) 0 1 1, =−−+∑ = − ptpt M m m pttp dsxs para p = 1, ... , P e t = 1, ... , T (4) ( ) mt P p mtpptmpt P p m ptpm wbxa ≤−+∑∑ = − = 1 ,1, 1 θδ para m = 1, ... , M e t = 1, ... , T (5) ( )∑∑ = = − ≤− P p t M m mtpptmpm qb 1 1 ,1,θδ para t = 1, ... , T (6) 0≥− ptmptmp xB δ para m = 1, ... , M , t = 1, ... , T , p = 1, ... , P (7) 0,, ≥− mtpptm θδ para m = 1, ... , M , t = 1, ... , T , p = 1, ... , P (8) Programa de Pós Graduação em Engenharia de Produção – UFMG - 35 - 0,1,,, ≥− − mtpmtp θδ para m = 1, ... , M , t = 1, ... , T , p = 1, ... , P (9) 1 1 ≤∑ = P p ptmθ para m = 1, ... , M e t = 1, ... , T (10) 3 1 ,1, ≤+++ ∑ ≠= − ptm P pjj jtm ptmmtp P θ δ δθ para m = 1, ... , M , t = 1, ... , T , p = 1, ... , P (11) ∑ = ≤ M m pptm f 1 δ para t = 1, ... , T , p = 1, ... , P (12) pts , ptd , ptmx Ν∈ { }1,0, ∈ptmptm θδ para m = 1, ... , M , t = 1, ... , T , p = 1, ... , P (13) 2.5. Observações gerais É importante observar alguns pontos relativos ao modelo proposto: I. A demanda tratada é variável entre dois patamares, um máximo e um mínimo. Isto é comum em sistemas onde existe uma demanda mínima contratada e uma demanda máxima potencial. II. Na função objetivo tratamos maximização de resultados ao contrário dos modelos clássicos de redução de custos. Isto foi feito com base em uma ótica em que a demanda efetivamente atendida pode variar desde que melhore o resultado e respeite as condições contratuais com os clientes. III. Para consideração da rampa de aproveitamento o valor do tempo de preparação utilizado na modelagem deve ser substituído pelo valor calculado em função da rampa, conforme mostrado anteriormente. Programa de Pós Graduação em Engenharia de Produção – UFMG - 36 - 2.6. Avaliação preliminar dos resultados Para permitir uma avaliação numérica dos modelos mostrados neste capítulo foram formulados dois problemas teste que visam demonstrar o comportamento de cada um. 2.6.1. Apresentação dos problemas teste Para esta avaliação foram elaborados problemas de pequeno porte que permitam uma noção intuitiva dos resultados. Estes possuem complexidade compatível com os problemas mais difíceis em função das definições do tamanho dos conjuntos e situações de produção apresentados a seguir. O conjunto de períodos mínimo para se observar o comportamento da situação de precedência é de três períodos. Desta forma podemos observar o efeito da condição de partida no período 1 e a condição de precedência possível entre os períodos 2 e 3. Para uma boa visualização do fenômeno da precedência e da alocação da produção nos recursos disponíveis foi considerado um mínimo de 3 peças a ser produzido por máquina em cada período. As situações de produção usadas foram: Problema A: Uma máquina, três períodos e três peças com o estoque inicial de uma das peças suficiente para atender à demanda máxima no primeiro período. O objetivo deste teste é apresentar a efetividade da restrição que determina a condição de precedência. Problema B: Duas máquinas, três períodos e três peças com estoque inicial zero. O objetivo deste é confirmar resultados incoerentes observados quando não aplicada a restrição de precedência. A condição de partida para o problema A será a peça 1 montada na máquina 1. Para o problema B teremos a peça 1 montada na máquina 1 e peça 2 montada na máquina 2. Como regra geral adotaremos também o custo de preparação da peça 1 superior ao das demais. Programa de Pós Graduação em Engenharia de Produção – UFMG - 37 - 2.6.2. Avaliação qualitativa Problema A Os resultados encontrados para o problema A são apresentados nos gráficos de Gantt. Problema A Modelo 1 Maquina 1 P1 P3 P1 P2 P3 P1 P2 P3 1 2 3 Periodo Modelo 2 Maquina 1 P1 P3 P1 P2 P3 P1 P2 P3 1 2 3 Periodo Modelo 3 Maquina 1 P1 P3 P3 P2 P1 P1 P2 P3 1 2 3 Periodo Legenda: Produção sem setup P1 Peça 1 Produção com setup P2 Peça 2 Disponibilidade P3 Peça 3 Como pode-se observar, no modelo 1 em toda produção ocorreu preparação. No modelo 2 verificamos que não ocorreu preparação no início da produção da peça 1 no primeiro período. No entanto observamos também que o modelo não indica preparação para a peça 1 no segundo e terceiro períodos uma vez que 111θ e 121θ foram ambos iguais a um. Isto está errado pois não há precedência uma vez que a peça 3 deve ser produzida após a peça 1 no Programa de Pós Graduação em Engenharia de Produção – UFMG - 38 - período anterior. Devido ao custo de preparação da peça 1 maior que das demais o modelo 2 faz com que 11 =tmθ para todos os períodos. Já o modelo 3 indica o aproveitamento da condição de partida da peça 1 no período 1, a precedência da peça 3 entre os períodos 1 e 2 ( 1311 =θ ) e da peça 1 nos períodos 2 e 3 ( 1121 =θ ). O conjunto de máquinas mínimo necessário para avaliação do comportamento de alocação de produção nos recursos é de duas máquinas. Com este permite-se a visualização da distribuição da produção em mais de uma máquina onde o modelo deve encontrar a melhor opção. Problema B Os resultados encontrados para o problema B foram: Modelo 1 Maquina 2 P1 P2 P1 P2 P3 P1 P2 P3 1 P4 P4 P4 1 2 3 Periodo Modelo 2 Maquina 2 P2 P3 P3 P4 P3 P4 1 P1 P4 P1 P2 P1 P2 1 2 3 Periodo Modelo 3 Maquina 2 P2 P2 P4 P1 P1 P2 1 P1 P4 P3 P3 P3 P4 1 2 3 Periodo Legenda: Produção sem setup P1 Peça 1 Produção com setup P2 Peça 2 Disponibilidade P3 Peça 3 P4 Peça 4 Programa de Pós Graduação em Engenharia de Produção – UFMG - 39 - Assim como no problema A observamos o modelo 1 contando preparação em todas as produções. O Modelo 2 permanece com resultados incoerentes no que diz respeito à precedência. E o modelo 3 apresenta a solução onde as precedências são apropriadamente utilizadas. 2.6.3. Avaliação quantitativa Os resultados obtidos em cada resolução são apresentados na tabela abaixo: Resultado Problema A Problema B Modelo 1 360.907,00R$ 1.026.256,00R$ Modelo 2 361.987,00R$ 1.029.167,00R$ Modelo 3 361.866,00R$ 1.029.018,00R$ Para uma avaliação gráfica dos resultados consideremos os desvios em relação à média apresentados nos gráficos abaixo: -0,20% -0,15% -0,10% -0,05% 0,00% 0,05% 0,10% 0,15% D e s v io ( % ) Problema A Problema B Desvio em relação à média dos resultados Modelo 1 Modelo 2 Modelo 3 Como pode-se observar, nos dois problemas o resultado dos modelos apresentou comportamento similar. Em ambos os problemas o modelo 1 apresentou resultado operacional inferior à média. O modelo 2 apresentou resultado otimista onde verificamos maior benefício. E o modelo 3 apresentou um resultado próximo ao do modelo 2 porém um pouco menor. O fato do modelo 1 ter apresentado o pior resultado dos três modelos era esperado uma vez que este não utiliza o benefício da precedência para economia nos custos de preparação. Programa de Pós Graduação em Engenharia de Produção – UFMG - 40 - O resultado obtido no modelo 2 também era esperado pois este utilizou dos menores custos de preparação possíveis para abatimento no resultado operacional. No problema A o modelo indicou precedência desnecessária da peça 1 no período 1 uma vez que a condição de partida era peça 1 montada na máquina 1. Na tabela abaixo mostramos o custo total de preparação em cada caso. Custo de Setup Problema A Problema B Modelo 1 3.715,00R$ 4.783,00R$ Modelo 2 2.095,00R$ 2.447,00R$ Modelo 3 2.216,00R$ 2.596,00R$ Da mesma forma como exibido anteriormente mostramos abaixo o gráfico dos desvios percentuais dos custos totais de preparação em relação à média. -40% -20% 0% 20% 40% 60% D e s v io ( % ) Problema A Problema B Desvio em relação à média dos custos totais de setup Modelo 1 Modelo 2 Modelo 3 Podemos observar pelo perfil dos dois gráficos que a diferença entre os resultados encontrados esta fortemente associada (inversamente proporcional) ao custo total de preparação presente nos dois problemas estudados. Um comentário importante é da influencia da condição de precedência na viabilidade e nas funções objetivo dos modelos quando efetivamente implementados no chão de fábrica. O modelo 3 apresenta uma solução viável para implementação no chão de fábrica com a função objetivo calculada de uma forma correta. Já o modelo 1 apresenta uma solução viável em que o valor da função objetivo é onerado com setup desnecessário. Por outro lado o modelo 2 apresenta uma solução que não necessariamente é viável para implementação no Programa de Pós Graduação em Engenharia de Produção – UFMG - 41 - chão de fábrica, pois os tempos de que não foram utilizados para setup podem ter sido utilizado para produção. Alem disto, caso a solução do modelo 3 seja viável, a função objetivo não é calculada corretamente devido a não consideração do setup necessário. Programa de Pós Graduação em Engenharia de Produção – UFMG - 42 - Capítulo 3 – Avaliação de desempenho Este capítulo apresenta o desempenho do modelo resolvendo dois tipos de problemas teste: Problemas reais encontradas em fundições, e problemas adaptados de instâncias obtidas na literatura. O modelo foi implementado no software GLPK 4.0 instalado em um PC com sistema operacional Windows XP e processador Intel Celeron M de 1.4GHz com 128 MB RAM. 3.1. Desempenho do modelo em casos reais Para teste, foram elaborados instâncias de três portes de acordo com as características das indústrias do setor de fundição. Estes são classificados de acordo com o número de variáveis da seguinte forma: Tamanho do Problema Número de variáveis Pequeno Até 300 Médio De 301 a 3.500 Grande De 3.500 até 13.000 Os problemas de pequeno porte consideram instalações com até 5 máquinas produzindo 4 peças diferentes onde se analisa o melhor resultado em um horizonte de 4 períodos. Apesar de ser considerado problema de pequeno porte, ele se aplica a grandes empresas. Como exemplo temos unidades fabris de injeção de blocos de motor em alumínio com até 25Kg onde freqüentemente existe esta configuração (máquina / peça) para atendimento de uma demanda regional. Para os problemas de médio porte foram consideradas instalações com até 10 máquinas produzindo 13 peças diferentes em uma análise sobre 7 períodos de tempo. Este tamanho de Programa de Pós Graduação em Engenharia de Produção – UFMG - 43 - problema abrange a maioria das indústrias de injeção de alumínio que atendem o mercado global de peças automobilísticas entre 3 e 15 Kg. Como problemas de grande porte, foram consideradas instalações com até 20 máquinas produzindo 22 peças diferentes em até 9 períodos de tempo. Este porte de problema é freqüente em indústrias de injeção de alumínio de peças de pequeno porte (até 3 Kg) freqüentes na região de São Paulo e sul do Brasil. Para indústria automobilística poucas plantas industriais se enquadram neste porte operando no território nacional. Os parâmetros utilizados em todos os problemas teste são parâmetros médios reais encontrados nas indústrias de injeção de alumínio que atendem o mercado automobilístico. As margens de contribuição das peças foram baseadas em valores orientativos considerando a cotação LME do alumínio ligado “high grade” (bolsa de metais de Londres) e dólar do primeiro semestre de 2005 e custos de mão de obra encontrados na região metropolitana de Belo Horizonte - MG. O custo de estocagem foi obtido com a estimativa do capital imobilizado somado a uma taxa de manuseio e estocagem estimada da ordem de 2% ao mês do valor da peça. Os tempos de preparação se baseiam em tempos reais para troca de ferramentas entre 5 e 25 toneladas com apoio de pórtico em injetoras horizontais, que estão entre 4 e 20 horas com dois funcionários. As curvas de aquecimento foram obtidas em um levantamento estatístico de até 20 inícios de produção de peças entre 5 e 18 Kg sem controle automático de temperatura a óleo. Foram observados tempos para entrada em regime de 10 horas a 2,5 dias variando em função da geometria em peso da peça. O tempo de ciclo utilizado foi com base em valores reais médios em máquinas automáticas e semi-automáticas ficando entre 45 e 150 segundos. As demandas mínimas foram estipuladas com base em uma saturação de 75% da capacidade. E as demandas máximas foram simuladas com base em projeções feitas sobre a capacidade considerando uma variação de até 60% sobre as demandas mínimas. A avaliação dos resultados foi feita com base no Gap (distancia relativa) entre o ótimo obtido pela resolução em programação linear (LP) e o resultado encontrado pelo modelo em programação inteira mista (MIP). Programa de Pós Graduação em Engenharia de Produção – UFMG - 44 - %100 )( )()( (%) × − = IPresultadoM IPresultadoMPresultadoL Gap Além deste são apresentados também o tempo de resolução e o resultado da relaxação linear. Os resultados são exibidos abaixo onde P indica o número de peças, M a quantidade de máquinas e T o número de períodos. # P M T Num Var Relaxação linear (LP) Resultado do uper bound Resultado MIP Gap (%) Tempo (S) PROBLEMAS PEQUENOS 1 2 3 3 66 2,39E+05 2,36E+05 2,33E+05 0 1 2 3 3 4 132 4,89E+05 4,75E+05 4,72E+05 0 2 3 4 3 4 176 7,46E+05 7,44E+05 7,42E+05 0 15 4 4 5 4 272 7,52E+05 7,50E+05 7,42E+05 0 58 PROBLEMAS MÉDIOS 5 6 7 7 966 1,88E+06 1,84E+06 1,83E+06 0,7 162 6 9 7 7 1449 2,83E+06 2,81E+06 2,79E+06 0,5 194 7 13 7 7 2093 4,12E+06 4,09E+06 4,02E+06 1,9 203 8 13 10 7 2912 4,17E+06 4,09E+06 3,99E+06 2,7 506 PROBLEMAS GRANDES 9 13 13 7 3731 4,15E+06 4,10E+06 4,07E+06 0,6 439 10 15 13 7 4305 4,83E+06 4,76E+06 4,69E+06 1,4 487 11 16 16 9 7.200 6,68E+06 6,60E+06 6,52E+06 1,3 728 12 16 20 9 8.928 6,65E+06 6,60E+06 6,57E+06 0,5 1350 13 17 20 9 9.486 7,12E+06 7,06E+06 6,99E+06 1 1266 14 18 20 9 10.044 7,48E+06 7,40E+06 7,37E+06 0,5 934 15 20 20 9 11.160 8,28E+06 8,25E+06 8,20E+06 0,6 1920 16 22 20 9 12.276 9,19E+06 9,07E+06 8,91E+06 1,8 3600 Tabela 2: Desempenho do modelo na resolução de problemas reais Os resultados obtidos mostram grande eficiência do modelo nos portes de problema abordados. Para problemas médios e grandes, apesar de interrompida a resolução, um bom resultado foi obtido em pouco tempo. Isto é muito importante pois permite rápida reação às ocorrências no chão de fábrica como alterações no plano de produção em função de quebra de máquina. Outra observação a ser feita se refere ao desempenho ao se utilizar a relaxação linear. Com esta os problemas foram resolvidos com bem menos tempo, por exemplo o problema 16 (maior entre os abordados) foi resolvido em 59 segundos. A diferença entre o resultado Programa de Pós Graduação em Engenharia de Produção – UFMG - 45 - obtido com a relaxação e o em programação inteira mista foi inferior a 2,5% para todos os casos abordados acima. 3.2. Desempenho do modelo em problemas encontrados na literatura Para este teste foram recuperados os problemas “Big Bucket” utilizados por TRIGEIRO et al. (1989) da página http://www.core.ucl.ac.be:16080/wolsey/lotsizel.htm. Os problemas “Big Bucket” são caracterizados pela produção de mais de um produto na mesma máquina dentro do mesmo período de tempo. Estas instâncias tratam problemas uma única máquina, com 12 a 30 períodos e 6 a 24 produtos. São parâmetros a demanda, os tempos de preparação e de produção, os custos de preparação, estocagem e produção. Para este teste foram efetuadas três baterias utilizando as 6 instâncias indicadas por Wolsey como representativas. A primeira bateria consiste em testar o modelo nestas instâncias adaptadas com o mínimo de modificação. A segunda bateria resolve os problemas acrescentados de mais máquinas somente replicando os parâmetros necessários ajustados. E a terceira bateria trata os problemas da segunda porém impondo variação nos parâmetros. As modificações feitas nas instâncias para a primeira bateria de testes foram a utilização da demanda máxima igual à demanda mínima, a margem da peça foi considerada 5 vezes o custo de estoque, estoque inicial das peças igual a zero, disponibilidade de preparação no período igual à capacidade de máquina, condição de partida é máquina sem ferramenta e quantidade de ferramenta por peça igual à quantidade de máquinas. As instâncias utilizadas para a segunda bateria de testes foram as mesmas da primeira bateria com a adição de mais duas máquinas. Com objetivo de garantir o mesmo grau de dificuldade foram triplicadas as demandas, a quantidade de ferramentas e a capacidade de preparação. Na terceira bateria de testes foram utilizadas as instâncias da segunda bateria alterando a demanda máxima de 20% , as capacidades de até 30% e o tempo de ciclo e custo de preparação de ± 20%. Programa de Pós Graduação em Engenharia de Produção – UFMG - 46 - Durante a execução destes testes o modelo gastou 3 horas e 45 minutos para chegar a 48,9% do ótimo no problema com 6 peças, 1 máquina e 15 períodos. Após este prazo o software entrou em um “looping” de instabilidade numérica. Para as demais instâncias após 3 a 5 horas de execussão o software entrou em “looping” sem encontrar solução viável em programação inteira mista. Este fato gerou a motivação para o desenvolvimento de uma Heurística apresentada no próximo capítulo. Dado o regime de variação da demanda do caso estudado o número de períodos original dos problemas encontrados na bibliografia foi reduzido em cinco vezes, desta forma permanecendo com um horizonte de três a seis semanas. Para não gerar incompatibilidade nos valores as demandas e capacidades também foram aumentadas na mesma razão. Os resultados obtidos são exibidos na tabela abaixo. # P M T Num Var Resultado do upper bound Resultado MIP Gap (%) Tempo (S) 1ª BATERIA g30n' 6 1 3 90 1,11E+14 1,11E+14 0 0,2 g53n' 12 1 3 180 1,65E+14 1,65E+14 0 88 g57n' 24 1 3 360 4,56E+14 4,25E+14 7,7 145 g62n' 6 1 6 180 2,42E+14 2,42E+14 0 25 g69n' 12 1 6 360 3,86E+14 3,55E+14 8,8 48 g72n' 24 1 6 720 8,55E+14 7,78E+14 9,9 10 2ª BATERIA g30n'' 6 3 3 198 3,60E+14 3,54E+14 1,8 28 g53n'' 12 3 3 396 5,58E+14 5,38E+14 3,7 37 g57n'' 24 3 3 792 1,39E+15 1,35E+15 2,9 29 g62n'' 6 3 6 396 7,65E+14 7,54E+14 1,5 79 g69n'' 12 3 6 792 1,18E+15 1,13E+15 3,7 12 g72n'' 24 3 6 1584 2,59E+15 - - 2 3ª BATERIA g30n''' 6 3 3 198 4,32E+14 4,26E+14 1,4 23 g53n''' 12 3 3 396 6,69E+14 6,51E+14 2,8 44 g57n''' 24 3 3 792 1,66E+15 1,62E+15 2,5 70 g62n''' 6 3 6 396 9,17E+14 9,07E+14 1,1 43 g69n''' 12 3 6 792 1,41E+15 1,37E+15 3,2 8 g72n''' 24 3 6 1584 3,10E+15 3,00E+15 3,4 41 Tabela 3: Desempenho do modelo na resolução de problemas da literatura O software utilizado não foi capaz de resolver a instância g72n”. Com 2,1 segundos ele retornou uma mensagem de erro indicando instabilidade e problemas numéricos na resolução da matriz. Apesar disto bons resultados foram obtidos em pouco tempo computacional. Programa de Pós Graduação em Engenharia de Produção – UFMG - 47 - Capítulo 4 – Proposta de heurística construtiva Neste capítulo é apresentada uma heurística para construção de uma solução viável que utiliza a capacidade remanescente para melhoria do resultado operacional. A motivação para adoção deste segundo método de resolução é a aplicação em problemas com grande quantidade de períodos. A explicação da metodologia é feita inicialmente indicando as respectivas linhas relativas ao pseudo-código apresentado em seguida. 4.1. Elaboração da heurística A heurística construtiva foi desenvolvida para trabalhar em duas etapas. A primeira busca uma solução viável e a segunda busca o atendimento das demandas máximas. Ambas as etapas trabalham considerando a possibilidade de poupar preparação se houver precedência (linhas 12 a 16). A primeira etapa da heurística inicialmente utiliza qualquer estoque disponível para o atendimento da demanda (linha 9). Caso necessário, a produção é alocada na máquina (linhas 19 a 25). Se a máquina não conseguir suprir a demanda ela produz até o limite de sua capacidade e a demanda remanescente é gerada (linhas 26 a 33). Se a capacidade remanescente de uma outra máquina for suficiente para atender a demanda remanescente o preparação é feito e somente esta máquina produz até o atendimento da demanda (linhas 37 a 52). Caso contrário a demanda remanescente é dividida para produção em mais de uma máquina (linhas 53 a 69). Desta forma, a mesma peça pode ser produzida em mais de uma máquina no mesmo período para garantir o atendimento da demanda sem extrapolar o limite de capacidade individual de cada máquina. A segunda etapa inicialmente utiliza a capacidade remanescente para produção da última peça, gerando estoque para o período consecutivo (linhas 76 a 84). Após percorrer todas as Programa de Pós Graduação em Engenharia de Produção – UFMG - 48 - máquinas e períodos a heurística vai do último ao primeiro período abatendo o estoque final após o atendimento das demandas máximas da quantidade produzida no período antecessor para zerar o estoque final (linhas 87 a 127). 4.2. Pseudo-código Abaixo é mostrado o pseudo-código elaborado para resolução desta heurística. Foram utilizados os índices, variáveis e parâmetros apresentados no Capítulo 2 e foram acrescidas as variáveis auxiliares i, y, h e f. 1 /* Primeira Etapa – construção de uma solução viável */ 2 3 Para t=1 até T faça 4 /* Primeira passada em P (consumindo estoque e alocando produção em única máquina) */ 5 Para m=1 até M faça 6 mtm ww ← 7 Fim para 8 Para p=1 até P faça 9 1, 1 −−← tpptpt sdd 10 0←h 11 1←m 12 0←pts 13 Enquanto ( Mm ≤ ) e ( 0=h ) então 14 Se ( 1,1, =− mtpθ ) então 15 mh ← 16 Senão 17 1+← mm 18 Fim enquanto 19 Se ( 0>ptd ) e ( 0>h ) então 20 Se ( hphpt wad ≤ ) então 21 ptpth dx ← 22 phpthhh axww −← Programa de Pós Graduação em Engenharia de Produção – UFMG - 49 - 23 0←ptd 24 1←pthθ 25 Fim-se 26 Senão 27 phhptpt awdd /−← 28 phhpth awx /← 29 0←hw 30 1←pthθ 31 Fim senão 32 Fim se 33 Fim para 34 35 /* Segunda passada em P (Fracionamento da produção em mais máquinas) */ 36 37 Para p=1 até P faça 38 Se ( 0>ptd ) então 39 ∞←f 40 0←h 41 Para m=1 até M faça 42 Se ( mpmpmpt wbad ≤+ ) então 43 Se ( { } fbadw pmpmptm <+− ) então 44 { }pmpmptm badwf +−← 45 mh ← 46 ptptm dx ← 47 Fim se 48 Fim se 49 Senão 50 [ ] pm pmm m a bw y − ← 51 Fim senão 52 Fim para Programa de Pós Graduação em Engenharia de Produção – UFMG - 50 - 53 Se ( 0>h ) então 54 [ ]phphpthh badww +−← 55 ptpth dx ← 56 0←ptd 57 1←pthθ 58 Fim se 59 Senão 60 Ordena my em ordem crescente 61 1←i 62 Enquanto ( 0>ptd ) e ( Mi ≤ ) faça 63 Aloca o que der da demanda 64 Se ( 0>ptd ) então 65 1+← ii 66 Fim se 67 Fim enquanto 68 Fim senão 69 Fim se 70 Se ( 0>ptd ) então 71 Retorna /* Não encontrada solução viável*/ 72 Fim se 73 Fim para 74 75 /* Segunda Etapa – Gerando estoque e melhorando a solução */ 76 /* Terceira passada em m (produzindo até esgotar a capacidade remanescente) */ 77 Para m=1 até M faça 78 Para p=1 até P faça 79 Se 0>mtw e 1=ptmθ então 80 pm mt ptm a w x ← 81 ptmptpt xss +← 82 Fim se 83 Fim Para Programa de Pós Graduação em Engenharia de Produção – UFMG - 51 - 84 Fim para 85 Fim para 86 /* Passada de retorno (abatendo o estoque final após o atendimento das demandas máximas) */ 87 Para t=T faça 88 Para p=1 até P faça 89 Se 12 ptptpt dds −> então 90 )( 12 ptptptpt ddss −−← 91 2 ptpt dd ← 92 Se ptptm sx > faça 93 ptptmptm sxx −← 94 0←pts 95 Senão 96 0←ptmx 97 ptmptpt xss −← 98 Fim senão 99 Senão 100 ptptpt sdd +← 101 0←pts 102 Fim senão 103 ptpt ss ← 104 Fim para 105 Fim para 106 Para t=T-1 até 1 107 Para p=1 até P 108 Enquanto 0>pts faça 109 Para m=1 até M 110 Se )( 12 ptptpt dds −> faça 111 )( 12 ptptptpt ddss −−← 112 2 ptpt dd ← 113 Se ptptm sx > faça Programa de Pós Graduação em Engenharia de Produção – UFMG - 52 - 114 ptptmptm sxx −← 115 0←pts 116 Senão 117 0←ptmx 118 ptmptpt xss −← 119 Fim senão 120 Senão 121 ptptpt sdd +← 122 0←pts 123 Fim senão 124 Fim para 125 Fim enquanto 126 Fim para 127 Fim para Vale comentar que a heurística mostrada gera um resultado com base na seqüência lógica de construção e não com base em avaliações do resultado operacional. Alem disso, devido a complexidade combinatória do problema, a heurística pode não gerar solução viável. Programa de Pós Graduação em Engenharia de Produção – UFMG - 53 - Conclusão Pela análise do trabalho desenvolvido pode-se verificar a eficiência da modelagem numérica para suporte à tomada de decisões. Verifica-se que a programação inteira mista permitiu a consideração de todas as restrições encontradas no chão de fábrica e a obtenção de resultados confiáveis. As avaliações qualitativas efetuadas mostram que o modelo possui comportamento previsível e esperado nos problemas utilizados. Com os testes de desempenho em casos reais, pôde-se observar que o modelo funciona bem na resolução destes problemas. Para problemas menores a interrupção da execução em função do tempo pôde ser feita sem se perder em muito a qualidade da resposta. A equação (11) do modelo final é uma importante contribuição para esta classe de problemas pois permite uma condição até o momento não abordada. Para os casos onde existe produção de mais de um produto por período e existe o fator da precedência ou start-up esta equação se mostrou eficaz. Os testes nos problemas encontrados na literatura confirmam o desempenho do modelo. No entanto foi constatado que o modelo não possui bom desempenho computacional em casos onde a quantidade de períodos é superior a 6 em instâncias com mais de 2.000 variáveis. Uma vez que as indústrias abordadas possuem controle de produção discretizado em semanas, o modelo pode ser considerado eficaz porque as previsões de demanda e horizonte de planejamento não ultrapassam com confiabilidade mais de 2 meses. Com base no exposto, o modelo matemático desenvolvido se mostra capaz de gerar soluções confiáveis em tempo hábil para suporte aos planejadores de empresas que possuam realidades similares à abordada nesta dissertação. Programa de Pós Graduação em Engenharia de Produção – UFMG - 54 - A heurística construtiva indicada, apesar de implementada em caráter preliminar, pode ser de grande utilidade na obtenção de soluções viáveis. Uma primeira extensão do trabalho é o refinamento e a validação numérica da heurística. Uma segunda extensão é o desenvolvimento de uma metaheurística, tendo como base a heurística proposta. Programa de Pós Graduação em Engenharia de Produção – UFMG - 55 - Referências AGGARWAL A. E PARK J. (1993) “Improved algorithms for economic lot size problems”. Operations Research, vol 41, pag 549-571. CARVALHO V. (1998) Une proposition d’integration de la planification et l’ordonnancement de production: Application de la méthode de Benders. Université Blaise Pascal- Clermont II, França. CONSTANTINO M. e ANGRA A. (1999) “Lotsizing with backlogging and start-ups: the case of Wagner-Whitin costs”. Operations Research Letters 25, pag 81-88. DASTIDAR e NAGI (2005) “Scheduling injection molding operations with multiple resource constraints and sequence dependent setup times and costs”. Computers & Operations Research vol 32, pag 2987-3005. DREXL A. e KIMMS A. (1997) “Lotsizing and scheduling – Survey and extensions”. European Journal of Operational Research. Vol 99, pag 221-235. FLEISCHMANN, B (1990) “The discrete lotsizing and scheduling problem”. European Journal of Operational Research vol 44, pag 337-348. GOPALAKRISHNAN M., DING K., BOURJOLLY J.M. e MOHAN S. (2001) “A Tabu- search heuristic for the capacitated lot-sizing problem with set-up carryover”. Management Science, vol 47, pag. 851-863. HANSSMAN, F., (1962) Operations Research in Productions and Inventory. John Wiley & Sons. Programa de Pós Graduação em Engenharia de Produção – UFMG - 56 - HAUGEN K., OLSTAD A. e PETTERSEN B. (2005) “The profit maximizing capacitated lot-size (PCLSP) problem”. European Journal of Operational Research, vol 176, pag 165-176. HARRIS F. W. (1913) “How many parts to make at once”. Factory, The Magazine of Management, 2(10): 135-136. HAX C. e CANDEA (1984) Production and Inventory Management. Prentice-Hall. JANS R. e DEGRAEVE Z. (2005) “Meta-heuristics for dynamic lot sizing: A review and comparison of solution approaches”. European Journal of Operational Research 2005.12.008. Vol 177. 1855-1875 KARMARKAR U. (1987a) “Lot sizes, lead times and in-process inventories”. Management Science, vol 33, pag 409-418. KARMARKAR U. (1987b) “Lot sizes and sequencing delays”. Management Science, vol 33, pag 419-423. KARMARKAR U., KEKRE SHAM e KEKRE SUNDER (1986) “The dynamic lot-sizing problem with startup and reservation costs”. Operations Research, vol 35, pag 389- 398. KARMARKAR U. e SCHRAGE L. (1985) “The deterministic dynamic production cycling problem”. Operations Research, vol 33, pag 326- 345. KRAJEWIWSKI L.J. e RITZMAN L.P. (1993) Operations Management Strategy and Analysis. Addison-Wesley Publishing Company. NABIL A. e SAFIA K. (2002) “The multi-item capacitated lot-sizing problem with setup times and shortage costs”. European Journal of Operational Research. Programa de Pós Graduação em Engenharia de Produção – UFMG - 57 - POCHET, Y. (2001), Mathematical programming models and formulations for deterministic production planning problems. Computational Combinatorial Optimization, Lecture Notes in Computer Science 2241, 57–111, Springer-Verlag. SALOMON (1991) Deterministic Lot sizing Models for Production Planning - Lecture Notes in Economics and Mathematical Systems. Springer-Verlag. TAYLOR G., TAHA A e CHOWNING M. (1997) “A heuristic model for the sequence- dependent lot scheduling problem”. Production Planning & Control vol 8, pag 213- 225. TRIGEIRO W., THOMAS L e McCLAIN O. (1989) “Capacitated lot sizing with setup times”. Management Science vol 35, pag 353-366. WAGNER H.M. e WHITIN T.M. (1958) “Dynamic version of the economic lot size model”. Management Science vol 5, pag 89-96. WOLSEY A.L. (2002) “Solving multi-item lot-sizing problems with an MIP solver using classification and reformulation”. Management Science vol 48, pag 1587-1602. WOLSEY A.L. e BELVAUX G. (2001) “Modelling practical lot-sizing problems as mixed- integer programs”. Management Science, vol 47, pag 993. WOLSEY A.L., TZUR M. e ANILY S. (2005) Multi-item lot-sizing with a joint set-up cost. Core discussion paper, Center of Operations Research and Econometrics (CORE), Universite catholique de Louvain, Belgium. VANDERBERCK (1998) “Lot-sizing with start-up times”. Management Science vol 44, pag 1409-1425.