Programación óptima del trabajo

La programación óptima de trabajos es una clase de problemas de optimización relacionados con la programación . Las entradas a 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 ). El resultado requerido es un cronograma : una asignación de trabajos a las máquinas. El cronograma 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áquina , programación de procesador , programación multiprocesador o simplemente programación .

Hay muchos problemas diferentes de programación óptima de trabajos, diferentes en la naturaleza de los trabajos, la naturaleza de las máquinas, las restricciones en el cronograma y la función objetivo. Ronald Graham , Eugene Lawler , Jan Karel Lenstra y Alexander Rinnooy Kan introdujeron una notación conveniente para 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 finales de la década de 1970, la notación se ha ampliado constantemente, a veces de forma inconsistente. Como resultado, hoy en día existen algunos problemas que aparecen con notaciones distintas en varios artículos.

Trabajos de una sola etapa versus trabajos de varias 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 dado 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 , existen 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 para la que esté programado. ${\displaystyle m}$ ${\displaystyle j}$ ${\displaystyle p_{j}}$
• P : Programación de máquinas uniformes . Hay máquinas paralelas y tienen diferentes velocidades dadas. 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 luego se fija. Por ejemplo, P2 indica que hay dos máquinas idénticas paralelas. Pm indica que hay m máquinas idénticas paralelas, donde m es un parámetro fijo. Por el contrario, P indica que hay m máquinas idénticas paralelas, pero m no es fija (es parte de la entrada).

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

• O : Problema de tienda abierta . 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 taller de flujo . Cada trabajo consta de operaciones que se programarán en el orden dado . 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 del taller de trabajo . Cada trabajo consta de operaciones que se programarán en ese orden. La operación debe procesarse para unidades en una máquina dedicada con for . ${\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 trabajos de investigación más antiguos se supone que son racionales.

• ${\displaystyle p_{i}=p}$, o : el tiempo de procesamiento es igual para todos los trabajos. ${\displaystyle p_{ij}=p}$
• ${\displaystyle p_{i}=1}$, o : 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 proporciona 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 sus momentos de publicación. En este contexto, el rendimiento de un algoritmo se mide por su ratio competitivo .
• ${\displaystyle d_{j}}$: para cada trabajo se proporciona una fecha de vencimiento. La idea es que cada trabajo debe completarse antes de su fecha de vencimiento y existe alguna penalización por 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 indica en el nombre del problema, a menos que existan algunas restricciones como, por ejemplo , suponiendo que todas las fechas de vencimiento sean iguales a una fecha determinada. ${\displaystyle d_{j}}$ ${\displaystyle d_{j}=d}$
• ${\displaystyle {\bar {d}}_{j}}$: para cada trabajo se da un plazo estricto. Cada trabajo debe completarse antes de su fecha límite.
• pmtn : los trabajos se pueden adelantar y posiblemente reanudar en otra máquina. A veces también se indica con ' prmp '.
• ${\displaystyle {\text{size}}_{j}}$: Cada trabajo viene con un número de máquinas en las que se debe programar al mismo tiempo. El valor predeterminado es 1. Este es un parámetro importante en la variante llamada 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 finalizar antes que el otro. Por ejemplo, si el trabajo i es un predecesor del trabajo j en ese orden, el trabajo j solo puede comenzar una vez que se completa el trabajo i.

• prec : No existen restricciones sobre las relaciones de precedencia.
• cadenas : cada trabajo es el predecesor de como máximo otro trabajo y está precedido como máximo por 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 como máximo por 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 paralelo en serie .
• altura limitada : la longitud de la ruta dirigida más larga tiene un límite de un valor fijo. (Una ruta dirigida es una secuencia de trabajos donde cada trabajo, excepto el último, es un 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 a partir de 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ían suponer además desfases temporales . El intervalo de tiempo 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 retraso , se supone que es cero. Los desfases temporales también pueden ser negativos. Un retraso de tiempo negativo significa que el segundo trabajo puede comenzar en un tiempo fijo antes de que finalice el primer trabajo. ${\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}}$: Diferentes pares de trabajos pueden tener diferentes desfases.

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 dependiente 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 en el 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 en el 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 dependiente 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 limitaciones

• rcrc : También conocido como Recirculación o taller de trabajo flexible. La promesa se ha levantado y para algunos pares podríamos tener . En otras palabras, es posible asignar 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 denomina ' nwt' . ${\displaystyle O_{k+1,i}}$ ${\displaystyle O_{k,i}}$
• no-idle : Ninguna máquina puede estar inactiva desde 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 del trabajo se realiza simultáneamente en máquinas paralelas. ${\displaystyle j}$ ${\displaystyle {\text{size}}_{j}}$
• ${\displaystyle {\text{fix}}_{j}}$: Tareas multiprocesador. Cada trabajo se realiza con un conjunto de máquinas y necesita simultáneamente todas estas máquinas para su ejecución. A veces también se indica con 'MPT'. ${\displaystyle j}$ ${\displaystyle {\text{fix}}_{j}\subseteq \{1,\ldots ,m\}}$
• ${\displaystyle M_{j}}$: Máquinas polivalentes. 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

Generalmente el objetivo es minimizar algún valor objetivo. Una diferencia es la notación en la que el objetivo es maximizar la cantidad de trabajos que se completan antes de la fecha límite. Esto también se llama rendimiento . El valor objetivo se puede sumar, posiblemente ponderado por algunas ponderaciones de prioridad dadas 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 makepan . A veces nos interesa el tiempo medio de finalización (el promedio de 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}}$: Tardanza . Cada trabajo tiene una fecha de vencimiento . La tardanza en el trabajo se define como . A veces se utiliza para denotar la viabilidad de un problema con los 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 . Cada trabajo tiene una fecha de vencimiento . Hay una ganancia unitaria para los trabajos que se completan a tiempo, es decir, si y no. 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 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}}$: Tardanzas . Cada trabajo tiene una fecha de vencimiento . La tardanza en el 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 vencimiento . La precocidad del 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 múltiples objetivos , pero están mucho menos estudiadas. ^[2]

