Programación óptima de trabajos

La programación óptima de trabajos es una clase de problemas de optimización relacionados con la programación . Las entradas de tales problemas son una lista de trabajos (también llamados procesos o tareas ) y una lista de máquinas (también llamadas procesadores o trabajadores ). La salida requerida es una programación , una asignación de trabajos a las máquinas. La programación debe optimizar una determinada función objetivo . En la literatura, los problemas de programación óptima de trabajos a menudo se denominan programación de máquinas , programación de procesadores , programación de multiprocesadores o simplemente programación .

Existen muchos problemas diferentes de programación óptima de trabajos, que difieren en la naturaleza de los trabajos, la naturaleza de las máquinas, las restricciones en la programación y la función objetivo. Ronald Graham , Eugene Lawler , Jan Karel Lenstra y Alexander Rinnooy Kan introdujeron una notación conveniente para los problemas de programación óptima . ^{[1] [2]} Consta de tres campos: α , β y γ . Cada campo puede ser una lista de palabras separadas por comas. El campo α describe el entorno de la máquina, β las características y restricciones del trabajo y γ la función objetivo. ^[3] Desde su introducción a fines de la década de 1970, la notación se ha ampliado constantemente, a veces de manera inconsistente. Como resultado, hoy en día hay algunos problemas que aparecen con notaciones distintas en varios artículos.

Trabajos de una sola etapa vs. trabajos de múltiples etapas

En los problemas más simples de programación óptima de trabajos, cada trabajo j consta de una única fase de ejecución, con un tiempo de procesamiento determinado p _j . En variantes más complejas, cada trabajo consta de varias fases de ejecución, que pueden ejecutarse en secuencia o en paralelo.

Entornos de máquinas

En los problemas de programación de trabajos de una sola etapa , hay cuatro categorías principales de entornos de máquina:

• 1 : Programación de una sola máquina . Hay una sola máquina.
• P : Programación de máquinas idénticas . Hay máquinas paralelas y son idénticas. El trabajo lleva tiempo en cualquier máquina en la que esté programado. ${\displaystyle m}$ ${\displaystyle j}$ ${\displaystyle p_{j}}$
• P : Programación uniforme de máquinas . Hay máquinas en paralelo y tienen distintas velocidades. El trabajo en la máquina lleva tiempo . ${\displaystyle m}$ ${\displaystyle j}$ ${\displaystyle i}$ ${\displaystyle p_{j}/s_{i}}$
• R : Programación de máquinas no relacionadas . Hay máquinas paralelas y no están relacionadas. El trabajo en la máquina lleva tiempo . ${\displaystyle m}$ ${\displaystyle j}$ ${\displaystyle i}$ ${\displaystyle p_{ij}}$

Estas letras pueden ir seguidas del número de máquinas, que en ese caso es fijo. Por ejemplo, P2 indica que hay dos máquinas idénticas en paralelo. Pm indica que hay m máquinas idénticas en paralelo, donde m es un parámetro fijo. Por el contrario, P indica que hay m máquinas idénticas en paralelo, pero m no es fijo (es parte de la entrada).

En problemas de programación de trabajos de varias etapas , existen otras opciones para los entornos de la máquina:

