Programación de talleres de trabajo

Problema de optimización

La programación de trabajos en taller , el problema de trabajo en taller ( JSP ) o problema de programación de trabajos en taller ( JSSP ) es un problema de optimización en informática e investigación de operaciones . 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 de tiempos de procesamiento variables, que deben programarse en m máquinas con potencia de procesamiento variable, mientras se intenta minimizar el makespan - la longitud total de la programación (es decir, cuando todos los trabajos han terminado de procesarse). En la variante específica conocida como programación de trabajos en taller , 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 se puede procesar una operación en un trabajo en un momento dado. Una relajación común es el taller de trabajo flexible , donde cada operación puede procesarse 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 de trabajo , pero el tema tiene amplias aplicaciones más allá de ese tipo de instancia. Este problema es uno de los problemas de optimización combinatoria más conocidos, y fue el primer problema para el que se presentó el análisis competitivo , por Graham en 1966. ^[1] Las mejores instancias de problemas para un modelo básico con un objetivo de makespan 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 se denota con J en el primer campo. Por ejemplo, el problema denotado con " " es un problema de taller de tres máquinas con tiempos de procesamiento unitarios, donde el objetivo es minimizar el tiempo máximo de finalización. ${\displaystyle J_{3}|p_{ij}|C_{\max }}$

Variaciones del problema

Existen muchas variantes del problema, incluidas 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 ningún tiempo de inactividad.
• Las máquinas pueden tener configuraciones dependientes de la secuencia.
• La función objetivo puede ser minimizar el tiempo de ejecución, la norma L p , la tardanza, la tardanza máxima, etc. También puede ser un problema de optimización multiobjetivo.
• Los trabajos pueden tener restricciones, por ejemplo, un trabajo i debe terminar antes de que se pueda iniciar el trabajo j (ver flujo de trabajo ). Además, la función objetivo puede tener múltiples criterios. ^[4]
• Un conjunto de trabajos puede relacionarse con diferentes conjuntos de máquinas.
• Tiempos de procesamiento deterministas (fijos) o tiempos de procesamiento probabilísticos.

Dureza NP

Dado que el problema del viajante de comercio es NP-duro , el problema del taller con una configuración dependiente de la secuencia también es claramente NP-duro, ya que el TSP es un caso especial del JSP con un solo trabajo (las ciudades son las máquinas y el vendedor es el trabajo). ^{[ cita requerida ]}

Representación del problema

El gráfico disyuntivo ^[5] es uno de los modelos populares utilizados para describir las instancias del problema de programación de talleres. ^[6]

El enunciado matemático del problema puede hacerse de la siguiente manera:

Sean y dos conjuntos finitos . Debido al origen industrial del problema, se denominan máquinas y se denominan puestos de trabajo . ${\displaystyle M=\{M_{1},M_{2},\dots ,M_{m}\}}$ ${\displaystyle J=\{J_{1},J_{2},\dots ,J_{n}\}}$ ${\displaystyle \displaystyle M_{i}}$ ${\displaystyle \displaystyle J_{j}}$

Sea el conjunto de todas las asignaciones secuenciales de trabajos a las máquinas, de modo que cada trabajo sea realizado por cada máquina exactamente una vez; los elementos pueden escribirse como matrices, en cuya columna se enumeran los trabajos que realizará la máquina, en orden. Por ejemplo, la matriz ${\displaystyle \displaystyle \ {\mathcal {X}}}$ ${\displaystyle x\in {\mathcal {X}}}$ ${\displaystyle n\times m}$ ${\displaystyle \displaystyle i}$ ${\displaystyle \displaystyle M_{i}}$

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

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

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

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

Eficiencia de programación

La eficiencia de programación se puede definir para una programación a través de 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}}}$

Aquí se muestra el tiempo de inactividad de la máquina i , C es el tiempo de ejecución y m es la cantidad de máquinas. Observe que con la definición anterior, la eficiencia de programación es simplemente el tiempo de ejecución normalizado a la cantidad de máquinas y el tiempo total de procesamiento. Esto permite comparar el uso de recursos en instancias JSP de diferentes tamaños. ^[7] ${\displaystyle l_{i}}$

El problema del coste infinito

