Uma heurística para um problema de designação produto-máquina

UMA HEURÍSTICA PARA UM PROBLEMA DE DESIGNAÇÃO PRODUTO-MÁQUINA Armando Zeferino Milioni

¶,§

Nelson Miguel Marino Junior Marcos Antonio Pereira

§

§

¶ §

Instituto Tecnológico de Aeronáutica (055 12 3947-5912) UniSoma – Matemática Para Produtividade (055 19 3208-0006)

Resumo: Descrevemos um caso real de aplicação de uma heurística de designação produto-máquina para diminuição do custo total de produção de uma empresa que produz fixadores para a indústria automobilística. Abstract: We describe a real case application of a product-machine assignment heuristic, designed to decrease total production cost in a company which produces fixing parts for the auto industry. Palavras-chave: Planejamento e Controle da Seqüenciamento (Scheduling).

Produção,

Designação

(Assignment),

1. INTRODUÇÃO O problema em questão foi proposto por uma empresa que produz fixadores para a indústria automobilística. A empresa conta com (números redondos) 100 prensas e produz 4.000 produtos diferentes. Mensalmente, o mercado solicita 40 produtos novos e deixa de solicitar quantia aproximadamente igual (produtos que são aposentados). Para que um produto p possa ser feito por uma determinada prensa m, há que se construir uma ferramenta que é adequada unicamente ao par (p, m). Essa ferramenta tem vida útil variável, com uma média aproximada de cerca de 6 meses. Feita a ferramenta, até a sua exaustão, o produto p será feito unicamente na máquina m. A empresa existe há muitos anos e, ao longo dos mesmos, passou por vários donos. Tais donos aumentaram sistematicamente o parque de prensas da empresa, mas fizeram-no de tal forma que o parque atual resultou bastante heterogêneo, com prensas de 118

diversas origens. Poucas partilham das mesmas especificações técnicas. Há prensas rápidas (no sentido peças/hora), mas com tempo de preparação (set-up time) mais lento que outras prensas mais lentas. E há toda sorte de situações intermediárias. Os critérios da atual designação produto-máquina não são muito claros. Há, entretanto, uma aparente tendência em escolher, dentre as prensas capazes de fazer um produto, a dita “minimamente capaz”, isto é, aquela cujas especificações técnicas excedam o mínimo possível às exigências do produto. A questão colocada era a de explorar uma metodologia mais adequada de designação produto-máquina. Menos do que atingir o ótimo (em termo de custo total de produção, que definiremos a seguir), o objetivo proposto era o de encontrar uma regra (heurística) simples, genérica, de fácil implementação e, principalmente, estável, face à renovação mensal dos produtos e a longevidade das ferramentas. 2. ESTRATÉGIA DE ABORDAGEM Diante da magnitude do problema (um problema combinatorial sabidamente complexo), optamos por iniciar com uma amostragem que, por razões práticas, contemplou 15 máquinas e os 550 produtos nelas produzidos. A estratégia de abordagem foi a seguinte: (i)

cálculo do custo da solução atual amostrada, fruto da designação feita manualmente; (ii) concepção de uma heurística de designação que respeitasse a demanda média (observada no trimestre anterior) e a freqüência de produção, relacionada ao tamanho do lote de cada produto; (iii) comparação entre os custos da solução atual e da solução concebida, em um horizonte de análise de um semestre. Apresentamos a seguir a estrutura de custos contemplada. Sejam: • m = indexador das máquinas (m = 1, 2, ..., M); • p = indexador dos produtos (p = 1, 2, ..., P); • j = indexador dos tipos de preparações (set-up) parciais (j = 1, ..., 6, i.e., foram identificados 6 tipos de preparação de máquina parciais). Definimos: • Tempo de operação da máquina m:

Op m =

Carga m Velocidade m

119

onde Cargam representa a quantidade total de produtos (em unidades) destinados à máquina m. • Tempo total de preparação (set-up) da máquina m: 6

S m = ∑ N mj s mj j =0

onde Nmj indica o número de set-ups do tipo j (j = 0 indica set-up total) na máquina m e smj é a duração (em minutos) do tempo de um set-up do tipo j na máquina m. • Custo horário da máquina m: Cm = $Homem-horam + $Máquina-horam Para os produtos temos: • dp: demanda do produto p; • cp: custo unitário do produto p; • lp: número de lotes do produto p. Dessa forma, podemos definir a função que representa o custo total da solução, considerando juros semestrais de manutenção de estoque de 7%, como: M

P

0,07c p d p

m =1

p =1

2l p

∑ C m (Opm + S m ) + ∑ 3. COLETA DE DADOS

A exaustiva fase de coleta de dados gerou informações como as ilustradas na tabela abaixo (por código de máquina): Máquina

Velocidade $Homem Disponibilidade Set-up $Máquina (peças/hora) (R$/hora) (horas/mês) (minutos) (R$/hora)

01

5.400

11,00

352

65

12,09

08

15.300

13,18

352

85

16,06

12

6.840

12,00

352

155

15,08

15

3.600

17,37

352

194

23,98

120