• O : Problema de taller abierto . Cada trabajo consta de operaciones para . Las operaciones se pueden programar en cualquier orden. La operación debe procesarse para las unidades en la máquina . ${\displaystyle j}$ ${\displaystyle m}$ ${\displaystyle O_{ij}}$ ${\displaystyle i=1,\ldots ,m}$ ${\displaystyle O_{ij}}$ ${\displaystyle p_{ij}}$ ${\displaystyle i}$
• F : Problema de flujo de trabajo . Cada trabajo consta de operaciones para , que se deben programar en el orden indicado . La operación debe procesarse para las unidades en la máquina . ${\displaystyle j}$ ${\displaystyle m}$ ${\displaystyle O_{ij}}$ ${\displaystyle i=1,\ldots ,m}$ ${\displaystyle O_{ij}}$ ${\displaystyle p_{ij}}$ ${\displaystyle i}$
• J : Problema de taller . Cada trabajo consta de operaciones para , que se deben programar en ese orden. La operación debe procesarse para unidades en una máquina dedicada con para . ${\displaystyle j}$ ${\displaystyle n_{j}}$ ${\displaystyle O_{kj}}$ ${\displaystyle k=1,\ldots ,n_{j}}$ ${\displaystyle O_{kj}}$ ${\displaystyle p_{kj}}$ ${\displaystyle \mu _{kj}}$ ${\displaystyle \mu _{kj}\neq \mu _{k'j}}$ ${\displaystyle k\neq k'}$

Características del puesto

Se supone que todos los tiempos de procesamiento son números enteros. Sin embargo, en algunos artículos de investigación más antiguos se supone que son números racionales.

• ${\displaystyle p_{i}=p}$, o bien : el tiempo de procesamiento es igual para todos los trabajos. ${\displaystyle p_{ij}=p}$
• ${\displaystyle p_{i}=1}$, o bien : el tiempo de procesamiento es igual a 1 unidad de tiempo para todos los trabajos. ${\displaystyle p_{ij}=1}$
• ${\displaystyle r_{j}}$:para cada trabajo se da un tiempo de liberación antes del cual no se puede programar, el valor predeterminado es 0.
• ${\displaystyle {\text{online-}}r_{j}}$: un problema en línea. Los trabajos se revelan en el momento de su lanzamiento. En este contexto, el rendimiento de un algoritmo se mide por su índice de competitividad .
• ${\displaystyle d_{j}}$: para cada trabajo se da una fecha de vencimiento. La idea es que cada trabajo debe completarse antes de su fecha de vencimiento y existe una penalización para los trabajos que se completan tarde. Esta penalización se denota en el valor objetivo. La presencia de la característica del trabajo se asume implícitamente y no se denota en el nombre del problema, a menos que haya algunas restricciones como, por ejemplo , suponer que todas las fechas de vencimiento son iguales a una fecha determinada. ${\displaystyle d_{j}}$ ${\displaystyle d_{j}=d}$
• ${\displaystyle {\bar {d}}_{j}}$:Para cada trabajo se establece una fecha límite estricta. Todos los trabajos deben completarse antes de la fecha límite.
• pmtn : los trabajos pueden interrumpirse y reanudarse posiblemente en otra máquina. A veces también se indica con " prmp ".
• ${\displaystyle {\text{size}}_{j}}$:Cada trabajo viene con una cantidad de máquinas en las que debe programarse al mismo tiempo. El valor predeterminado es 1. Este es un parámetro importante en la variante denominada programación de tareas paralelas .

Relaciones de precedencia

Cada par de dos trabajos puede tener o no una relación de precedencia. Una relación de precedencia entre dos trabajos significa que un trabajo debe terminarse antes que el otro. Por ejemplo, si el trabajo i es predecesor del trabajo j en ese orden, el trabajo j solo puede comenzar una vez que el trabajo i se haya completado.

• prec : No hay restricciones sobre las relaciones de precedencia.
• cadenas : cada trabajo es el predecesor de como máximo otro trabajo y es precedido por como máximo otro trabajo.
• árbol: Las relaciones de precedencia deben satisfacer una de las dos restricciones.
  • intree: Cada nodo es el predecesor de como máximo otro trabajo.
  • outtree: cada nodo está precedido por, como máximo, otro trabajo.
• bosque opuesto: si el gráfico de relaciones de precedencia se divide en componentes conectados , entonces cada componente conectado es un árbol interno o externo.
• sp-graph: El gráfico de relaciones de precedencia es un gráfico en serie paralelo .
• altura limitada : la longitud de la ruta dirigida más larga está limitada a un valor fijo. (Una ruta dirigida es una secuencia de trabajos donde cada trabajo, excepto el último, es predecesor del siguiente trabajo en la secuencia).
• Orden de nivel : cada trabajo tiene un nivel, que es la longitud de la ruta dirigida más larga que comienza desde ese trabajo. Cada trabajo con nivel es un predecesor de cada trabajo con nivel . ${\displaystyle k}$ ${\displaystyle k-1}$
• orden de intervalo : cada trabajo tiene un intervalo [ s _x , e _x ) y el trabajo es un predecesor de si y solo si el final del intervalo de es estrictamente menor que el inicio del intervalo para .= ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle x}$ ${\displaystyle y}$