Uno de los primeros problemas que se deben abordar en el JSP es que muchas soluciones propuestas tienen un coste infinito: es decir, existe tal que . De hecho, es bastante sencillo inventar ejemplos de este tipo al asegurar que dos máquinas se bloquearán , de modo que cada una espere la salida del siguiente paso de la otra. ${\displaystyle x_{\infty }\in {\mathcal {X}}}$ ${\displaystyle C(x_{\infty })=+\infty }$ ${\displaystyle x_{\infty }}$

Resultados principales

Graham ya había proporcionado el algoritmo de programación de listas en 1966, que es (2 − 1/ m ) -competitivo, donde m es el número de máquinas. ^[1] Además, se demostró que la programación de listas es un algoritmo en línea óptimo para 2 y 3 máquinas. El algoritmo Coffman-Graham (1972) para trabajos de longitud uniforme también es óptimo para dos máquinas y es (2 − 2/ m ) -competitivo. ^{[8] [9]} En 1992, Bartal, Fiat, Karloff y Vohra presentaron un algoritmo que es 1.986-competitivo. ^[10] Karger, Philips y Torng presentaron un algoritmo 1.945-competitivo en 1994. ^[11] En 1992, Albers proporcionó un algoritmo diferente que es 1.923-competitivo. ^[12] Actualmente, el resultado más conocido es un algoritmo dado por Fleischer y Wahl, que logra un ratio competitivo de 1,9201. ^[13]

Albers presentó un límite inferior de 1.852. ^[14] Las instancias de Taillard tienen un papel importante en el desarrollo de la programación de talleres con el objetivo de makespan.

En 1976, Garey proporcionó una prueba ^[15] de que este problema es NP-completo para m>2, es decir, no se puede calcular ninguna solución óptima en tiempo polinomial determinista para tres o más máquinas (a menos que P=NP ).

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

Minimización del tiempo de fabricación fuera de línea

Trabajos atómicos

La forma más simple del problema de minimización de makespan fuera de línea se ocupa de trabajos atómicos, es decir, trabajos que no se subdividen en múltiples operaciones. Es equivalente a empaquetar una cantidad de elementos de distintos tamaños en una cantidad fija de contenedores, de modo que el tamaño máximo de contenedor necesario sea lo más pequeño posible. (Si, en cambio, se debe minimizar la cantidad de contenedores y el tamaño de contenedor es fijo, el problema se convierte en un problema diferente, conocido como el problema de empaquetamiento de contenedores ).

En 1987, Dorit S. Hochbaum y David Shmoys presentaron un esquema de aproximación en tiempo polinomial que encuentra una solución aproximada al problema de minimización de makespan fuera de línea con trabajos atómicos con cualquier grado deseado de precisión. ^[18]

Trabajos que constan de múltiples operaciones

La forma básica del problema de programación de trabajos con múltiples (M) operaciones, sobre M máquinas, de modo que todas las primeras operaciones deben realizarse en la primera máquina, todas las segundas operaciones en la segunda, etc., y un solo trabajo no puede realizarse en paralelo, se conoce como el problema de programación de flujo de trabajo . Existen varios algoritmos, incluidos los algoritmos genéticos . ^[19]

Algoritmo de Johnson

Se puede utilizar un algoritmo heurístico de SM Johnson para resolver el caso de un problema de N trabajos con 2 máquinas cuando todos los trabajos deben procesarse en el mismo orden. ^[20] Los pasos del algoritmo son los siguientes:

El trabajo P _i tiene dos operaciones, de duración P _i1 , P _i2 , que deben realizarse en la máquina M1, M2 en esa secuencia.

• Paso 1. Lista A = { 1, 2, …, N }, Lista L1 = {}, Lista L2 = {}.
• Paso 2. De todas las duraciones de operación disponibles, elija la mínima.

Si el mínimo pertenece a P _k1 ,

Eliminar K de la lista A; añadir K al final de la lista L1.

Si el mínimo pertenece a P _k2 ,

Eliminar K de la lista A; añadir K al comienzo de la lista L2.

• Paso 3. Repita el paso 2 hasta que la Lista A esté vacía.
• Paso 4. Unir la lista L1 con la lista L2. Esta es la secuencia óptima.

El método de Johnson sólo funciona de forma óptima para dos máquinas. Sin embargo, dado que es óptimo y fácil de calcular, algunos investigadores han intentado adoptarlo para M máquinas ( M  > 2).

