Programación de la producción en máquinas paralelas sujeto a adelantos, retrasos y fechas límite

Abstract

[EN] This Final Master's Work deals with the scheduling of production on unrelated parallel machines, taking into account launch dates, deadlines, sequence and machinedependent preparation times in order to minimize weighted earliness and weighted tardiness. A heuristic / metaheuristic method is proposed to solve it. We propose a mathematical model of mixed integer linear programming and the implementation of the model in Lingo version 17. The proposed method is a genetic algorithm whose initial population consists of solutions obtained from the dispatch rule SPT and random solutions. The algorithm has been implemented in C #. The necessary computational tests have been carried out to evaluate the proposed methods. Statistical evaluations have been performed to calibrate the proposed algorithm. Statistical analyzes indicate that the version of the algorithm that incorporates operators that have the possibility of including idle times is the one that works best.

La programación de la producción en talleres con máquinas en paralelo es especialmente particular ya que puede representar situaciones reales, donde las etapas que son cuello de botella de un proceso contienen varias máquinas para aumentar la capacidad y la productividad. En el problema de programación de máquinas en paralelo hay un conjunto de N = {1,¿,n} trabajos que deben ser procesados en una máquina de un conjunto M = {1,¿,m} de m máquinas en paralelo. El caso mas general de máquinas en paralelo es máquinas no relacionadas donde los tiempos de procesado de cada trabajo dependen de la máquina donde sea asignado el trabajo, este caso es más general que cuando las máquinas son idénticas o uniformes. Cada trabajo debe visitar una máquina y se asume que todas las máquinas son capaces de procesar todos los trabajos. Cada máquina no puede procesar más de un trabajo al mismo tiempo y una vez comenzados los trabajos deben ser procesados hasta completarse. Esto se conoce como no preemption, es decir que los trabajos no pueden ser interrumpidos. El objetivo de minimizar el Adelanto/Tardanza ponderada. Este objeetivo surge de los sistemas de manufactura Justo a Tiempo (JIT). Se desea completar los trabajos tan cerca de la fecha de entrega como sea posible, dado que si se termina los trabajos con adelantado se incurre en costos de inventario si el cliente no acepta el pedido hasta la fecha de entrega y si se termina tarde se incurre en compensaciones hacia el cliente por haber incumplido la fecha de entrega. Para hacer el problema más realista se han agregado fechas de lanzamiento que son los instantes donde un trabajo puede comenzar o estar disponible, debido a que puede estar esperando materia prima o sea el tiempo en que se ha recibido la orden siendo estos solo dos ejemplos. Se consideran también fechas límite o "deadlines" que a diferencia de las fechas de entrega no pueden ser violadas y todos los trabajos deben ser terminados antes de esta fecha, cuando se cuenta con tiempos de lanzamientos y fechas límite el resultado es llamado ¿ventana de procesamiento¿ ya que el tiempo de procesado de un trabajo debe ser completado entre el lanzamiento y la fecha límite. Las fechas límite en general y la ventana de procesamiento afectan que se pueda obtener una programación factible, no todas las secuencias de ordenamiento de los trabajos en las máquinas son posibles, cuando se está trabajando con adelantos/tardanzas conviene incluir una fecha límite para que no retrase los trabajos más allá de esa fecha cuando se está minimizando los adelantos. Los tiempos de preparación son tiempos no productivos que se necesitan en las máquinas para realizar configuraciones o preparaciones y limpiezas para la producción entre los trabajos. Para este trabajo se utilizan tiempos de preparación dependientes de la secuencia de los trabajos y de las máquinas se denota como Sijk el tiempo de preparación necesario en la maquina i cuando se procesa un trabajo j y le sigue un trabajo k en la secuencia. Estos tiempos de preparación son asimétricos, es decir los tiempos de preparación entre un trabajo j y k en una máquina i pueden ser diferentes de tiempos de preparación entre k y j trabajos en la misma máquina. Dado que se desea minimizar los pesos ponderados de adelantos/tardanzas y con tiempos preparación dependientes de la secuencia y la máquina, el orden de asignación de los trabajos se convierte de vital importancia en la programación de máquinas paralelas no relacionadas, ya que dependiendo del orden que se asigna el trabajo, el tiempo de completación cambiará por lo tanto cambiando el adelanto/tardanza. Además, se insertarán tiempos de inactividad para ayudar a la función objetivo principalmente reducir los adelantos. Se propondrá una heurística que permita resolver el problema, probando las variaciones necesarias que permitan hacer las comparaciones si se introduce o no tiempos de inactividad

[CA] Este Treball Final de Màster tracta sobre la programació de la producció en màquines en paral·lel no relacionades, tenint en compte dates de llançament, dates límit, temps de preparació dependents de la seqüència i de la màquina amb l'objectiu de minimitzar els avanços i retards ponderats. Es proposa un mètode heurístico/metaheurístico per a resoldre-ho. Es planteja un model matemàtic de programació lineal sencera mixta i la implementació del model en Lingo versió 17. El mètode proposat és un algoritme genètic la població inicial del qual està composta per solucions obtingudes de la regla de despatx SPT i solucions aleatòries. L'algoritme s'ha implementat en C#. S'han dut a terme les proves computacionals necessàries per a avaluar els mètodes proposats. S'han realitzat avaluacions estadístiques per a calibrar l'algoritme proposat. Les anàlisis estadístiques realitzats indiquen que la versió de l'algoritme que incorpora operadors que tenen la possibilitat d'incloure temps ociosos és la que millor funciona.