BrBRCEEn0101-74382003000300002

Dimensionamento de lotes e programação do forno numa fundição automatizada de porte médio

1. Introdução O setor de fundição caracteriza-se como uma importante indústria primária que fornece bens intermediários para diversas outras, tais como, automotivas, siderúrgicas, construção, dentre outras. No Brasil o setor produziu, de janeiro a março de 2002, 445.696 toneladas e, no mesmo período de 2003, 540.015 toneladas representando um crescimento de 21,2%, gerando cerca de 45.000 empregos diretos (ABIFA, 2003).

A grande maioria da produção brasileira de fundidos é consumida pelas indústrias automotivas e siderúrgicas (fundições cativas), ficando apenas uma pequena parcela para os setores da indústria mecânica e da infra-estrutura (fundições de mercado). Esta demanda relativamente baixa e a ausência de uma política de mercado caracterizam as fundições de mercado como empresas de pequeno ou médio porte, carentes de uma estrutura gerencial organizada.

Entretanto, nos últimos anos, as fundições de mercado vêm registrando um grande crescimento, e a prática gerencial baseada apenas no bom senso e na experiência do administrador de processo não tem sido suficiente.

A fundição que serviu de base para este trabalho foi primeiramente estudada por Santos-Meza et al. (2002). O processo produtivo (Figura_1) caracteriza-se por um forno que é alimentado por matérias-primas (em geral, lingotes fundidos obtidos após um processo de refino de minérios, sucatas e outros) produzindo determinado tipo de liga. O forno tem uma limitação de capacidade por hora podendo produzir uma quantidade máxima de uma certa liga. Uma vez determinada a liga que deve ser produzida, deve-se determinar a melhor mistura de matéria- prima, de acordo com a composição química, de forma a minimizar o custo da liga, ou seja, tem-se que resolver o clássico problema da mistura.Após fundida, a liga é vazada em moldes de areia e o forno é então realimentado para a produção de um novo (ou mesmo) tipo de liga.

Os moldes são preparados segundo projetos que especificam todos os detalhes dos contornos, canais de vazamento, bem como o tipo de liga adequada e são produzidos por máquinas de moldagem paralelas automatizadas que têm taxas de produtividade conhecidas. Estas máquinas podem trabalhar uma parte da hora produzindo um tipo de molde e outra parte na produção de outros tipos. No entanto, cabe observar que, para o problema em questão, embora as máquinas de moldagem possam ser re-preparadas para a produção de diferentes moldes dentro de uma hora, a liga produzida pelo forno somente pode ser alterada na mudança de turnos (6 horas). Portanto, as mudanças na produção dos moldes são restritas aos itens que utilizam a mesma liga.

Diante disso, observa-se que, a programação da produção nesta fundição tem dois momentos importantes e interligados: a programação do forno, na qual é definida a liga a ser produzida em cada período; e a programação das máquinas de moldagem, na qual é definida a quantidade de cada item a ser produzida em cada período, ou seja, deve-se dimensionar os lotes de cada item.

Pode-se definir de forma bastante simples o problema de dimensionamento de lotescomo um problema de otimização que consiste em determinar a quantidade de itens a ser produzida em uma ou mais máquinas, em cada período ao longo de um horizonte de planejamento finito, de modo a atender uma certa demanda e a otimizar uma função objetivo (por exemplo, minimizar custos). Em geral, esses problemas pertencem a classe NP-difícil, fazendo com que a maioria dos métodos de solução sejam heurísticos. No caso das fundições, o problema de dimensionamento de lotes está presente na programação do setor de moldagem onde se determina a quantidade de cada item a ser produzida em cada período.

Revisões bibliográficas destes problemas são encontradas em Bahl et al. (1987) e Kuik et al. (1994).

O problema de programação da produção (scheduling) é definido como um problema de otimização que consiste em programar determinadas tarefas em uma ou várias máquinas de forma a otimizar uma função objetivo (por exemplo, minimizar o tempo de processamento). As decisões tomadas são de curto prazo (nível operacional). A programação do forno em fundições, onde são definidas quais ligas devem ser produzidas em cada período, é um bom exemplo de um problema de programação da produção. Algumas revisões bibliográficas podem ser encontradas em Potts & van Wassenhove (1992), Potts & Kovalyov (2000) e Allahverdi et al. (1999).