La idea es la siguiente: imaginemos que cada trabajo requiere m operaciones en secuencia, en M1, M2… Mm. Combinamos las primeras m /2 máquinas en un centro de mecanizado (imaginario), MC1, y las máquinas restantes en un centro de mecanizado MC2. Entonces, el tiempo total de procesamiento para un trabajo P en MC1 = suma (tiempos de operación en las primeras m /2 máquinas), y el tiempo de procesamiento para el trabajo P en MC2 = suma (tiempos de operación en las últimas m /2 máquinas).

De esta manera, hemos reducido el problema de las m-máquinas a un problema de programación de dos centros de mecanizado. Podemos resolverlo utilizando el método de Johnson.

Predicción de Makespan

Recientemente se ha utilizado el aprendizaje automático para predecir el tiempo de ejecución óptimo de una instancia JSP sin producir realmente la programación óptima. ^[7] Los resultados preliminares muestran una precisión de alrededor del 80 % cuando se aplicaron métodos de aprendizaje automático supervisado para clasificar pequeñas instancias JSP generadas aleatoriamente en función de su eficiencia de programación óptima en comparación con el promedio.

Ejemplo

A continuación se muestra un ejemplo de un problema de programación de talleres formulado en AMPL como un problema de programación de números enteros mixtos con restricciones de indicador:

parámetro N_TRABAJOS ; parámetro N_MÁQUINAS ;  establecer TRABAJOS ordenados = 1 .. N_TRABAJOS ; establecer MÁQUINAS ordenadas = 1 .. N_MÁQUINAS ;        param ProcessingTime { TRABAJOS , MÁQUINAS } > 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 TRABAJOS , i2 en TRABAJOS : i1 <> i2 } = max { j en MÁQUINAS } ( TiempoAcumulado [ i1 , j ] - TiempoAcumulado [ i2 , j ] + TiempoDeProcesamiento [ i2 , j ]);                   final var >= 0 ; var inicio { TRABAJOS } >= 0 ; var precede a { i1 en TRABAJOS , i2 en TRABAJOS : ord ( i1 ) < ord ( i2 )} binario ;                minimizar makespan : fin ;  sujeto a makespan_def { i en TRABAJOS }: fin >= inicio [ i ] + suma { j en MÁQUINAS } ProcessingTime [ i , j ];           sujeto a no12_conflicto { i1 en TRABAJOS , i2 en TRABAJOS : ord ( i1 ) < ord ( i2 )}: precede [ i1 , i2 ] ==> inicio [ i2 ] >= inicio [ i1 ] + TimeOffset [ i1 , i2 ];                sujeto a no21_conflicto { i1 en TRABAJOS , i2 en TRABAJOS : ord ( i1 ) < ord ( i2 )}: ! precede [ i1 , i2 ] ==> inicio [ i1 ] >= inicio [ i2 ] + TimeOffset [ i2 , i1 ];                datos ;parámetro N_TRABAJOS : = 4 ; parámetro N_MÁQUINAS : = 4 ;      param TiempoDeProcesamiento : 1 2 3 4 : = 1 5 4 2 1 2 8 3 6 2 3 9 7 2 3 4 3 1 5 8 ;                      

Problemas relacionados

• La programación de flujo de trabajo es un problema similar pero sin la restricción de que cada operación debe realizarse en una máquina específica (solo se mantiene la restricción del orden).
• La programación de tienda abierta es un problema similar pero también sin la restricción de pedido.

Véase también

• Gráfico disyuntivo
• Programación dinámica
• Programación de algoritmos genéticos
• Lista de problemas NP-completos
• Control óptimo
• Programación (procesos de producción)

Referencias

