Optimización de la tardanza total en máquinas paralelas: caso de estudio en la industria del café

Production scheduling is one of the most important tasks in manufacturing systems since it allows the allocation of jobs with a certain number of available resources. In the production and service industries, meeting the established commitments with the different customers and production deadlines can lead to higher levels of satisfaction and market competitive advantages. On the other hand, one of the main industries worldwide is the coffee industry. Indeed, coffee is the second most traded commodity in the world. Therefore, this research addresses the optimization of the total tardiness in the scheduling of jobs in parallel machines for a case study in a coffee roaster. This is an NP-hard problem where each job requires the roasting process and, in addition, has an associated delivery time. Each job’s processing time depends on the machine that is designated and not all machines can run all jobs. We present the mathematical model to describe the problem using mixed integer linear programming and then it is implemented in Python. Additionally, a mate heuristic model based on the ATC heuristic is proposed in order to reduce the computation time and to reach solutions close to the optimum. This model was evaluated with one thousand instances of real data from the roasting process. The Gurobi optimizer was used to solve the problem. The exact method shows high computational times, so we proposed to first perform the sequencing of jobs and then assign them to the machines by means of a simplified mathematical model. By using the proposed mate heuristic model, an average reduction of 53.98% of the execution time is achieved and with respect to the solution delay, this model achieves a median of 0.0% with respect to the optimum.
La programación de producción es una de las tareas con mayor importancia en sistemas de manufactura ya que permite la asignación de trabajos con cierto número de recursos disponibles. En la industria de manufactura y de servicios, poder cumplir con los compromisos acordados con los diferentes clientes y con los plazos de producción puede generar mayores niveles de satisfacción y ventajas competitivas en el mercado. Por otra parte, una de las principales industrias a nivel mundial es la cafetera. El café es la segunda materia prima más negociada del mundo. Por lo tanto, en esta investigación se aborda la optimización de la tardanza total en la programación de trabajos en máquinas paralelas para un caso de estudio en una tostadora de café. Este es un problema NP-hard donde cada trabajo requiere del proceso de tostión y, además, cuenta con una fecha de entrega asociada. El tiempo de procesamiento de cada trabajo depende de la máquina que se designe y no todas las máquinas puede ejecutar todos los trabajos. Se presenta el modelo matemático para describir el problema mediante programación lineal entera mixta y se implementa en Python. Adicionalmente, se propone un modelo mate heurístico basado en la heurística ATC que permite reducir el tiempo de cómputo y obtener soluciones cercanas al óptimo. Este modelo fue evaluado con mil instancias de datos reales del proceso de tostión. Para la solución del problema se utilizó el optimizador Gurobi. El método exacto muestra altos tiempos de cómputo por lo que se propuso realizar primero la secuenciación de trabajos para luego asignarlos a las maquinas por medio de un modelo matemático simplificado. Al utilizar el modelo mate heurístico propuesto se logra reducir en promedio un 53.98% el tiempo de ejecución y con respecto a la tardanza de la solución, este modelo logra una mediana del 0.0% con respecto al optimo.