En presencia de una relación de precedencia, se podría suponer además que hay desfases temporales . El desfase temporal entre dos trabajos es la cantidad de tiempo que se debe esperar después de que se completa el primer trabajo antes de que comience el segundo. Formalmente, si el trabajo i precede al trabajo j, entonces debe ser verdadero. Si no se especifica ningún desfase temporal , se supone que es cero. Los desfases temporales también pueden ser negativos. Un desfase temporal negativo significa que el segundo trabajo puede comenzar un tiempo fijo antes de que finalice el primero. ${\displaystyle C_{i}+\ell _{ij}\leq S_{j}}$ ${\displaystyle \ell _{ij}}$

• ℓ : El desfase temporal es el mismo para cada par de trabajos.
• ${\displaystyle \ell _{ij}}$:Distintos pares de trabajos pueden tener distintos desfases temporales.

Retrasos en el transporte

• ${\displaystyle t_{jk}}$:Entre la finalización de la operación del trabajo en la máquina y el inicio de la operación del trabajo en la máquina , hay un retraso en el transporte de al menos unidades. ${\displaystyle O_{kj}}$ ${\displaystyle j}$ ${\displaystyle k}$ ${\displaystyle O_{k+1,j}}$ ${\displaystyle j}$ ${\displaystyle k+1}$ ${\displaystyle t_{jk}}$
• ${\displaystyle t_{jkl}}$:Entre la finalización de la operación del trabajo en la máquina y el inicio de la operación del trabajo en la máquina , hay un retraso en el transporte de al menos unidades. ${\displaystyle O_{kj}}$ ${\displaystyle j}$ ${\displaystyle k}$ ${\displaystyle O_{l,j}}$ ${\displaystyle j}$ ${\displaystyle l}$ ${\displaystyle t_{jkl}}$
• ${\displaystyle t_{k}}$:Retraso en el transporte que depende de la máquina. Entre la finalización de la operación del trabajo en la máquina y el inicio de la operación del trabajo en la máquina , hay un retraso en el transporte de al menos unidades. ${\displaystyle O_{kj}}$ ${\displaystyle j}$ ${\displaystyle k}$ ${\displaystyle O_{k+1,j}}$ ${\displaystyle j}$ ${\displaystyle k+1}$ ${\displaystyle t_{k}}$
• ${\displaystyle t_{kl}}$:Retraso de transporte dependiente del par de máquinas. Entre la finalización de la operación del trabajo en la máquina y el inicio de la operación del trabajo en la máquina , hay un retraso de transporte de al menos unidades. ${\displaystyle O_{kj}}$ ${\displaystyle j}$ ${\displaystyle k}$ ${\displaystyle O_{l,j}}$ ${\displaystyle j}$ ${\displaystyle l}$ ${\displaystyle t_{kl}}$
• ${\displaystyle t_{j}}$:Retraso en el transporte que depende del trabajo. Entre la finalización de la operación del trabajo en la máquina y el inicio de la operación del trabajo en la máquina , hay un retraso en el transporte de al menos unidades. ${\displaystyle O_{kj}}$ ${\displaystyle j}$ ${\displaystyle k}$ ${\displaystyle O_{l,j}}$ ${\displaystyle j}$ ${\displaystyle l}$ ${\displaystyle t_{j}}$

Varias restricciones

• rcrc : También conocido como Recirculación o taller de trabajo flexible. La promesa de se levanta y para algunos pares podríamos tener . En otras palabras, es posible que se asignen diferentes operaciones del mismo trabajo a la misma máquina. ${\displaystyle \mu }$ ${\displaystyle k\neq k'}$ ${\displaystyle \mu _{kj}=\mu _{k'j}}$
• no-wait : la operación debe comenzar exactamente cuando se completa la operación. En otras palabras, una vez que finaliza una operación de un trabajo, la siguiente operación debe comenzar inmediatamente. A veces también se denota como ' nwt' . ${\displaystyle O_{k+1,i}}$ ${\displaystyle O_{k,i}}$
• no-idle : ninguna máquina puede estar inactiva entre el inicio de su primera ejecución hasta el final de su última ejecución.
• ${\displaystyle {\text{size}}_{j}}$: Tareas multiprocesador en máquinas paralelas idénticas. La ejecución de la tarea se realiza simultáneamente en máquinas paralelas. ${\displaystyle j}$ ${\displaystyle {\text{size}}_{j}}$
• ${\displaystyle {\text{fix}}_{j}}$: Tareas multiprocesador. Cada tarea se asigna a un conjunto de máquinas y necesita todas estas máquinas simultáneamente para su ejecución. A veces también se denomina "MPT". ${\displaystyle j}$ ${\displaystyle {\text{fix}}_{j}\subseteq \{1,\ldots ,m\}}$
• ${\displaystyle M_{j}}$:Máquinas multipropósito. Cada trabajo debe programarse en una máquina de un conjunto determinado . A veces también se denota por M _j . ${\displaystyle j}$ ${\displaystyle M_{j}\subseteq \{1,\ldots ,m\}}$