1. Graham, R. (1966). "Límites para ciertas anomalías de multiprocesamiento" (PDF) . Bell System Technical Journal . 45 (9): 1563–1581. doi :10.1002/j.1538-7305.1966.tb01709.x.
2. "Instancias de Taillard".
3. Maccarthy (1993). "Abordar la brecha en la investigación sobre programación: una revisión de los métodos de optimización y heurísticos en la programación de la producción".
4. Malakooti, ​​B (2013). Sistemas de producción y operaciones con objetivos múltiples . John Wiley & Sons. ISBN 978-1-118-58537-5.
5. B. Roy, B. Sussmann, Les problèmes d'ordonnancement avec constraintes disjonctives, SEMA, Note DS, No. 9, París, 1964.
6. Jacek Błażewicz, Erwin Pesch, Małgorzata Sterna, La representación de la máquina de gráficos disyuntivos del problema de programación del taller, Revista Europea de Investigación Operativa, Volumen 127, Número 2, 1 de diciembre de 2000, Páginas 317-331, ISSN 0377-2217, 10.1016/S0377-2217(99)00486-5.
7. Mirshekarian, Sadegh; Šormaz, Dušan N. (2016). "Correlación de las características de los problemas de programación de talleres con la eficiencia de la programación" (PDF) . Expert Systems with Applications . 62 : 131–147. doi :10.1016/j.eswa.2016.06.014.
8. Coffman, EG Jr .; Graham, RL (1972), "Programación óptima para sistemas de dos procesadores" (PDF) , Acta Informatica , 1 (3): 200–213, doi :10.1007/bf00288685, MR  0334913, S2CID  40603807.
9. Lam, Shui; Sethi, Ravi (1977), "Análisis del peor caso de dos algoritmos de programación", SIAM Journal on Computing , 6 (3): 518–536, doi :10.1137/0206037, MR  0496614.
10. Bartal, Y.; A. Fiat; H. Karloff; R. Vohra (1992). "Nuevos algoritmos para un antiguo problema de planificación". Proc. 24.° Simposio ACM . Teoría de la computación. págs. 51–58. doi :10.1145/129712.129718.
11. Karger, D .; S. Phillips; E. Torng (1994). "Un algoritmo mejor para un antiguo problema de programación". Proc. Quinto simposio ACM . Algoritmos discretos.
12. Albers, Susanne ; Torben Hagerup (1992). "Mejora de la ordenación paralela de números enteros sin escritura concurrente". Actas del tercer simposio anual ACM-SIAM sobre algoritmos discretos . Archivo del simposio sobre algoritmos discretos. págs. 463–472.
13. Fleischer, Rudolf (2000). Algoritmos – ESA 2000. Berlín/Heidelberg: Springer. págs. 202-210. doi :10.1007/3-540-45253-2_19. ISBN 978-3-540-41004-1.
14. Albers, Susanne (1999). "Mejores límites para la programación en línea". Revista SIAM de Informática . 29 (2): 459–473. CiteSeerX 10.1.1.685.8756 . doi :10.1137/S0097539797324874. 
15. Garey, MR; Johnson, DS; Sethi, Ravi (1976). "La complejidad de la programación de talleres de flujo y de talleres de trabajo". Matemáticas de la investigación de operaciones . 1 (2): 117–129. doi :10.1287/moor.1.2.117. JSTOR  3689278.
16. Chen, Xin; Lan, Yan; Benkő, Atila; Dósa, György; Han, Xin (2011). "Algoritmos óptimos para programación online con reordenamiento acotado al final". Informática Teórica . 412 (45): 6269–6278. doi : 10.1016/j.tcs.2011.07.014 .
17. Liu, M.; Xu, Y.; Chu, C.; Zheng, F. (2009). "Programación en línea en dos máquinas uniformes para minimizar el tiempo de fabricación". Theoret. Comput. Sci . 410 (21–23): 2099–2109. doi : 10.1016/j.tcs.2009.01.007 .
18. Hochbaum, Dorit ; Shmoys, David (1987). "Uso de algoritmos de aproximación dual para problemas de planificación: resultados teóricos y prácticos" (PDF) . Revista de la ACM . 34 (1): 144–162. CiteSeerX 10.1.1.125.5753 . doi :10.1145/7531.7535. S2CID  9739129. 
19. Khuri, Sami; Miryala, Sowmya Rao (1999). "Algoritmos genéticos para resolver problemas de programación de tiendas abiertas". Actas de la IX Conferencia Portuguesa sobre Inteligencia Artificial: Progreso en Inteligencia Artificial . Londres: Springer Verlag . CiteSeerX 10.1.1.29.4699 . 
20. SM Johnson, Programas óptimos de producción de dos y tres etapas con tiempos de preparación incluidos, Naval Res. Log. Quart. I(1954)61-68.

Enlaces externos

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