Optimización y simulación del no-wait Flow Shop Scheduling Problem

Abstract

Este trabajo tiene como finalidad la optimización y simulación de un problema de planificación de tareas conocido como ’flow shop scheduling’, haciendo uso de la restricción ’no-wait’, la cual impide que existan tiempos de espera entre la ejecución de una misma tarea en diferentes máquinas. Es un tipo especial de problema que surge a partir del ‘job shop scheduling’, añadiendo una restricción de orden para el modo en el que se realizan las tareas. El ’flow shop scheduling’ se puede aplicar tanto al campo de la informática como al campo de la producción industrial u otros campos ajenos, como podría ser el paso de un paciente por una operación, donde tenemos tres tareas que se deben ejecutar en un orden estricto: el preoperatorio, la operación y el postoperatorio. Para la fase de optimización, se han utilizado algoritmos heurísticos para intentar obtener una solución lo más aproximada posible a la esperada en el menor tiempo posible, ya que el problema es computacionalmente complejo y por ello se encuentra dentro del conjunto ‘NP-Hard’. De cara a la simulación, se ha implementado un pequeño programa basado en simulaciones por eventos discretos, que ha permitido conocer como se comporta la secuencia obtenida en la optimización bajo un cierto umbral de incertidumbre y con ello extraer datos para analizarlos.

This work is aimed at optimizing and simulating a task planning problem known as ‘flow shop scheduling’, making use of the ‘no-wait’ restriction, which prevents waiting times between the execution of the same task on different machines. It’s a special type of problem that comes from the ‘job shop scheduling’, adding an order restriction to the way in which tasks are performed. The ‘flow shop scheduling’ can be applied to the field of computer science and to the field of industrial production or other outside fields, such as the passage of a patient through an operation, where we have three tasks that must be executed in a strict order: preoperative, operation and postoperative. For the optimization phase, heuristic algorithms have been used to try to obtain a solution as close as possible to the expected in the shortest possible time, since the problem is computationally complex and for that is inside the ‘NP-Hard’ set. For the simulation, a small program based on simulations for discrete events has been implemented, which has allowed us to know how the sequence obtained in the optimization behaves under a certain threshold of uncertainty and with it extract data to analyze them.