Resolución del problema de flujo general flexible con fechas comprometidas y costes dependientes del intervalo de realización de las operaciones

Abstract

En el marco de la problemática de la programación de operaciones en taller, en esta tesis se introduce un nuevo problema, que se identifica como problema de flujo general flexible (fJSP) con fechas comprometidas y costes dependientes del intervalo de realización de las operaciones. En el fJSP se deben tratar dos subproblemas, el de asignación de las operaciones a las máquinas que pueden ejecutarlas y el de secuenciación de las operaciones en cada una de las máquinas. Para este problema se propone, como función objetivo, minimizar la suma de los costes asociados a los adelantos y retrasos que se generan con respecto a la fecha de entrega comprometida y unos costes dependientes del intervalo de realización de las operaciones. De entre estos últimos se utiliza el coste de la energía necesaria para ejecutar las operaciones de los jobs (tareas) en las máquinas. Para resolver el problema propuesto se plantea un procedimiento dividido en tres pasos. En el Paso 1 se obtiene una secuencia inicial de jobs; en el Paso 2 se genera una solución inicial mediante un procedimiento que se basa principalmente en realizar, simultáneamente, la construcción y búsqueda del camino mínimo en un grafo polietápico para cada job; y en el Paso 3 se emplean procedimientos de mejora de la solución inicial. También se exponen los resultados de la experiencia computacional que evalúa el procedimiento de resolución propuesto. En los resultados se observa que el procedimiento favorece la programación de las operaciones respetando las fechas de entrega, y ayuda a reducir la factura de la empresa eléctrica, ya que en las soluciones de un conjunto de tipos de ejemplares se observa cómo se asignan, mayoritariamente, operaciones a máquinas con menor consumo de energía, y principalmente en aquellos intervalos de tiempo en los que el coste de la energía es menor. Al analizar los resultados de la experiencia computacional se observa, además, que el procedimiento encuentra la solución de ejemplares de diferente dimensión en un tiempo de proceso de ordenador razonable

In the context of the job-shop scheduling problem, this thesis introduces a new problem, which is identified as the flexible job-shop scheduling problem (fJSP) with due dates and energy costs that are dependent on the time interval in which the operations are processed. The fJSP involves two subproblems: that of assigning operations to the machines that can process them and that of sequencing the operations on each of the machines. For this problem, we propose an objective function that minimizes the sum of the costs of earliness and tardiness with respect to the due date and the costs that depend on the time interval in which the operations are processed. Regarding these costs, we have focused primarily on the cost of the energy required to process the jobs on the machines. To solve the proposed problem, we suggest a solution procedure that is divided into three steps. Step 1 involves obtaining an initial sequence of jobs, Step 2 involves generating an initial solution using a procedure based primarily on simultaneously constructing and finding the shortest path in a multistage graph for each job, and Step 3 involves implementing procedures for improving the initial solution. We report the results of the computational experiment used to test the proposed solution procedure. We were able to conclude from the results that the procedure is useful for scheduling operations while respecting due dates and that it could help reduce electricity bills, since the solutions to a set of example types demonstrated that operations were generally assigned to machines with a lower energy consumption, and mainly in time intervals in which the energy costs is low. When analysing the results of the computational experiment, we also observed that the procedure found the solution for examples of varying sizes in a fairly reasonable computer processing time.