Programación de talleres

La programación de talleres , el problema de programación de talleres ( JSP ) o problema de programación de talleres ( JSSP ) es un problema de optimización en ciencias de la computación e investigación operativa . Es una variante de la programación óptima de trabajos . En un problema general de programación de trabajos, se nos dan n trabajos J ₁ , J ₂ , ..., J _n con tiempos de procesamiento variables, que deben programarse en m máquinas con potencia de procesamiento variable, mientras se intenta minimizar el tiempo de finalización ( makespan ), es decir, la duración total de la programación (cuando todos los trabajos han terminado de procesarse). En la variante específica conocida como programación de talleres , cada trabajo consta de un conjunto de operaciones O ₁ , O ₂ , ..., O _n que deben procesarse en un orden específico (conocido como restricciones de precedencia ). Cada operación tiene una máquina específica en la que debe procesarse y solo una operación de un trabajo puede procesarse a la vez. Una práctica habitual es el taller de trabajo flexible , donde cada operación se puede procesar en cualquier máquina de un conjunto determinado (las máquinas de cada conjunto son idénticas).      

El nombre proviene originalmente de la programación de trabajos en un taller , pero el tema tiene amplias aplicaciones más allá de ese tipo de instancia. Es un problema de optimización combinatoria bien conocido y fue el primero en someterse a un análisis competitivo , introducido por Graham en 1966. ^{[ 1 ]} Las mejores instancias del problema para un modelo básico con un objetivo de tiempo de finalización se deben a Taillard. ^{[ 2 ]}

En la notación estándar de tres campos para problemas de programación óptima de trabajos , la variante de taller de trabajo se denota por J en el primer campo. Por ejemplo, el problema denotado por "${\displaystyle J_{3}|p_{ij}|C_{\max }}$" es un problema de taller de 3 máquinas con tiempos de procesamiento unitarios, donde el objetivo es minimizar el tiempo máximo de finalización.

Existen muchas variantes del problema, entre ellas las siguientes:

• Las máquinas pueden tener duplicados (taller de trabajo flexible con máquinas duplicadas) o pertenecer a grupos de máquinas idénticas (taller de trabajo flexible). ^{[ 3 ]}
• Las máquinas pueden requerir un cierto intervalo entre trabajos o no tener tiempo de inactividad.
• Las máquinas pueden tener configuraciones que dependen de la secuencia.
• La función objetivo puede consistir en minimizar el tiempo de finalización, la norma Lp , la tardanza, _la tardanza máxima , etc. También puede tratarse de un problema de optimización multiobjetivo.
• Ciertos trabajos deben completarse antes de que otros puedan comenzar (ver flujo de trabajo ), y los objetivos pueden implicar múltiples criterios. ^{[ 4 ]}
• Un conjunto de tareas puede estar relacionado con un conjunto diferente de máquinas.
• Tiempos de procesamiento deterministas (fijos) o tiempos de procesamiento probabilísticos.

Dado que el problema del viajante es NP-difícil , el problema del taller con configuración dependiente de la secuencia también es NP-difícil, ya que el TSP es un caso especial del JSP con un solo trabajo (el vendedor en el TSP) y las máquinas (las ciudades en el TSP). ^{[ 5 ]}

El grafo disyuntivo ^{[ 6 ]} es uno de los modelos populares utilizados para describir las instancias del problema de programación de talleres. ^{[ 7 ]}

El problema se puede plantear matemáticamente de la siguiente manera:

Dejar${\displaystyle M=\{M_{1},M_{2},\dots ,M_{m}\}}$y${\displaystyle J=\{J_{1},J_{2},\dots,J_{n}\}}$sean dos conjuntos finitos . Debido a los orígenes industriales del problema,${\displaystyle \displaystyle M_ {i}}$se llaman máquinas y la${\displaystyle \displaystyle J_ {j}}$se llaman trabajos .

Dejar${\displaystyle \displaystyle \ {\mathcal {X}}}$denota el conjunto de todas las asignaciones secuenciales de trabajos a máquinas, de modo que cada trabajo es realizado por cada máquina exactamente una vez; elementos${\displaystyle x\in {\mathcal {X}}}$puede escribirse como${\displaystyle n\times m}$matrices, en qué columna${\displaystyle \displaystyle i}$enumera los trabajos que la máquina${\displaystyle \displaystyle M_ {i}}$servirá, en orden. Por ejemplo, la matriz

${\displaystyle x={\begin{pmatrix}1&2\\2&3\\3&1\end{pmatrix}}}$

significa que la máquina${\displaystyle \displaystyle M_ {1}}$hará los tres trabajos${\ Displaystyle \ Displaystyle J_ {1}, J_ {2}, J_ {3}}$en el orden${\ Displaystyle \ Displaystyle J_ {1}, J_ {2}, J_ {3}}$, mientras que la máquina${\displaystyle \displaystyle M_ {2}}$realizarán los trabajos en el orden${\ Displaystyle \ Displaystyle J_ {2}, J_ {3}, J_ {1}}$.

Supongamos también que existe alguna función de coste.${\displaystyle C:{\mathcal {X}}\to [0,+\infty ]}$La función de coste puede interpretarse como un "tiempo total de procesamiento" y puede tener alguna expresión en términos de tiempos.${\displaystyle C_{ij}:M\times J\to [0,+\infty ]}$, el costo/tiempo para la máquina${\displaystyle \displaystyle M_{i}}$hacer trabajo${\displaystyle \displaystyle J_{j}}$.

El problema del taller de trabajo consiste en encontrar una asignación de trabajos.${\displaystyle x\in {\mathcal {X}}}$de tal manera que${\displaystyle \displaystyle C(x)}$es un mínimo, es decir, no hay${\displaystyle y\in {\mathcal {X}}}$de tal manera que${\displaystyle \displaystyle C(x)>C(y)}$.