O objetivo deste trabalho é propor um modelo matemático e um método de solução para auxiliar, principalmente as fundições de mercado, na resolução dos problemas planejamento e programação da produção. O modelo considera de forma simultânea o problema de dimensionamento de lotes para os itens e problema de programação das ligas. Drexl & Kimms (1997) apresentam uma excelente revisão bibliográfica de trabalhos que consideram problemas integrados.

Uma revisão da literatura em problemas de planejamento e programação da produção em fundições é apresentada na seção 2. A seção 3 contém o modelo matemático que pode ser caracterizado por um problema de dimensionamento de lotes monoestágio com vários itens, custo de preparação, restrição de capacidade e máquinas paralelas, sem considerar tempo de preparação e admitindo atraso no atendimento à demanda. Na seção 4 é proposto um método de solução heurístico. Na seção 5 são apresentados os resultados computacionais e, na seção 6, as conclusões.

2. Revisão Bibliográfica Após uma ampla revisão bibliográfica foi possível constatar a escassez de trabalhos envolvendo problemas de planejamento e programação da produção especificamente voltados ao setor de fundições, principalmente, fundições de pequeno e médio porte.

Em Araujo et al. (2002) é realizado um estudo do problema de planejamento e programação da produção para um caso prático encontrado em uma fundição de porte pequeno. O processo produtivo é bastante parecido com o processo descrito na seção 1, as principais diferenças consistem no fato de que as ligas podem ser modificadas a cada fornada e, cada item pode ser produzido por uma, e somente uma, liga. Araujo et al. (2002) modelaram o problema como um problema de programação inteira mista, com restrição de capacidade, custo de preparação e considerando a possibilidade de atraso no atendimento a demanda. O objetivo principal é minimizar os atrasos e os custos de estoque. O método de solução desenvolvido consiste num método de horizonte rolante, ou seja, resolve-se o problema para um horizonte de planejamento de T períodos onde apenas o primeiro período é efetivamente implementado e os dados atualizados. Em seguida o horizonte é rolado à frente e o método é aplicado novamente para mais T períodos. Além disso, os autores utilizaram busca local para fixar algumas variáveis a cada etapa do método. São apresentados alguns resultados computacionais comparando o método de solução e o pacote Cplex 7.1.

Em Araujo (2003) foi feito um estudo de caso em uma fundição de grande porte para a qual foi proposto um modelo matemático que foi resolvido com um pacote de otimização inteira. Nesta fundição, existem vários fornos em operação que produzem apenas dois tipos principais de liga, tornando a programação dos fornos menos crítica de modo que, a programação das linhas de moldagem é que "puxa" a programação dos fornos. Os resultados computacionais foram comparados com aqueles obtidos pela empresa, mostrando expressivos ganhos de produtividade e redução de atrasos na entrega dos pedidos.

O estudo em Santos-Meza et al. (2002) é semelhante ao presente trabalho, no entanto, os autores não consideram custo de preparação e não permitem atraso no atendimento à demanda. O método de solução proposto por Santos-Meza et al.

(2002) serviu de base para o método da seção 4 deste trabalho.

Sounderpandian & Balashanmuga (1991) estudaram o problema de sequenciamento de tarefas às máquinas numa grande fundição (850 empregados), que têm como principal cliente a indústria automobilística. A fábrica produz 200 tipos de itens em 41 máquinas. Para cada máquina são atribuídos valores de 0 a 100 de acordo com a conveniência de se utilizar a máquina para fazer determinado item.

O método de solução considera apenas os 100 itens principais que representam 90% da demanda e é baseado no clássico Problema de Transportes, onde cada máquina oferece uma quantidade de horas por semana e cada item demanda um certo número de horas para ser fabricado. O objetivo é a minimização do custo total da programação (que é baseado numa matriz de conveniência). Segundo os autores, o método foi implantado facilmente na empresa conseguindo reduzir os problemas encontrados.

Gravel et al.(2000) utilizaram algoritmos genéticos para resolver um problema de sequenciamento das ligas numa fundição de alumínio. O indústria possui três fornos que devem produzir diferentes tipos de ligas. Entre duas cargas do forno é possível deixar um resíduo da liga antiga para que o tempo de aquecimento da nova liga seja menor. Entretanto, dependendo da seqüência em que as ligas são feitas isto não é possível, pois a liga anterior pode ter componentes que não podem estar presentes na liga que será feita posteriormente. Neste caso, o forno tem que ser esvaziado e o tempo de preparação é muito maior. Desta forma, o tempo de preparação depende da seqüência em que as ligas são produzidas. Os autores apresentaram um algoritmo genético em duas fases. Na primeira fase as ligas são associadas aos fornos e, na segunda fase é feito o sequenciamento das ligas nos fornos. Segundo os autores, o método apresenta bons resultados e está sendo utilizado pela empresa.

