Resolución de un problema de programación de la producción en un entorno flowshop mediante un procedimiento metaheurístico biobjetivo

Abstract

En este trabajo se analiza un problema de secuenciación correspondiente a un entorno de producción del tipo flowshop. Se recurre a un procedimiento metaheurístico biobjetivo para resolver el problema de secuenciación correspondiente a dicha configuración productiva. El problema de programación de la producción considerado puede caracterizarse como un skip flowshop en el que se tiene en cuenta la vinculación con los almacenes de materias primas y de productos terminados. Al evaluar la calidad de las soluciones propuestas se tienen en cuenta simultáneamente los objetivos de minimización del tiempo de producción total (makespan) y minimización del retraso total (total tardiness). El procedimiento propuesto está basado en una estrategia multiobjetivo de búsqueda local que responde a la estructura de la metaheurística recocido simulado (simulated annealing). En este caso, el método metaheurístico desarrollado genera un conjunto de soluciones que intenta proporcionar una buena aproximación a la frontera óptima de Pareto. Con el fin de evaluar el rendimiento de la metodología propuesta se realizan una serie de experimentos sobre dos conjuntos de problemas de prueba. A partir de los resultados obtenidos con el primer conjunto de problemas de tamaño más reducido y su comparación con un método exacto de resolución puede concluirse que las soluciones proporcionadas por el procedimiento utilizado resultan adecuadas tanto desde el punto de vista de su calidad como del esfuerzo computacional invertido en su generación. Además, el algoritmo fue probado con problemas de mayor tamaño, para evaluar su comportamiento en espacios de búsqueda más amplios.

In this work, we analyze a sequencing problem corresponding to a production environment of the flowshop type. A biobjective metaheuristic procedure is used to solve the sequencing problem corresponding to the aforementioned configuration. The production scheduling problem can be characterized as a skip flowshop in which the links with the warehouses of raw materials and finished products is taken into account. When evaluating the quality of the proposed solutions, the objectives of minimization of maximum completion time (makespan) and minimization of total tardiness are taken into account simultaneously. The proposed procedure is based on a biobjective local search strategy that responds to the structure of simulated annealing metaheuristics. In this case, the metaheuristic method developed generates a set of solutions that try to provide a good approximation to the Pareto optimal front. In order to evaluate the performance of the proposed methodology, a series of experiments are carried out on two sets of test problems. From the results obtained with the first set of problems of smaller size and its comparison with an exact method of resolution, it can be said that the solutions provided by the proposed procedure are suitable both from the point of view of their quality and the computational effort invested in their generation. In addition, the algorithm was tested with larger problems, to evaluate its behavior in wider search spaces.

Neste trabalho analisamos um problema de sequenciamento correspondente a um ambiente de produção do tipo flowshop. Um procedimento metaheurístico biobjetivo é usado para resolver o problema de sequenciamento correspondente à referida configuração produtiva. O problema de programação da produção considerado pode ser caracterizado como um skip flowshop no qual a ligação com os armazéns de matérias-primas e produtos acabados é levada em consideração. Ao avaliar a qualidade das soluções propostas, os objetivos de minimização do tempo total de produção e minimização do atraso total são levados em consideração simultaneamente. O procedimento proposto é baseado em uma estratégia de busca local multiobjetivo que responde à estrutura de metaheurísticas de recozimento simulado. Nesse caso, o método metaheurístico desenvolvido gera um conjunto de soluções que tentam fornecer uma boa aproximação à fronteira ótima de Pareto. A fim de avaliar o desempenho da metodologia proposta, uma série de experimentos são realizados em dois conjuntos de problemas de teste. A partir dos resultados obtidos com o primeiro conjunto de problemas de menor tamanho e sua comparação com um método exato de resolução pode-se afirmar que as soluções fornecidas pelo procedimento proposto são adequadas tanto do ponto de vista de sua qualidade quanto do esforço computacional investido em sua geração. Além disso, o algoritmo foi testado com problemas maiores, para avaliar seu comportamento em espaços de busca mais extensos.