As disponibilidades listadas acima são teóricas. Na prática, trabalhamos com valores médios históricos, que levaram em conta as paradas para manutenção ou por outras causas. Foram também coletados dados por produto, referentes à demanda e à freqüência de produção. Finalmente, foram desenvolvidos dois algoritmos. Um deles confrontou as especificações técnicas de cada produto com as de cada máquina, gerando uma matriz binária que chamamos Matriz de Viabilidades. Cada célula (m, p) dessa matriz apresenta o número 1 ou o número 0, conforme a máquina m fosse ou não, respectivamente, capaz de produzir o produto p. O segundo algoritmo avaliou o tipo de preparação (set-up) que se dava na máquina m, para cada par de produtos possíveis de serem produzidos em m. Os seis tipos de setup tiveram seus tempos avaliados de acordo com os percentuais sobre o tempo de set-up total da máquina, resultando em: • • • • • •

tipo tipo tipo tipo tipo tipo

1 2 3 4 5 6

= = = = = =

0% do tempo de set-up total (i.e., sem set-up); 8%; 16%; 21%; 37%; 89%.

4. SOLUÇÃO E RESULTADOS Como já foi mencionado, o objetivo do problema não era, necessariamente, o de otimização. Contudo, optamos por também modelar o problema como tal, de forma a ter sempre um limitante inferior de custos como referência. A formulação matemática do problema de designação, um conhecido problema com variáveis de decisão 0-1, é simples e a omitimos aqui. Aos interessados recomenda-se a referência [1]. A solução atual, resultado da designação feita manualmente ao longo do tempo, teve seu custo total avaliado em R$ 148,1 mil. A solução ótima, supondo uma Matriz de Viabilidades plena, isto é, com o número 1 em todas as células (isto é, qualquer prensa pode produzir qualquer produto) resultou em um custo de R$ 107,2 mil, 28% inferior, portanto. A solução ótima com a Matriz de Viabilidades efetivamente levantada atingiu um custo de R$ 124,0 mil, cerca de 16% inferior ao custo da solução atual. A solução da heurística proposta (descrita resumidamente a seguir) foi de R$ 128,5 mil, 13% abaixo da atual (i.e., a heurística capturou mais de 80% da possibilidade de otimização). A solução ótima foi obtida pelo GAMS ([2]), utilizando-se a biblioteca de rotinas OSL ([3]) como solver, rodando em uma estação RISC 6000 da IBM. A heurística de alocação não pode ser completamente detalhada no presente trabalho, por compromisso de sigilo acertado entre o cliente e a empresa prestadora de serviço. Podemos dizer, todavia, que a idéia básica contempla: 121

(i)

agrupamento das máquinas de acordo com a velocidade e o tempo de preparação (set-up); (ii) agrupamento dos produtos de acordo com o tamanho do lote, e; (iii) ordenação dos produtos, em cada grupo, de acordo com sua viabilidade, isto é, com a quantidade de máquina capazes de fazê-lo.

A heurística desenvolvida explora a designação dentro dos grupos descritos em (i) e (ii), respeitando a ordenação descrita em (iii). 5. OUTROS RESULTADOS Com a heurística proposta, diversos estudos foram viabilizados. Por exemplo, o estudo das conseqüências de um investimento em redução dos tempos de set-up e em aumento nas disponibilidades reais. Sob a hipótese de que tanto um como outro melhorassem em 10%, obtivemos um custo total de R$ 119,1 mil na solução ótima (20% a menos, em relação a atual) e R$ 123,3 mil (17% a menos) na solução heurística (captura de 85% das possibilidades de otimização). Também foram viabilizados estudos de eliminação de máquinas da amostra. A eliminação de duas máquinas escolhidas estrategicamente, por exemplo, exigiu a eliminação de apenas dois produtos (que só podiam ser fabricados nas mesmas) e levou a um custo de R$ 125,6 mil (15% menos) na solução ótima e de R$ 128,3 mil (13% menos) na solução heurística. Não surpreende o fato de que, neste caso, tanto a solução ótima como a solução heurística apresentem resultados piores que os anteriores, pois está claro que a eliminação de máquinas reduz o universo de soluções viáveis. A eliminação de máquinas, entretanto, gera benefícios que não podem ser medidos diretamente pela função de custo total da produção, pois possibilita descontinuidades como o encerramento de turnos, a venda ou a remoção da máquina para outro local de interesse da fábrica etc. Um outro estudo propôs a eliminação de quatro máquinas, o que exigiu a eliminação de apenas três produtos e levou a custos de R$ 125,4 mil (15% menos) na solução ótima e de R$ 127,6 mil (14% menos) na solução heurística (captura de quase 95% das possibilidades de otimização). Seguiram-se estudos voltados à eliminação de produtos. No caso da eliminação dos 50 produtos menos rentáveis (10% da amostra), por exemplo, os custos atingidos foram de R$ 122,8 mil (redução de 17%) na solução ótima e de R$ 126,0 mil (redução de 15%) na solução heurística. Outros estudos contemplaram análise de sensibilidade quanto à Matriz de Viabilidades e aos tipos de set-up.

122

6. BIBLIOGRAFIA [1] Milioni, A. Z., N. M. Marino Jr e M. A. Pereira. Relatório Interno do Projeto de Designação Produto-Máquina, UniSoma, Campinas, SP, 1995. [2] Brooke, A., D. Kendrick e A. Meeraus. GAMS: A User’s Guide, The Scientific Press, São Francisco, EUA, 1988. [3] Optimization Subroutine Library – Guide and Reference, 3a edição, IBM, 1991.

123