La eficiencia de la programación se puede definir para una programación mediante la relación entre el tiempo total de inactividad de la máquina y el tiempo total de procesamiento, como se muestra a continuación:

${\displaystyle C'=1+{\sum _{i}l_{i} \over \sum _{j,k}p_{jk}}={C.m \over \sum _{j,k}p_{jk}}}$

Dónde${\displaystyle l_{i}}$representa el tiempo de inactividad de la máquina i , C es el tiempo de finalización y m es el número de máquinas. Esta formulación normaliza el tiempo de finalización por el número de máquinas y el tiempo total de procesamiento, lo que permite comparar la utilización de recursos entre instancias de programación de talleres (JSP) de diferentes tamaños. ^{[ 8 ]}

Uno de los primeros problemas que deben abordarse en el JSP es que muchas soluciones propuestas tienen un costo infinito: es decir, existe${\displaystyle x_{\infty }\in {\mathcal {X}}}$de tal manera que${\displaystyle C(x_{\infty })=+\infty }$De hecho, es bastante sencillo inventar ejemplos de tales cosas.${\displaystyle x_{\infty }}$garantizando que dos máquinas entren en un punto muerto , de modo que cada una espere la salida del siguiente paso de la otra.

Graham introdujo el algoritmo de planificación List en 1966, que es (2 − 1/m)-competitivo, donde m es el número de máquinas. ^{[ 1 ]} Posteriormente se demostró que era el algoritmo óptimo en línea para dos y tres máquinas. El algoritmo Coffman-Graham (1972) para trabajos de longitud uniforme también es óptimo para dos máquinas y (2 − 2/m)-competitivo. ^{[ 9 ] [ 10 ]}

En 1992, Bartal, Fiat, Karloff y Vohra presentaron un algoritmo con una competitividad de 1,986, ^{[ 11 ]} seguido por un algoritmo con una competitividad de 1,945 por Karger, Philips y Torng en 1994. ^{[ 12 ]} Ese mismo año, Albers introdujo un algoritmo diferente con una competitividad de 1,923. ^{[ 13 ]} El mejor resultado conocido es el de Fleischer y Wahl, que alcanzó una relación competitiva de 1,9201. ^{[ 14 ]}

Albers también estableció un límite inferior de 1,852. ^{[ 15 ]} Las instancias de Taillard juegan un papel clave en el desarrollo de la programación de talleres con un objetivo de tiempo de finalización.

En 1976, Garey demostró que este problema es NP-completo para m > 2, lo que significa que no se puede calcular ninguna solución óptima en tiempo polinomial a menos que P=NP . ^{[ 16 ]}

En 2011, Xin Chen et al. proporcionaron algoritmos óptimos para la planificación en línea en dos máquinas relacionadas, mejorando los resultados anteriores. ^{[ 17 ] [ 18 ]}

El aprendizaje automático se ha utilizado recientemente para predecir el tiempo de finalización óptimo de una instancia JSP sin generar realmente la programación óptima. ^{[ 8 ]} Los resultados preliminares muestran una precisión de alrededor del 80 % en la clasificación de pequeñas instancias JSP generadas aleatoriamente según la eficiencia de programación óptima mediante aprendizaje supervisado.

Aquí se muestra un ejemplo de un problema de programación de talleres formulado en AMPL como un problema de programación entera mixta con restricciones indicadoras:

parámetro N_JOBS ; parámetro N_MACHINES ;establecer JOBS ordenados = 1 .. N_JOBS ; establecer MACHINES ordenados = 1 .. N_MACHINES ;param ProcessingTime { JOBS , MACHINES } > 0 ;param TiempoAcumulado { i en TRABAJOS , j en MÁQUINAS } = suma { jj en MÁQUINAS : ord ( jj ) <= ord ( j )} TiempoProcesamiento [ i , jj ];param TimeOffset { i1 en JOBS , i2 en JOBS : i1 <> i2 } = max { j en MACHINES } ( CumulativeTime [ i1 , j ] - CumulativeTime [ i2 , j ] + ProcessingTime [ i2 , j ]);final var >= 0 ; var inicio { TRABAJOS } >= 0 ; var precede a { i1 en TRABAJOS , i2 en TRABAJOS : ord ( i1 ) < ord ( i2 )} binario ;minimizar makestan : fin ;sujeto a makespan_def { i en JOBS }: fin >= inicio [ i ] + suma { j en MACHINES } ProcessingTime [ i , j ];sujeto a no12_conflict { i1 en JOBS , i2 en JOBS : ord ( i1 ) < ord ( i2 )}: precede [ i1 , i2 ] ==> start [ i2 ] >= start [ i1 ] + TimeOffset [ i1 , i2 ];sujeto a no21_conflict { i1 en JOBS , i2 en JOBS : ord ( i1 ) < ord ( i2 )}: ! precede a [ i1 , i2 ] ==> start [ i1 ] >= start [ i2 ] + TimeOffset [ i2 , i1 ];datos ;param N_JOBS : = 4 ; param N_MACHINES : = 4 ;param ProcessingTime : 1 2 3 4 : = 1 5 4 2 1 2 8 3 6 2 3 9 7 2 3 4 3 1 5 8 ;

• La programación de talleres de flujo es un problema similar, pero sin la restricción de que cada operación deba realizarse en una máquina específica (solo se mantiene la restricción del orden).
• La planificación de talleres abiertos es un problema similar, pero también sin la restricción de pedidos.

• Directorio de metodologías, sistemas y software para la optimización dinámica de la Universidad de Viena .
• instancias de Taillard
• Brucker P. Algoritmos de programación . Heidelberg, Springer. Quinta ed. ISBN 978-3-540-24804-0