Funciones objetivas

Por lo general, el objetivo es minimizar algún valor objetivo. Una diferencia es la notación , donde el objetivo es maximizar la cantidad de trabajos que se completan antes de la fecha límite. Esto también se denomina rendimiento . El valor objetivo se puede sumar, posiblemente ponderado por algunos pesos de prioridad determinados por trabajo. ${\displaystyle \sum U_{j}}$ ${\displaystyle w_{j}}$

• - : La ausencia de un valor objetivo se indica con un solo guión. Esto significa que el problema consiste simplemente en producir una programación factible que satisfaga todas las restricciones dadas.
• ${\displaystyle C_{j}}$: el tiempo de finalización del trabajo es el tiempo máximo de finalización; también conocido como makespan . A veces nos interesa el tiempo medio de finalización (el promedio de todos los j ), que a veces se denota por mft (tiempo medio de finalización). ^[4] ${\displaystyle j}$ ${\displaystyle C_{\max }}$ ${\displaystyle C_{j}}$
• ${\displaystyle F_{j}}$:El tiempo de flujo de un trabajo es la diferencia entre su tiempo de finalización y su tiempo de liberación, es decir . ${\displaystyle F_{j}=C_{j}-r_{j}}$
• ${\displaystyle L_{j}}$: Retraso . A cada trabajo se le asigna una fecha de vencimiento . El retraso de un trabajo se define como . A veces se utiliza para indicar la viabilidad de un problema con plazos. De hecho, al utilizar la búsqueda binaria, la complejidad de la versión de viabilidad es equivalente a la minimización de . ${\displaystyle j}$ ${\displaystyle d_{j}}$ ${\displaystyle j}$ ${\displaystyle C_{j}-d_{j}}$ ${\displaystyle L_{\max }}$ ${\displaystyle L_{\max }}$
• ${\displaystyle U_{j}}$: Rendimiento . A cada trabajo se le asigna una fecha de vencimiento . Existe una ganancia unitaria para los trabajos que se completan a tiempo, es decir, si y en caso contrario. A veces, el significado de se invierte en la literatura, lo que es equivalente cuando se considera la versión de decisión del problema, pero que marca una gran diferencia para las aproximaciones. ${\displaystyle d_{j}}$ ${\displaystyle U_{j}=1}$ ${\displaystyle C_{j}\leq d_{j}}$ ${\displaystyle U_{j}=0}$ ${\displaystyle U_{j}}$
• ${\displaystyle T_{j}}$: Retraso . Cada trabajo tiene una fecha de entrega . El retraso de un trabajo se define como . ${\displaystyle j}$ ${\displaystyle d_{j}}$ ${\displaystyle j}$ ${\displaystyle T_{j}=\max\{0,C_{j}-d_{j}\}}$
• ${\displaystyle E_{j}}$: Precocidad . Cada trabajo tiene una fecha de entrega . La precocidad de un trabajo se define como . Este objetivo es importante para la programación justo a tiempo. ${\displaystyle j}$ ${\displaystyle d_{j}}$ ${\displaystyle j}$ ${\displaystyle E_{j}=\max\{0,d_{j}-C_{j}\}}$

También existen variantes con objetivos múltiples , pero están mucho menos estudiadas. ^[2]

Ejemplos

A continuación se presentan algunos ejemplos de problemas definidos utilizando la notación anterior. ^[1]

