Programación del taller de trabajo

Para otros usos, consulte Programación .

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 en el que los trabajos se asignan a los recursos en momentos particulares. La versión más básica es la siguiente: Se nos da n empleos J ₁ ,  J ₂ , ...,  J _n de diferentes tiempos de procesamiento, que necesitan ser programado en m máquinas con diferentes potencia de procesamiento, y tratar de minimizar el makespan . El intervalo de tiempo es la duración total de la programación (es decir, cuando todos los trabajos han terminado de procesarse).

La versión estándar del problema es donde tiene n trabajos J ₁ ,  J ₂ , ...,  J _n . Dentro de cada trabajo hay 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 se puede procesar en cualquier máquina de un conjunto dado (las máquinas del conjunto son idénticas).

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]

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.

Se introdujo una notación sistemática para presentar las diferentes variantes de este problema de programación y problemas relacionados, denominada notación de tres campos .

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 espacio 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 del problema

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:

Sean y dos conjuntos finitos . A causa de los orígenes industriales del problema, el son llamados máquinas y el son llamados 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}}$

Deje designar el conjunto de todas las asignaciones secuenciales de puestos de trabajo a las máquinas, de manera que cada trabajo se realiza por todas las máquinas de una sola 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}}$

Suponga 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 para que la máquina haga 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 ​​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 en la 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 la duración 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]${\displaystyle l_{i}}$${\displaystyle i}$${\displaystyle C}$${\displaystyle m}$

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 tales que . De hecho, es bastante simple inventar ejemplos de esto asegurándose de que dos máquinas se bloqueen , 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

Esta sección solo describe un aspecto altamente especializado de su tema asociado . Ayude a mejorar este artículo agregando más información general. La página de discusión puede contener sugerencias. ( Octubre de 2009 )

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

Trabajos atómicos

Ver también: Programación de multiprocesador

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 varias operaciones

La forma básica del problema de programar trabajos con múltiples (M) operaciones, sobre M máquinas, de manera 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

Ver también: regla 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 ;                 

Ver también

• Gráfico disyuntivo
• Programación dinámica
• Programación de Flow Shop
• Programación de algoritmos genéticos
• Lista de problemas NP-completos
• Programación de tienda abierta
• Control optimo
• Programación (procesos de producción)
• Programación de trabajos veraz

Referencias

1. 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 .
2. "Instancias de Taillard" .
3. 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".
4. Malakooti, ​​B (2013). Sistemas de Operaciones y 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 restringe 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 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 .
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 programación". Proc. 24th ACM Symp . 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 problema de programación antiguo" . Proc. Quinto ACM Symp . Algoritmos discretos.
12. 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.
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 Computación . 29 (2): 459–473. CiteSeerX 10.1.1.685.8756 . doi : 10.1137 / S0097539797324874 . 
15. 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 . 
16. 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 .
17. 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 .
18. 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 .   
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 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