Programación de talleres de trabajo

Problema de optimizacion

La programación de trabajos , el problema de trabajo ( JSP ) o el problema de programación de trabajos ( JSSP ) es un problema de optimización en ciencias de la computación y la investigación de operaciones . Es una variante de la programación óptima del trabajo . 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, al mismo tiempo que se intenta minimizar el intervalo de tiempo : el duración total del programa (es decir, cuando todos los trabajos hayan terminado de procesarse). En la variante específica conocida como programación de taller , cada trabajo consta de un conjunto de operaciones O ₁ ,  O ₂ , ...,  On _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 se puede procesar en cualquier máquina de un conjunto determinado (las máquinas de cada conjunto son idénticas).

El nombre originalmente surgió 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 cual Graham presentó el análisis competitivo en 1966. ^[1] Los mejores ejemplos de problemas para un modelo básico con un objetivo de makepan 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 indica con J en el primer campo. Por ejemplo, el problema indicado por " J3| | ${\displaystyle p_{ij}}$ " 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. ${\displaystyle C_{\max }}$

Variaciones del problema

Existen muchas variaciones 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 que dependen de la secuencia.
• La función objetivo puede ser minimizar el tiempo de preparació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 finalizar antes de poder iniciar el trabajo j (consulte el flujo de trabajo ). Además, la función objetivo puede ser multicriterio. ^[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 es NP-difícil , el problema del taller con configuración dependiente de la secuencia es claramente también NP-difícil 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 necesaria ]}

Representación del problema

El gráfico disyuntivo ^[5] es uno de los modelos populares utilizados para describir los casos de problemas de programación del taller. ^[6]

Un planteamiento matemático del problema se puede hacer de la siguiente manera:

Sean y dos conjuntos finitos . Debido al origen industrial del problema, a las se les llama máquinas y a los empleos . ${\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}}$