Bowers et al. (1995) estudaram o problema de planejamento e programação da produção numa indústria de fabricação de lingotes de alumínio. Nesta indústria, não é permitido atraso no atendimento à demanda. Quando não existem lingotes para o atendimento da demanda, deve-se importar lingotes ou aparar lingotes mais largos para suprir a demanda. O objetivo do artigo é minimizar a quantidade de lingotes importados ou aparados. Os autores apresentaram um método de solução em duas fases aplicado de forma rolante no tempo, onde, na primeira fase uma heurística determina a programação das máquinas de moldagem para todo o horizonte de planejamento e, na segunda fase, um problema linear é resolvido para determinar a programação ótima dos fornos de acordo com a programação estabelecida na primeira fase. Os resultados computacionais apresentados mostram, segundo os autores, uma redução de 20,4% para 0,4% de lingotes importados ou aparados.

Hendry et al.(1996) estudam um problema de corte de estoque acoplado ao problema de programação da produção numa indústria de cobre. O processo produtivo pode ser dividido em três partes e consiste basicamente em fundir o metal no forno, produzir barras grandes e cortar as barras grandes em pedaços menores. O objetivo principal do estudo é a redução de custos, o que implica diretamente na redução do número de vezes que o forno é utilizado e na redução das perdas no corte das barras. Um método de solução, em dois estágios, baseado no princípio de horizonte rolante foi proposto. No primeiro estágio, um modelo matemático de programação inteira é resolvido heuristicamente determinando uma solução agregada indicando os padrões de cortes a serem utilizados minimizando a perda. No segundo estágio, outro modelo de programação inteira é resolvido por um método exato determinando um programa de produção diária para a solução agregada dada pelo primeiro estágio. Os resultados são comparados com os resultados práticos da empresa, mostrando uma redução substancial nos custos com ganhos no rendimento dos fornos e diminuição das perdas no processo de corte.

Foram encontrados alguns outros trabalhos que tratam do problema de programação da produção em grandes siderúrgicas onde o processo produtivo é um pouco diferente daquele encontrado em fundições. O processo produtivo da indústria siderúrgica é caracterizado pela inexistência do setor de moldagem, pois os itens demandados são chapas de aço de diferentes tamanhos e composições fabricadas por máquinas de laminação, onde o metal passa por cilindros rolantes distanciados de acordo com as especificações da chapa a ser fabricada.

Tang et al.(2001) fazem uma revisão bibliográfica de trabalhos de planejamento e programação da produção aplicados à indústria siderúrgica. Neste trabalho, o desenvolvimento histórico do processo produtivo é descrito, dando uma ênfase maior ao processo de produção atual, onde se integram as várias fases de produção. Além de modelagem matemática, fazem ainda uma revisão dos métodos de solução, em sua maioria desenvolvidos especificamente para grandes siderúrgicas e, por fim, apontam algumas direções para futuros trabalhos com novas modelagens e métodos de solução que podem ser desenvolvidos.

Lopes et al. (1998) enfatizam seus estudos na programação da produção do setor de laminação. Os autores modelaram o problema como um problema do caixeiro viajante com restrições do tipo mochila e propõem um método heurístico, baseado em busca tabu. Dados práticos foram utilizados para obter os resultados computacionais que mostraram uma melhoria do método proposto em relação ao plano que vinha sendo implementado na indústria.

Tang et al.(2000a) também resolvem o problema de programação da produção no setor de laminação, com uma modelagem de múltiplos caixeiros viajante, sendo que, no método de solução é feita uma relaxação para o problema de um único caixeiro viajante, o qual é resolvido utilizando algoritmos genéticos. O método foi aplicado numa grande fábrica durante um ano obtendo uma melhoria de 20% em relação ao sistema anterior.

Tang et al. (2000b) apresentam um modelo de programação não linear que trata do conflito entre máquinas, cujo objetivo consiste na pontualidade na entrega dos pedidos e continuidade do fluxo produtivo, ou seja, minimizar o tempo de espera entre as operações da fábrica. O método de solução consiste numa reformulação do problema como um modelo de programação linear.

