La programación del taller de trabajo o el problema del taller de trabajo ( JSP ) es un problema de optimización en la ciencia de la computación y la investigación de operaciones . Es una variante de la programación de trabajos óptima . En un problema general de programación de trabajos, se nos asignan n trabajos J 1 , J 2 , ..., J n de diferentes tiempos de procesamiento, que deben programarse en m máquinas con diferente potencia de procesamiento, mientras intentamos minimizar el tiempo de fabricación.- la duración total de la programación (es decir, cuando todos los trabajos han terminado de procesarse). En la variante específica conocida como programación del taller , cada trabajo consta de un conjunto de operaciones O 1 , O 2 , ..., 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 se puede procesar en cualquier máquina de un conjunto dado (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 Graham presentó el análisis competitivo en 1966. [1] Las mejores instancias de problemas para el modelo básico con objetivo de makepan se deben a Taillard. [2]
En la notación estándar de tres campos para problemas de programación de trabajos óptimos , la variante de taller se indica con J en el primer campo. Por ejemplo, el problema denotado por " J3 ||"es un problema de taller de 3 máquinas con tiempos de procesamiento unitario, donde el objetivo es minimizar el tiempo máximo de finalización.
Variaciones de problemas
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 dependientes de la secuencia.
- La función del objetivo puede ser minimizar el lapso de tiempo, 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 que debo terminar antes de que se pueda iniciar el trabajo j (ver flujo de trabajo ). Además, la función objetivo puede ser multicriterio. [4]
- El 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 vendedor ambulante es NP-difícil , el problema del taller con la 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 requerida ]
Representación de problemas
El gráfico disyuntivo [5] es uno de los modelos populares que se utilizan para describir las instancias de problemas de programación del taller. [6]
Se puede hacer un enunciado matemático del problema de la siguiente manera:
Dejar y ser dos conjuntos finitos . Debido a los orígenes industriales del problema, lase llaman máquinas y lasse llaman trabajos .
Dejar denotar 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; elementos puede escribirse como matrices, en qué columna enumera los trabajos que la máquina Hará, en orden. Por ejemplo, la matriz
significa que la máquina Hará los tres trabajos en el orden , mientras que la máquina hará los trabajos en el orden .
Supongamos también que existe alguna 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 de la máquina hacer trabajo .
El problema del taller es encontrar una asignación de trabajos. tal que es un mínimo, es decir, no hay tal que .
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:
Aquí es el tiempo de inactividad de la máquina , es el makepan y es el número de máquinas. Tenga en cuenta que con la definición anterior, la eficiencia de programación es simplemente el intervalo de tiempo normalizado al número de máquinas y al tiempo total de procesamiento. Esto hace posible comparar el uso de recursos en instancias JSP de diferente tamaño. [7]
El problema del costo infinito
Uno de los primeros problemas que se deben abordar en la JSP es que muchas soluciones propuestas tienen un costo infinito: es decir, existen tal que . De hecho, es bastante sencillo inventar ejemplos de talesasegurándose de que dos máquinas se bloqueen , de modo que cada una espere la salida del siguiente paso de la otra.
Resultados principales
Graham ya había proporcionado el algoritmo de programación List en 1966, que es competitivo (2 - 1 / m ) , 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 competitivo (2 - 2 / m ) . [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 de 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 una relación competitiva de 1.9201. [13]
Albers presentó un límite inferior de 1.852. [14] Las instancias de Taillard desempeñan un papel importante en el desarrollo de la programación del taller de trabajo con el objetivo de lograr un mayor alcance.
En 1976 Garey proporcionó una prueba [15] de que este problema es NP-completo para m> 2, es decir, no se puede calcular una solución óptima en tiempo polinómico 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
Empleos atómicos
La forma más simple del problema de minimización de la capacidad de expansión fuera de línea se refiere a trabajos atómicos, es decir, trabajos que no se subdividen en varias operaciones. Es equivalente 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 minimiza el número de contenedores y se arregla el tamaño del contenedor, el problema se convierte en un problema diferente, conocido como el problema de embalaje del contenedor ).
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 del espacio de trabajo 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, 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 una sola El trabajo no se puede realizar en paralelo, se conoce como el problema de programación del 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 trabajo de 2 máquinas N cuando todos los trabajos deben procesarse en el mismo orden. [20] Los pasos del algoritmo son los siguientes:
Trabajo P i tiene dos operaciones, la duración de P i1 , P i2 , que se realizan en una 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 ,
Quite K de la lista A; Agregue K al final de la Lista L1.
Si el mínimo pertenece a P k2 ,
Quite 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. Ésta es la secuencia óptima.
El método de Johnson solo 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áquinas M, ( M > 2).
La idea es la siguiente: Imagine 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 de procesamiento total para un trabajo P en MC1 = suma (tiempos de operación en las primeras máquinas m / 2) y el tiempo de procesamiento para el trabajo P en MC2 = suma (tiempos de operación en las últimas máquinas m / 2).
Al hacerlo, hemos reducido el problema de la 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 Makespan
El aprendizaje automático se ha utilizado recientemente para predecir el rendimiento ó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 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 del taller de trabajo formulado en AMPL como un problema de programación de enteros mixtos con restricciones de indicador:
param N_JOBS ; param N_MACHINES ;establecer TRABAJOS ordenados = 1 .. N_JOBS ; conjunto MACHINES clasificadas = 1 .. N_MACHINES ; param ProcessingTime { TRABAJOS , MÁQUINAS } > 0 ; param CumulativeTime { i en TRABAJOS , j en MÁQUINAS } = suma { jj en MÁQUINAS : ord ( jj ) <= ord ( j )} ProcessingTime [ i , jj ]; param TimeOffset { i1 en TRABAJOS , i2 en TRABAJOS : i1 <> i2 } = max { j en MÁQUINAS } ( CumulativeTime [ i1 , j ] - CumulativeTime [ i2 , j ] + ProcessingTime [ i2 , j ]); var end > = 0 ; var start { TRABAJOS } > = 0 ; var precede a { i1 en TRABAJOS , i2 en TRABAJOS : ord ( i1 ) < ord ( i2 )} binario ; minimizar makepan : end ; subj to makespan_def { i in JOBS }: end > = start [ i ] + sum { j in MACHINES } ProcessingTime [ i , j ]; sujeto a no12_conflict { i1 en JOBS , i2 en JOBS : ord ( i1 ) < ord ( i2 )}: precede a [ i1 , i2 ] ==> start [ i2 ] > = start [ i1 ] + TimeOffset [ i1 , i2 ]; subj a no21_conflict { i1 en JOBS , i2 en JOBS : ord ( i1 ) < ord ( i2 )}: ! precede a [ i1 , i2 ] ==> inicio [ i1 ] > = inicio [ i2 ] + TimeOffset [ i2 , i1 ]; datos ;param N_JOBS : = 4 ; param N_MACHINES : = 4 ; param ProcessingTime : 1 2 3 4 : = 1 4 2 1 2 3 6 2 3 7 2 3 4 1 5 8 ;
Problemas relacionados
- La programación del 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 de orden).
- La programación de la tienda abierta es un problema similar pero también sin la restricción del pedido.
Ver también
- Gráfico disyuntivo
- Programación dinámica
- Programación de algoritmos genéticos
- Lista de problemas NP-completos
- Control optimo
- Programación (procesos de producción)
Referencias
- ↑ a b Graham, R. (1966). "Límites para determinadas anomalías de multiprocesamiento" (PDF) . Revista técnica de Bell System . 45 (9): 1563-1581. doi : 10.1002 / j.1538-7305.1966.tb01709.x .
- ^ "Instancias de Taillard" .
- ^ Maccarthy (1993). "Abordar la brecha en la programación de la investigación: una revisión de la optimización y métodos heurísticos en la programación de la producción".
- ^ Malakooti, B (2013). Sistemas de Operaciones y Producción con Múltiples Objetivos . John Wiley e hijos. ISBN 978-1-118-58537-5.
- ↑ B. Roy, B. Sussmann, Les problèmes d'ordonnancement avec restringe disjonctives, SEMA, Note DS, No. 9, París, 1964.
- ^ 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.
- ^ a b Mirshekarian, Sadegh; Šormaz, Dušan N. (2016). "Correlación de las características del problema 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 .
- ^ 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.
- ^ 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.
- ^ Bartal, Y .; A. Fiat; H. Karloff; R. Vohra (1992). "Nuevos algoritmos para un antiguo problema de programación". Proc. 24th ACM Symp . Teoría de la Computación. págs. 51–58. doi : 10.1145 / 129712.129718 .
- ^ Karger, D .; S. Phillips; E. Torng (1994). "Un algoritmo mejor para un problema de programación antiguo" . Proc. Quinto ACM Symp . Algoritmos discretos.
- ^ Albers, Susanne ; Torben Hagerup (1992). "Mejor ordenación de enteros paralelos sin escritura concurrente" . Actas del tercer simposio anual ACM-SIAM sobre algoritmos discretos . Archivo Simposio sobre algoritmos discretos. págs. 463–472.
- ^ 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.
- ^ Albers, Susanne (1999). "Mejores límites para la programación en línea". Revista SIAM de Computación . 29 (2): 459–473. CiteSeerX 10.1.1.685.8756 . doi : 10.1137 / S0097539797324874 .
- ^ Garey, MR (1976). "La complejidad de la programación de Flowshop y Jobshop". Matemáticas de la investigación operativa . 1 (2): 117–129. doi : 10.1287 / moor.1.2.117 . JSTOR 3689278 .
- ^ Chen, Xin; Lan, Yan; Benkő, Atila; Dósa, György; Han, Xin (2011). " Algoritmos óptimos para la programación en línea con reordenamiento acotado al final " . Informática Teórica . 412 (45): 6269–6278. doi : 10.1016 / j.tcs.2011.07.014 .
- ^ Liu, M .; Xu, Y .; Chu, C .; Zheng, F. (2009). "Programación en línea en dos máquinas uniformes para minimizar el lapso de tiempo". Theoret. Computación. Sci . 410 (21-23): 2099-2109. doi : 10.1016 / j.tcs.2009.01.007 .
- ^ Hochbaum, Dorit ; Shmoys, David (1987). "Utilización de algoritmos de aproximación dual para la programación de problemas: 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 .
- ^ 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 .
- ^ SM Johnson, programas de producción óptimos en dos y tres etapas con tiempos de preparación incluidos, Naval Res. Tronco. Cuarto de galón. Yo (1954) 61-68.
enlaces externos
- Universidad de Viena Directorio de metodologías, sistemas y software para la optimización dinámica.
- Instancias de Taillard
- Brucker P. algoritmos de programación . Heidelberg, Springer. Quinta ed. ISBN 978-3-540-24804-0
- Programación visual del taller de trabajo