Ejemplos

A continuación se muestran 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 total máximo de procesamiento en las máquinas. Esta es una versión optimizada del problema de la partición. ${\displaystyle n}$
• 1|preparación| – asignar a una sola máquina procesos con restricción de precedencia general, minimizando el retraso máximo. ${\displaystyle L_{\max }}$
• R|pmtn| – asignar tareas a un número variable de máquinas paralelas no relacionadas, permitiendo la preferencia y minimizando 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}\mid C_{\max }}$
• ${\displaystyle P\mid {\text{size}}_{j}\mid C_{\max }}$– asignar trabajos a máquinas idénticas en paralelo, donde cada trabajo viene con una cantidad de máquinas en las que debe programarse al mismo tiempo, minimizando el tiempo máximo de finalización. Consulte programación de tareas paralelas . ${\displaystyle m}$

Otras variantes

• Todas las variantes examinadas 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 aleatoriamente. ^[2]
• En un juego de equilibrio de carga , cada trabajo pertenece a un agente estratégico, quien 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.

Ver también

• Programación de trabajo 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 ciencias de la gestión . 4 : 445–522. doi :10.1016/S0927-0507(05)80189-6. ISBN 9780444874726. ISSN  0927-0507.{{cite journal}}: Mantenimiento CS1: varios nombres: lista de autores ( enlace )
3. B. Chen, CN Potts y GJ Woeginger . "Una revisión de la programación de máquinas: complejidad, algoritmos y proximidad". Manual de optimización combinatoria (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 (Juego) 
4. Horowitz, Ellis; Sahni, Sartaj (1 de abril de 1976). "Algoritmos exactos y aproximados para programar 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, Elías; Spirakis, Paul G. (eds.). "Eficiencia de Pareto y eficiencia de Pareto aproximada en juegos de enrutamiento y equilibrio de carga". Teoría algorítmica de juegos . Apuntes de conferencias sobre 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 óptima 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.