Heurísticas para o Problema de Dimensionamento de Lotes com Máquinas Paralelas Flexíveis

Abstract

This work is related to the lot sizing problem with flexible parallel machines, which basically consists in determining the quantity of items to be produced, on each of the machines, in a finite time horizon, satisfying a given demand. This problem has an economic origin and involves costs of production, inventory and setup. In the standard problem, each item can be produced on any of the machines, i.e., we have the total machine flexibility. However, it is not always feasible to have total machine flexibility due to the costs. Therefore, it may be important to implement only a limited amount of flexibility. The investment of upgrading a machine to produce a specific product becomes a binary decision variable and there is a global budget on investment decisions. A mathematical formulation to this problem was proposed in the literature and the computational results obtained throwgh a combinatorial optimization package showed that solve the formulation is very difficult, especially for instances with many items. So in this work we have proposed three different heuristics for this problem, in order to find good solutions in low computational times. Experiments were performed to compare the heuristics with the resolution of the model via optimization package. We have seen that by increasing the number of items and machines, the results with better quality were obtained by only one of the heuristics. In terms of computational times, all the heuristics achieved inferior times in average over CPLEX.

Este artigo trata do problema de dimensionamento de lotes com máquinas paralelas flexíveis, que consiste basicamente em determinar a quantidade de itens a serem produzidos, em cada uma das máquinas, em um horizonte de tempo finito, satisfazendo uma demanda pré-estabelecida. Este problema tem origem econômica e envolve custos de produção, estoque e preparação de máquinas. No problema padrão, cada item pode ser produzido em qualquer uma das máquinas, ou seja, tem-se a flexibilidade total de máquinas. No entanto, nem sempre é viável ter flexibilidade total das máquinas, devido aos altos custos relacionados. Portanto, pode ser de grande importância implementar apenas uma flexibilidade limitada das máquinas. A consideração ou não da flexibilidade de uma máquina para produzir um produto específico torna-se uma variável de decisão e há um custo de investimento associado a estas decisões. Uma formulação matemática para esse problema foi proposta na literatura e os resultados computacionais obtidos por meio de um pacote de otimização combinatória mostraram que resolvê-la pode ser uma tarefa difícil, especialmente para instâncias com muitos itens. Sendo assim, neste trabalho foram propostas três heurísticas para o problema, com intuito de buscar boas soluções em baixos tempos computacionais. Experimentos foram realizados para comparar as heurísticas com a resolução do modelo via pacote de otimização. Pôde-se observar que conforme o número de itens e de máquinas foram aumentando, as soluções com melhor qualidade foram obtidas por apenas uma das heurísticas. Em termos de tempos computacionais, todas as heurísticas obtiveram em média tempos inferiores aos do CPLEX.