stringtranslate.com

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:

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:

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.

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.

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.

Retrasos en el transporte

Varias restricciones

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.

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]

Otras variantes

Véase también

Referencias

  1. ^ ab 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. ^ abc 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