• ${\displaystyle P_{2}\parallel C_{\max }}$– asignar cada uno de los trabajos dados a una de las dos máquinas idénticas para minimizar el tiempo máximo total de procesamiento en las máquinas. Esta es una versión optimizada del problema de partición ${\displaystyle n}$
• 1|prec| – asignar a una sola máquina, procesos con restricción de precedencia general, minimizando la demora máxima. ${\displaystyle L_{\max }}$
• R|pmtn| – asigna tareas a un número variable de máquinas paralelas no relacionadas, lo que permite la prelación y minimiza el tiempo total de finalización. ${\displaystyle \sum C_{i}}$
• J3| | – 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 p_{ij}=1}$ ${\displaystyle C_{\max }}$
• ${\displaystyle P\mid {\text{size}}_{j}\mid C_{\max }}$– asignar tareas a máquinas idénticas en paralelo, donde cada tarea viene con una cantidad de máquinas en las que debe programarse al mismo tiempo, minimizando así el tiempo máximo de finalización. Ver programación de tareas en paralelo . ${\displaystyle m}$

Otras variantes

• Todas las variantes estudiadas anteriormente son deterministas, en el sentido de que el planificador conoce todos los datos. También existen variantes estocásticas , en las que los datos no se conocen de antemano o pueden alterarse de forma aleatoria. ^[2]
• En un juego de equilibrio de carga , cada trabajo pertenece a un agente estratégico, que puede decidir dónde programar su trabajo. El equilibrio de Nash en este juego puede no ser óptimo. Aumann y Dombb ^[5] evalúan la ineficiencia del equilibrio en varios juegos de equilibrio de carga.

Véase también

• Programación de trabajos fraccionada

Referencias

1. Graham, RL; Lawler, EL; Lenstra, JK; Rinnooy Kan, AHG (1979). "Optimización y aproximación en secuenciación y programación deterministas: una encuesta" (PDF) . Actas del Instituto de Investigación Avanzada sobre Optimización Discreta y Aplicaciones de Sistemas del Panel de Ciencia de Sistemas de la OTAN y del Simposio de Optimización Discreta . Elsevier. págs. (5) 287–326.
2. Eugene L. Lawler, Jan Karel Lenstra, Alexander HG Rinnooy Kan, David B. Shmoys (1 de enero de 1993). "Capítulo 9 Secuenciación y programación: algoritmos y complejidad". Manuales de investigación de operaciones y ciencia de la gestión . 4 : 445–522. doi :10.1016/S0927-0507(05)80189-6. ISBN 9780444874726. ISSN  0927-0507.{{cite journal}}: CS1 maint: multiple names: authors list (link)
3. B. Chen, CN Potts y GJ Woeginger . "Una revisión de la programación de máquinas: complejidad, algoritmos y aproximabilidad". Handbook of Combinatorial Optimization (volumen 3) (Editores: D.-Z. Du y P. Pardalos), 1998, Kluwer Academic Publishers. 21-169. ISBN 0-7923-5285-8 (HB) 0-7923-5019-7 (Set) 
4. Horowitz, Ellis; Sahni, Sartaj (1 de abril de 1976). "Algoritmos exactos y aproximados para la programación de procesadores no idénticos". Revista de la ACM . 23 (2): 317–327. doi : 10.1145/321941.321951 . ISSN  0004-5411. S2CID  18693114.
5. Aumann, Yonatan; Dombb, Yair (2010). Kontogiannis, Spyros; Koutsoupias, Elias; Spirakis, Paul G. (eds.). "Eficiencia de Pareto y eficiencia de Pareto aproximada en juegos de enrutamiento y balanceo de carga". Teoría de juegos algorítmicos . Apuntes de clase en informática. Berlín, Heidelberg: Springer: 66–77. doi :10.1007/978-3-642-16170-4_7. ISBN 978-3-642-16170-4.

Enlaces externos

• Zoológico de programación (por Christoph Dürr, Sigrid Knust, Damien Prot, Óscar C. Vásquez): una herramienta en línea para buscar un problema de programación óptimo utilizando la notación.
• Resultados de complejidad para problemas de programación (por Peter Brucker, Sigrid Knust): una clasificación de problemas de programación óptimos según lo que se conoce sobre su complejidad en tiempo de ejecución.