Metaheurísticas para la programación de producción de la planta de la imprenta de billetes del banco de la república

Abstract

Abstract This work proposes the investigation and implementation of three metaheuristics that allow solving the job scheduling and sequencing problem of Imprenta de Billetes del Banco de la República, which works under the Hybrid Flowshop with Missinging Operations system with the objective of minimizing the total time to complete all the jobs or Makespan, known for being an NP-Hard type problem. For this purpose, we compare the performance of the Simulated Annealing (SA), Greedy Randomized Adaptive Search Procedure (GRASP) and Biased Random-Keys Genetic Algorithm metaheuristics using the same scheduling procedure based on the NEH algorithm. Likewise, computational results are shown with respect to the solutions of an exact model to evaluate its efficiency on 30 randomly generated instances.

Resumen Este trabajo plantea la investigación e implementación de tres metaheurísticas que permiten resolver el problema de programación y secuenciación de trabajos de la planta de producción de la Imprenta de Billetes del Banco de la República, el cual, funciona bajo el sistema Hybrid Flowshop with Missing Operations teniendo como objetivo minimizar el tiempo total de completar todos los trabajos o Makespan, conocido por ser un problema de tipo NP-Hard. Para este propósito, se comparan las soluciones de las metaheurísticas Simulated Annealing (SA), Greedy Randomized Adapttive Search Procedure (GRASP) y Biased Random-Keys Genetic Algorithm utili-zando el mismo procedimiento de scheduling basado en el algoritmo NEH. Igualmente, se muestran los resultados computacionales respecto a las soluciones de un modelo exacto para evaluar su eficiencia en 30 instancias generadas aleatoriamente.