Denotemos el conjunto de todas las asignaciones secuenciales de trabajos a máquinas, de modo que cada trabajo sea realizado por cada máquina exactamente una vez; Los elementos se pueden escribir 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 alguna función de costos . 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 tarda la máquina en 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 de trabajo es encontrar una asignación de trabajos tal que sea mínima, es decir, que no exista tal cosa . ${\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 la 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í está el tiempo de inactividad de la máquina , es el makespan y es el número de máquinas. Observe que con la definición anterior, la eficiencia de la programación es simplemente el intervalo de tiempo normalizado al número de máquinas y el tiempo total de procesamiento. Esto hace posible comparar el uso de recursos entre instancias JSP de diferentes tamaños. ^[7] ${\displaystyle l_{i}}$ ${\displaystyle i}$ ${\displaystyle C}$ ${\displaystyle m}$

El problema del coste infinito

Uno de los primeros problemas que debe abordarse en el JSP es que muchas soluciones propuestas tienen un costo infinito: es decir, existen soluciones que . De hecho, es bastante sencillo inventar ejemplos de este tipo asegurándose de que dos máquinas se bloqueen , de modo que cada una espere el resultado 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 de 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 competitivo de 1,945 en 1994. ^[11] En 1992, Albers proporcionó un algoritmo diferente que es competitivo de 1,923. ^[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 trabajos con objetivos de makepan.

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

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

Minimización de makepan sin conexión

Trabajos atómicos

La forma más simple del problema de minimización de makepan fuera de línea se ocupa de trabajos atómicos, es decir, trabajos que no se subdividen en múltiples operaciones. Equivale a empaquetar una cantidad de artículos de varios tamaños diferentes en un número fijo 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 el número de contenedores y se fija el tamaño de los contenedores, el problema se convierte en un problema diferente, conocido como problema de embalaje de contenedores ).

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

Trabajos que constan de múltiples operaciones.

La forma básica del problema de programar trabajos con múltiples (M) operaciones, en 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 una sola El trabajo no se puede realizar en paralelo, lo que se conoce como problema de programación de taller de flujo . 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 de 2 máquinas cuando todos los trabajos deben procesarse en el mismo orden. ^[20] Los pasos del algoritmo son los siguientes:

El trabajo Pi _tiene dos operaciones, de duración Pi1 _, Pi2 _, 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; Agregue K al final de la Lista L1.

Si el mínimo pertenece a P _k2 ,

Eliminar K de la lista A; Agregue K al comienzo de la Lista L2.

• Paso 3. Repita el Paso 2 hasta que la Lista A esté vacía.
• Paso 4. Únase a la Lista L1, Lista L2. Esta es la secuencia óptima.

El método de Johnson sólo funciona de manera ó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áquinas m /2 en un centro de mecanizado (imaginario), MC1, y las máquinas restantes en un centro de mecanizado MC2. Luego, 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 un Trabajo P en MC2 = suma (tiempos de operación en las últimas m /2 máquinas).

Al hacerlo, hemos reducido el problema de m-Machine a un problema de programación de dos centros de mecanizado. Podemos resolver esto usando el método de Johnson.

predicción de makepan

El aprendizaje automático se ha utilizado recientemente para predecir la duración óptima 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 supervisados ​​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 entera mixta con restricciones de indicador:

parámetro N_TRABAJOS ; parámetro N_MACHINES ;  establecer TRABAJOS ordenados = 1 .. N_TRABAJOS ; establecer MÁQUINAS ordenadas = 1 .. N_MAQUINAS ;        param ProcessingTime { TRABAJOS , MÁQUINAS } > 0 ;    param Tiempo acumulativo { i en TRABAJOS , j en MÁQUINAS } = suma { jj en MÁQUINAS : ord ( jj ) <= ord ( j )} Tiempo de procesamiento [ i , jj ];               param TimeOffset { i1 en TRABAJOS , i2 en TRABAJOS : i1 <> i2 } = max { j en MÁQUINAS } ( TiempoAcumulativo [ i1 , j ] - TiempoAcumulativo [ 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 el makepan : fin ;  sujeto a makepan_def { i en TRABAJOS }: fin >= inicio [ i ] + suma { j en MÁQUINAS } Tiempo de procesamiento [ i , j ];           sujeto a no12_conflict { i1 en TRABAJOS , i2 en TRABAJOS : ord ( i1 ) < ord ( i2 )}: precede a [ i1 , i2 ] ==> inicio [ i2 ] >= inicio [ i1 ] + TimeOffset [ i1 , i2 ];                sujeto a no21_conflict { i1 en TRABAJOS , i2 en TRABAJOS : ord ( i1 ) < ord ( i2 )} :! precede a [ i1 , i2 ] ==> inicio [ i1 ] >= inicio [ i2 ] + TimeOffset [ i2 , i1 ];                datos ;parámetro N_TRABAJOS : = 4 ; parámetro N_MAQUINAS : = 4 ;      parámetro Tiempo de procesamiento : 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 taller de flujo 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 tiendas abiertas es un problema similar pero también sin la restricción de pedidos.

Ver también

• Grafo 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 determinadas anomalías de multiprocesamiento" (PDF) . Revista técnica del sistema Bell . 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 de la programación: una revisión de la optimización y los métodos heurísticos en la programación de la producción".
4. Malakooti, ​​B (2013). Operaciones y Sistemas de Producción con Múltiples Objetivos . John Wiley e hijos. 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 gráfica disyuntiva del problema de programación del taller, European Journal of Operational Research, 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 del taller con la eficiencia de la programación" (PDF) . Sistemas Expertos con Aplicaciones . 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 de los casos de dos algoritmos de programación", SIAM Journal on Computing , 6 (3): 518–536, doi :10.1137/0206037, MR  0496614.
10. Bartal, Y.; R. Fiat; H. Karloff; R. Vohra (1992). "Nuevos algoritmos para un antiguo problema de programació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, Susana ; Torben Hagerup (1992). "Clasificación de enteros paralelos mejorada sin escritura simultánea". Actas del tercer simposio anual ACM-SIAM sobre algoritmos discretos . Archivo 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 online". Revista SIAM de Computación . 29 (2): 459–473. CiteSeerX 10.1.1.685.8756 . doi :10.1137/S0097539797324874. 
15. Garey, señor; Johnson, DS; Sethi, Ravi (1976). "La complejidad de la programación de Flowshop y Jobshop". 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 online en dos máquinas uniformes para minimizar el tiempo de preparación". Teoría. Computadora. Ciencia . 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 programació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: Progresos en Inteligencia Artificial . Londres: Springer Verlag . CiteSeerX 10.1.1.29.4699 . 
20. SM Johnson, Programas de producción óptimos de dos y tres etapas con tiempos de preparación incluidos, Naval Res. Registro. Cuarto de galón. I (1954) 61-68.

enlaces externos

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