Lee et al. (1996) dão uma visão geral do desenvolvimento do processo de fundição e descrevem com detalhes o processo de fabricação no qual o ferro fundido é transformado em placas de aço, destacando os vários objetivos que podem ser considerados neste tipo de fundição. São relatadas várias experiências da IBM em desenvolvimento de métodos de solução para o problema de sequenciamento de tarefas entre as várias máquinas.

Outros trabalhos que tratam do problema de sequenciamento em grandes siderúrgicas são: Petersen et al.(1992), onde foi desenvolvida uma heurística gulosa e Hamana et al. (1995) que apresentaram um método de solução híbrido utilizando algoritmos genéticos.

3. Modelo Matemático Índices: m=1,...,M máquinas de moldagem; t=1,...,T períodos de tempo i=1,...,N tipos de itens; k=1,...,K tipos de ligas.

Dados: quantidade de itens do tipo i possível de ser produzida na máquina m por hora (se aim =0, o item i não pode ser produzido pela máquina m); quantidade máxima de liga produzida pelo forno por hora no período t; demanda de itens do tipo i no período t; número de horas no período t; custo de estocar uma unidade do item i de um período para o próximo; penalidade por atrasar uma unidade do item i de um período para o próximo; penalidade por preparar a liga k(é um parâmetro do problema que, por consistência futura, representa simbolicamente 'número de itens' não produzidos pela mudança de liga); conjunto de itens que utilizam a liga k; um número grande.

Variáveis de decisão: fração de tempo no período t utilizado para produzir itens do tipo i na máquina estoque do item i no final do período quantidade atrasada do item ino final do período t([/img/revistas/pope/v23n3/ variável binária que indica se a liga k é produzida no período t; variável que indica se será cobrado custo de preparação para a liga k no período t (como será explicado posteriormente, embora esta variável seja contínua, as características do modelo fazem com que ela assuma apenas valores 0 ou 1).

O problema é formulado matematicamente como:

A função objetivo (1) consiste nos custos de estoques e nas penalidades por atraso no atendimento a demanda. A restrição de balanceamento de estoque em (2) considera o estoque negativo. Observe que,[/img/revistas/pope/v23n3/ a02img09.gif]htaimXimt significa a quantidade produzida, em toneladas, de itens do tipo ino período t (em todas as máquinas). A restrição (3) define a capacidade de produção do forno em cada período t. As restrições (4) e (5) garantem que, em cada período, somente itens associados à liga escolhida possam ser produzidos. Ainda, (6) faz com que apenas um tipo de liga seja produzido em cada período t, e (7) representa a mudança de liga de um período para o outro.

As demais inequações delimitam as variáveis do modelo, sendo, que a variável[/ img/revistas/pope/v23n3/a02img08.gif]apesar de ser contínua, a restrição (7) em conjunto com a função objetivo (1) faz com que, na otimalidade, assuma somente valores 0 ou 1 (=0 se[/img/revistas/ pope/v23n3/a02img10.gif]=<formula/>(i.e., não houve mudança de liga); e<formula/>=1 se[/img/ revistas/pope/v23n3/a02img10.gif]=0e<formula/>=1 (i.e., houve mudança de liga)).

Na função objetivo (1), as penalidades por atraso têm peso maior do que os custos de estoques. Além disso, a segunda parcela da função objetivo consiste nas penalidades por preparação, que, neste caso, penaliza mudanças de liga, não tendo relação com a ordem em que as ligas são feitas.

A variável<formula/>funciona como uma variável artificial usada para obter uma solução factível. Se[/img/revistas/pope/v23n3/ a02img11.gif]>0 para algum i (ou seja, existe atraso no último período para algum item), significa que não foi possível atender a demanda no horizonte de planejamento estabelecido com a capacidade disponível nesse horizonte. No entanto, se<formula/>>0, para algum i com t¹Te[/ img/revistas/pope/v23n3/a02img11.gif]=0 para todo i, então existe capacidade suficiente para produzir a demanda dentro do horizonte de planejamento estabelecido. Vale a pena observar que os estoques negativos correspondem a atrasos e o decisor pode, alterando os parâmetros da função objetivo (1), proibir, ou não, atrasos de certos itens. Além disso, os estoques negativos fornecem uma ferramenta para a avaliação dos prazos de entrega. Por exemplo, se di1=30 e<formula/>=10,[/img/revistas/pope/v23n3/ a02img13.gif]=5,<formula/>=0, significa que a demanda para o item iserá totalmente atendida com 3 dias de atraso. Desta forma, é possível alertar o cliente e, se necessário, re-calibrar os parâmetros relativos a este item.

Observe que, no modelo (1)-(11), as equações (4) e (5) não podem ser simplificadas por

como na maioria dos modelos de dimensionamento de lotes. Isso decorre do fato que um mesmo item pode ser produzido por diferentes ligas. Por exemplo, sendo S1={1, 2}eS2={2, 3}o conjunto de itens que as ligas 1 e 2 podem produzir, respectivamente. Se<formula/>=0 (a liga do tipo 1 não é preparada no período 1), então X1,m,1= X2,m,1= 0 devido a (4') (os itens 1 e 2 não podem ser produzidos no período 1), o que é um erro pois, se[/img/ revistas/pope/v23n3/a02img16.gif]=1 (a liga do tipo 2 é preparada no período 1), então X2m1 > 0. Isso ocorre pois o item 2 pertence aos conjuntos S1e S2.

Observa-se que (1)-(11) é um modelo de programação inteira mista e, encontrar a solução ótima para casos práticos é, na maioria das vezes, inviável. Um método de solução mais eficiente do que a otimização exata do modelo é, portanto, fundamental. Esse é o objetivo do método de solução proposto a seguir.

4. Método de Solução Nesta seção apresentamos um método de solução heurístico que pode ser dividido em 3 fases. Na primeira fase tem-se uma relaxação do problema onde se considera que todos os itens possam ser produzidos por uma única liga. Com isso é proposto um modelo de programação linear que determina a quantidade de cada item a ser produzida em cada período. Na segunda fase, uma heurística determina a liga que deve ser produzida em cada período, levando-se em consideração as decisões do problema relaxado. Finalmente, na terceira fase tem-se a programação das máquinas de moldagem.

4.1 Relaxação Considere o problema relaxado onde uma liga pode produzir todos os itens. Desta forma, não é necessário fazer a programação do forno e as restrições (4), (5), (6), (7), (10) e (11) podem ser desconsideradas do modelo relaxado, assim como a segunda parcela da função objetivo.

Considerando tais relaxações e definindo uma nova variável,

segue o seguinte problema relaxado:

Sujeito a:

O modelo (13)-(17) é linear e consiste num modelo de dimensionamento de lotes monoestágio com restrição de capacidade, e pode ser considerado como um problema de fluxo em redes, o qual pode ser facilmente resolvido. Neste trabalho foi utilizado o pacote Ampl/Cplex (Fourer et al., 1993 e ILOG CPLEX 7.1, 2001) para resolver esse modelo.

4.2 Heurística Resolvendo o problema relaxado (13)-(17) o valor de Pit é obtido e consiste na quantidade de cada item a ser produzida em cada período. O próximo passo consiste na verificação da existência de alguma liga capaz de produzir todos os itens dados na solução do problema em cada período, ou seja, deve-se procurar ligas kt, t=1,...,Tde forma que: {i : Pit>0, i =1, 2,....,N}Í <formula/> Caso não exista uma liga que produza todos os itens para algum determinado período, adota-se uma heurística para escolher a liga, período a período, isto é, quando da escolha da liga no período t, já foram escolhidas as ligas nos períodos 1, ...,t-1.

' Heurística para a escolha de uma liga em cada período t Suponha k1,...,kt-1 são os índices das ligas já produzidas nos períodos 1,...,t-1, respectivamente (observe que os itens pertencentes aos conjuntos[/ img/revistas/pope/v23n3/a02img18.gif],t=1, ..., t-1, podem ser produzidos antes do período t).

1. Determine o conjunto de itens At-1 que podem ser produzidos antes do período t:

2. Determine o conjunto de itens Bt com alta prioridade em t (isto é, itens demandados em algum períodot=1, ..., t que não podem ser produzidos em períodos anteriores, pois suas ligas não foram previamente preparadas): Bt = {i | iÏAt-1 e dit> 0,t = 1, 2,..., t} 3. Se Bt ¹ Æ Então: Determine o conjunto de ligas com alta prioridade no período t: Ct = {k: Sk Ê Bt} Se Ct =Æ então: escolha a liga kt para o período t tal que:

senão: escolha a liga kt para o período t tal que:

Senão: escolha a liga kt para o período t tal que:

(Obs. Em (18) ' (20) o valor da variável[/img/revistas/pope/v23n3/ a02img08.gif]é dado por:<formula/>=0 se k=kt-1 e[/ img/revistas/pope/v23n3/a02img08.gif]=1 se k ¹ kt-1) Fim da heurística para a escolha da liga no período t.

Os passos 1 e 2 são de importância fundamental para o sucesso da heurística, pois a escolha da liga em determinado período é feita com base em decisões tomadas em períodos anteriores, o que é muito importante para minimizar os atrasos.

No passo 3, as equações (18), (19) e (20) determinam a liga a ser produzida com base nas decisões do problema relaxado (Pit) e em uma penalidade por trocas de ligas (csk<formula/>). Nas equações (18) e (20) a escolha é feita entre todas as ligas, sendo que, em (18) é dada uma prioridade maior às ligas que produzem a maior quantidade de itens associados ao conjunto Bt. Na equação (19) a escolha é feita somente entre as ligas que produzem todos os itens associados ao conjunto Bt. Como critério de desempate nas equações (18), (19) e (20), a liga kpara a qual o conjunto Sk tem maior cardinalidade será escolhida.

Cabe observar que, outras heurísticas para a escolha das ligas foram implementadas e testadas, mas os resultados computacionais foram inferiores à heurística acima. Uma delas considerava o impacto que a escolha de uma determinada liga provocaria na função objetivo do problema relaxado.

Outra heurística implementada, cujos resultados são apresentados na seção 5 (Tabela_6) e foram bastante próximos dos resultados da heurística acima, apenas substitui a equação (18) por:

A idéia desta heurística é privilegiar uma liga que possa produzir os itens sugeridos pelo problema relaxado no período t, isto é, Pit, além dos itens com grandes atrasos. Vale a pena observar que a solução Pit do problema relaxado (13)-(17) já carrega o esforço de diminuir os atrasos.

4.3 Programação das Máquinas de Moldagem Uma vez determinadas heuristicamente as ligas que serão produzidas em cada período, deve-se fazer a programação das máquinas de moldagem, que consiste em definir a fração de tempo que cada máquina mdeve ser utilizada para produzir determinado item i num período t(Ximt). Lembre-se que o total de itens do tipo i produzido na máquina m no período t é aimhtXimt. Para tanto, um problema de transporte generalizado é resolvido para cada período t.

Pode-se utilizar vários critérios para se definir a função objetivo. Por exemplo:

o qual tenta balancear a produção dos itens entre as máquinas de moldagem.

segue o seguinte modelo (o qual foi resolvido com o pacote Ampl/Cplex) para determinar a programação das máquinas em cada período t:

4.4 Algoritmo Geral Cabe observar que, o procedimento proposto nas seções 4.1 ' 4.3, produz uma solução factível (sem garantia de otimalidade) para o modelo (1)-(11). De fato, se a heurística for capaz de obter uma solução, então ao reconsiderar o modelo (1)-(11) as restrições (6) e (7) são satisfeitas pois, [/img/revistas/pope/ v23n3/a02img20.gif] =1 e <formula/> =0 para todo k¹kt. As restrições (5) são satisfeitas devido à (27) e (4) são satisfeitas devido á hipótese de que a capacidade da máquinas é folgada, de modo que Ft<1.

As outras restrições do modelo (1)-(11) são consideradas no modelo (13)-(17).

' Algoritmo Geral Faça t=1.

1 Enquanto t<T, faça: 1.1 Resolva o problema relaxado (13)-(17).

1.2 Determine, heuristicamente (seção 4.2), a liga kt para cada período t.

Se {i : Pit>0, i = 1, 2,....,N} Í[/img/revistas/pope/v23n3/ a02img17.gif] Então: t=t+1 e repita o passo 1.2 Senão: Faça Pit=0, iÏ [/img/revistas/pope/v23n3/ a02img17.gif],t=t+1 e vá para o passo 1.1 2 Resolva o problema relaxado (cabe observar que as ligas k1, k2, ..., kT já foram escolhidas para os períodos 1, 2, ..., T, respectivamente). Para cada período t, t=1, ..., T resolva o problema (23)-(27), determinando Ximt, a fração de tempo do período t utilizada para produzir itens do tipo i na máquina m. Fim.

O método de solução proposto no Algoritmo Geral acima é baseado no método proposto por Santos-Meza et al. (2002). As principais modificações estão na heurística para determinação das ligas, onde, no passo 3 o problema deixa de ser infactível caso Ct =Æ , pois, admitindo atraso no atendimento à demanda, mesmo que não exista uma liga para produzir determinado item que tem demanda positiva num período t, este item poderá ser produzido nos períodos seguintes.

Além disso, as equações (18), (19) e (20) tiveram que ser adaptadas para o novo modelo que considera atraso no atendimento a demanda e custo de preparação.

5. Resultados Computacionais Os testes computacionais foram realizados num Pentium III 500 MHz com 512 MB de RAM e os parâmetros utilizados para a geração dos exemplos são apresentados na Tabela_1:

Observa-se que os dados utilizados nos exemplos foram semelhantes aos utilizados por Santos-Meza et al.(2002). Entretanto, foram feitas algumas modificações que tornaram os exemplos mais próximos da realidade e, conseqüentemente, mais difíceis de serem resolvidos: - demanda (dit): a demanda para todos os itens e todos os períodos, inclusive para primeiro, foi gerada aleatoriamente no intervalo [0,200] com dit=0 se dit <50.

- capacidade (Capt): foram consideradas diferentes capacidades para a geração dos exemplos. A capacidade foi alterada pelo fator multiplicativo b que em Santos-Meza et al.(2002) foi usado 1,4. Nos testes computacionais realizados aqui foram considerados os seguintes valores para b : 0,6, 1,0 e 1,4, representando capacidade apertada, normal e folgada, respectivamente. Vale observar mais uma vez que o modelo atual permite trabalhar com capacidade mais apertada, pois lida com atrasos.

- penalidade por preparação(csk): devido às características do problema prático, a penalidade por troca de ligas (preparação) é relativamente pequena quando comparada com os outros custos. No entanto, manteremos em (18), (19) e (20), os fatores relativos a decisões sobre preparações, pois assim tem-se um método mais robusto e de fácil adaptação para casos onde a penalidade por preparação é mais expressiva.

Foram gerados 10 exemplos para cada combinação de parâmetros. Cada exemplo foi resolvido diretamente pelo método branch and bounddo pacote Cplex 7.1 e pelo método heurístico descrito na seção 4.

As Tabelas_2 e 3 mostram o tempo médio (em segundos) gasto pelo pacote Cplex e pelo método heurístico, respectivamente. Como é possível observar, para todos os exemplos o tempo computacional do método heurístico é significativamente inferior ao obtido pelo pacote, que só não é ainda maior devido ao fato de que foi imposta uma limitação de tempo, pois, caso contrário, o pacote Cplex levaria várias horas para rodar os exemplos, muitas vezes sem melhorar a solução. O limite de tempo estabelecido foi de 1 hora (3.600 segundos), pois, considerando um problema prático onde o programa deve ser rodado pelo menos uma vez por dia, permitir mais de 1 hora torna sua aplicação inviável.

Analisando os resultados das Tabelas_2 e 3 pode-se concluir que, para o método heurístico, o aumento do tamanho do exemplo causa um impacto suave no tempo computacional. Entretanto, isso não acontece para o pacote Cplex onde, tanto o aumento do número de itens como do número de períodos fazem com que o esforço computacional aumente de forma desproporcional.

O efeito da variação de capacidade no tempo computacional do método heurístico também é bastante suave, sendo que, para o pacote Cplex, em geral, quanto mais apertada a capacidade menor o tempo computacional. Isso ocorreu porque para exemplos com capacidade apertada, as decisões com respeito às ligas que deverão ser produzidas em cada período são mais simples, desde que, poucos itens podem ser produzidos em cada período.

A Tabela_4 fornece a porcentagem de exemplos em que o pacote conseguiu encontrar a solução ótima antes do limite de tempo (uma solução é considerada ótima se está a menos de 1% do limitante inferior). Como era de se esperar, quanto menor o tamanho do exemplo, maior a porcentagem. Para a maioria dos exemplos grandes (mais de 45 itens e 12 períodos), o limite de tempo (1 hora) foi alcançado antes da otimalidade (ver o complementar dos números da Tabela 4). Nestes casos, a melhor solução factível encontrada é apresentada.

Comparando agora a qualidade da solução, a Tabela_5 mostra a variação média entre os dois métodos, sendo que, esta variação é calculada de acordo com a seguinte fórmula:

Avaliando o desempenho do método heurístico em relação ao método branch and bound do pacote Cplex pode-se observar que, em geral, a heurística apresenta um desempenho muito bom. Observe que, na medida em que o tamanho dos exemplos cresce, o desempenho do método heurístico melhora em relação ao pacote. Isso ocorreu porque, para problemas maiores, a porcentagem de exemplos em que o Cplex obteve a solução ótima decresce (ver Tabela_4) e a qualidade das soluções factíveis encontradas pelo pacote é inferior do que as soluções encontradas pela heurística. Mesmo para problemas pequenos, onde o Cplex obteve a solução ótima, pode-se considerar que a heurística apresenta bons resultados.

Uma outra heurística foi implementada onde se utiliza a escolha da liga por (18') no lugar de (18). Os resultados computacionais são apresentados na Tabela 6 e, para os exemplos em que o Cplex chegou a otimalidade a variaçãomédia da solução heurística é de 16,63%. Portanto, em média, os resultados computacionais foram inferiores aos da heurística anterior (Tabela_5). Isso ocorreu devido a alguns exemplos (cerca de 1% do total de exemplos) onde a heurística com (18') apresentou resultados muito ruins fazendo piorar a média geral. Isso mostra que a heurística com a escolha (18) é mais robusta, enfatizando a importância de escolher ligas que produzam itens pertencentes ao conjunto Btde itens críticos.

O modelo matemático e o método de solução proposto por Santos-Meza et al.(2002) foram utilizados para tentar resolver os exemplos do presente trabalho.

Entretanto, o fato de não permitir atraso no atendimento da demanda fez com que em nenhum dos exemplos o método proposto em Santos-Meza et al.(2002) conseguisse encontrar uma solução factível. Foi possível constatar que, para exemplos com capacidade apertada e normal (b =0,6 e 1,0) as infactibilidades ocorreram principalmente devido à violação das restrições de capacidade.

Entretanto, para exemplos com capacidade folgada (b =1,4) a maioria das infactibilidades ocorreram devido à falta de liga capaz de produzir todos os itens demandados em cada período (Ct=Æ, para algum período t).

A Tabela_7 apresenta a porcentagem de exemplos em que a causa das infactibilidades foi a violação das restrições de capacidade. Como todos os exemplos foram infactíveis, o complementar desta porcentagem representa os exemplos em que a falta de liga foi a causa das infactibilidades.

A consideração de demanda positiva no primeiro período de planejamento tornou os exemplos difíceis de serem resolvidos sem considerar atrasos, pois no primeiro período não é possível atender a demanda pelos estoques. Tais infactibilidades não ocorreram em Santos-Meza et al.(2002), pois para realização dos testes computacionais, os autores utilizaram uma estrutura especial para a geração da demanda, ou seja, no primeiro período não existe demanda e, além disso, para exemplos maiores (mais de 45 itens), a matriz de demanda foi gerada numa estrutura de escada (por exemplo, existe demanda para os itens i=1, ..., 15 somente nos períodos t=1, 2, 3; demanda para os itens i=13, ..., 25 somente ocorrem nos períodos t=4, 5, 6...) evitando a falta de liga que produza todos os itens demandados. Os autores argumentaram que este tipo de estrutura ocorre em alguns problemas práticos, devido à formação de lotes em estágios subseqüentes.

6. Conclusão Este artigo foi baseado num trabalho anterior desenvolvido por Santos-Meza et al.(2002) que trata de um problema prático encontrado numa fundição de médio porte. Com a intenção de tornar o modelo mais geral e mais próximo da realidade, neste trabalho é proposto um modelo estendido considerando custo de preparação e permitindo atraso no atendimento à demanda (o que, em muitos casos práticos, é inevitável). Desta forma, foi possível obter soluções mesmo com a redução da capacidade do forno.

O modelo proposto consiste num modelo de programação inteira mista de difícil resolução. Após a análise dos resultados computacionais foi possível ressaltar a importância do desenvolvimento de métodos heurísticos baseados em características específicas do problema, pois, além do baixo custo de implantação, em termos de tempo computacional o método heurístico desenvolvido se mostrou perfeitamente aplicável a problemas práticos de grande escala. Em termos de qualidade da solução o método foi bastante eficiente, principalmente quando se tem em mente que em problemas práticos, a busca pela otimalidade muitas vezes não se faz realmente necessária, pois os dados são geralmente imprecisos tais como, as penalidades por atraso e custos de estoque que são subjetivamente estimados e as previsões de demanda que nem sempre são corretas e sofrem alterações freqüentes.