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 llamados procesadores o trabajadores ). La salida requerida es un programa , una asignación de trabajos a las máquinas. El horario debe optimizar una determinada función objetivo . En la literatura, los problemas de la programación óptima de trabajos a menudo se denominan programación de máquinas , programación de procesadores , programación de multiprocesadores., o simplemente programar .
Hay muchos problemas diferentes para la programación óptima de trabajos, diferentes en la naturaleza de los trabajos, la naturaleza de las máquinas, las restricciones en el horario 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 limitaciones 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 extendido constantemente, a veces de manera inconsistente. Como resultado, hoy en día existen algunos problemas que aparecen con notaciones distintas en varios artículos.
Trabajos de una etapa frente a trabajos de varias etapas
En los problemas de programación de trabajos óptimos más simples, 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áquinas:
- 1 : hay una sola máquina. Consulte la programación de una sola máquina .
- P : haymáquinas paralelas, y son idénticas. Trabajo requiere tiempo en cualquier máquina para la que esté programado.
- Q : haymáquinas paralelas, y tienen diferentes velocidades dadas. Trabajo en la máquina requiere tiempo . Consulte la programación uniforme de la máquina .
- R : hay máquinas paralelas, y no están relacionadas - Job en la máquina requiere tiempo .
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 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 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 consiste en operaciones por . Las operaciones se pueden programar en cualquier orden. Operación debe ser procesado para unidades en la máquina .
- F : Problema de flow-shop . Cada trabajo consiste en operaciones por , que se programará en el orden indicado . Operación debe ser procesado para unidades en la máquina .
- J : Problema de taller . Cada trabajo consiste en operaciones por , que se programará en ese orden. Operación debe ser procesado para unidades en una máquina dedicada con por .
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 asume que son racionales.
- , o : el tiempo de procesamiento es igual para todos los trabajos.
- , o : el tiempo de procesamiento es igual a 1 unidad de tiempo para todos los trabajos.
- : para cada trabajo se da un tiempo de liberación antes del cual no se puede programar, el valor predeterminado es 0.
- : un problema en línea. Los trabajos se revelan en sus tiempos de lanzamiento. En este contexto, el rendimiento de un algoritmo se mide por su relación competitiva .
- : para cada trabajo se da una fecha de vencimiento. La idea es que todos los trabajos deben completarse antes de la fecha de vencimiento y hay una multa 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 indica en el nombre del problema, a menos que existan algunas restricciones como, por ejemplo, , asumiendo que todas las fechas de vencimiento son iguales a alguna fecha dada.
- : para cada trabajo se da un plazo estricto. Cada trabajo debe completarse antes de su fecha límite.
- pmtn : Los trabajos se pueden interrumpir y reanudar posiblemente en otra máquina. A veces también se denota por ' prmp '.
- : Cada trabajo viene con una serie 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
Se pueden dar relaciones de precedencia para los trabajos, en forma de orden parcial, lo que significa que si i es un predecesor de i 'en ese orden, i' puede comenzar solo cuando i se completa.
- prec : Relación de precedencia general dada. Si luego la hora de inicio de no debe ser anterior a la hora de finalización de .
- cadenas : relación de precedencia dada en forma de cadenas (los grados y los grados son como máximo 1).
- árbol: relación de precedencia general dada en forma de árbol, ya sea dentro o fuera del árbol.
- intree: relación de precedencia general dada en forma de intree (los grados externos son como máximo 1).
- árbol externo: relación de precedencia general dada en forma de árbol externo (los grados son como máximo 1).
- bosque opuesto: relación de precedencia general dada en forma de una colección de árboles internos y externos.
- sp-graph: Relación de precedencia dada en forma de un gráfico paralelo en serie.
- altura acotada : Relación de precedencia dada donde el camino dirigido más largo está acotado por una constante.
- orden de nivel : Relación de precedencia dada donde cada vértice de un nivel dado l (es decir, la longitud del camino dirigido más largo que comienza desde este vértice es l) es un predecesor de todos los vértices del nivel l-1.
- orden de intervalo : Relación de precedencia dada para la cual se puede asociar a cada vértice un intervalo en la línea real, y hay precedencia entre xey si y solo si los intervalos semiabiertos x = [s_x, e_x) e y = [s_y , e_y) son tales que e_x es menor o igual que s_y.
- orden de cuasi intervalo: las órdenes de cuasi intervalo son una superclase de órdenes de intervalo definidas en Moukrim: Programación óptima en máquinas paralelas para una nueva clase de orden, Operations Research Letters, 24 (1): 91-95, 1999.
- orden de sobreintervalo: las órdenes de sobreintervalo son una superclase de órdenes de cuasi intervalo definidas en Chardon y Moukrim: el algoritmo de Coffman-Graham resuelve de manera óptima los sistemas de tareas UET con órdenes de sobreintervalo, SIAM Journal on Discrete Mathematics, 19 (1): 109 121, 2005.
- Orden am: las órdenes Am son una superclase de órdenes sobre intervalo definidas en Moukrim y Quilliot: una relación entre la programación multiprocesador y la programación lineal. Orden, 14 (3): 269-278, 1997.
- Gráfico DC : Un gráfico de divide y vencerás es una subclase de gráficos en serie paralelos definidos en Kubiak et al .: Optimidad de HLF para programar gráficos de tareas UET de divide y vencerás en procesadores paralelos idénticos. Optimización discreta, 6: 79-91, 2009.
- Orden parcial 2-dim : Un orden parcial bidimensional es un orden parcial k-dimensional para k = 2.
- orden parcial k-dim : un poset es un orden parcial k-dimensional si puede ser incrustado en el espacio euclidiano k-dimensional de tal manera que cada nodo está representado por un punto k-dimensional y hay una precedencia entre dos nodos iyj sif para cualquier dimensión la coordenada de i es menor o igual que la de j.
En presencia de una relación de precedencia, se podrían suponer además retrasos en el tiempo . Dejar denotar la hora de inicio de un trabajo y su tiempo de finalización. Entonces la relación de precedencia implica la restricción . Si no hay retraso de tiempose especifica entonces se supone que es cero. Los retrasos pueden ser números positivos o negativos.
- l: retrasos en el tiempo independiente del trabajo. En otras palabras para todos los pares de trabajos i, j y un número dado l.
- : retardos arbitrarios dependientes del par de trabajos.
Retrasos en el transporte
- : Entre la finalización de la operación de trabajo en la máquina y el inicio de la operación de trabajo en la máquina , hay un retraso de transporte de al menos unidades.
- : Entre la finalización de la operación de trabajo en la máquina y el inicio de la operación de trabajo en la máquina , hay un retraso de transporte de al menos unidades.
- : Retraso de transporte dependiente de la máquina. Entre la finalización de la operación de trabajo en la máquina y el inicio de la operación de trabajo en la máquina , hay un retraso de transporte de al menos unidades.
- : Retraso de transporte dependiente del par de máquinas. Entre la finalización de la operación de trabajo en la máquina y el inicio de la operación de trabajo en la máquina , hay un retraso de transporte de al menos unidades.
- : Retraso en el transporte dependiente del trabajo. Entre la finalización de la operación de trabajo en la máquina y el inicio de la operación de trabajo en la máquina , hay un retraso de transporte de al menos unidades.
Varias limitaciones
- rcrc : Recirculación, también llamado Taller de trabajo flexible. La promesa en se levanta y para algunas parejas podríamos tener .
- no-wait : la operacióndebe comenzar exactamente cuando la operación completa. A veces también se denota como ' nwt '.
- no-inactivo : ninguna máquina está inactiva entre dos ejecuciones.
- : Tareas de multiprocesador en máquinas paralelas idénticas. La ejecución del trabajo se hace simultáneamente en máquinas paralelas.
- : Tareas de multiprocesador. Cada trabajose da con un conjunto de maquinas , y necesita simultáneamente todas estas máquinas para su ejecución. A veces también se denota por 'MPT'.
- : Máquinas polivalentes. Cada trabajo debe programarse en una máquina de un conjunto dado . A veces también se denota por 'M_j'.
Funciones objetivas
Por lo general, el objetivo es minimizar algún valor objetivo. Una diferencia es la notacióndonde el objetivo es maximizar el número de trabajos que se completan antes de la fecha límite. Esto también se denomina rendimiento . El valor objetivo puede ser una suma, posiblemente ponderado por algunas ponderaciones prioritarias dadas por trabajo.
- - : 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.
- : 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 desobre todo j ), que a veces se denota por mft (tiempo medio de finalización). [4]
- : El tiempo de flujo de un trabajo es la diferencia entre su tiempo de finalización y su tiempo de liberación, es decir.
- : Tardanza . Cada trabajo se le da una fecha de vencimiento . La tardanza del trabajo Se define como . Algunas vecesse utiliza para indicar la viabilidad de un problema con plazos. De hecho, utilizando la búsqueda binaria, la complejidad de la versión de viabilidad es equivalente a la minimización de.
- : Rendimiento . Cada trabajo tiene una fecha de vencimiento. Hay una ganancia unitaria para los trabajos que se completan a tiempo, es decir Si y de lo contrario. A veces el significado de está invertido 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.
- : Tardanza . Cada trabajo se le da una fecha de vencimiento . La tardanza del trabajo Se define como .
- : Precocidad . Cada trabajo se le da una fecha de vencimiento . La precocidad del trabajo Se define como . Este objetivo es importante para la programación justo a tiempo.
También hay variantes con múltiples objetivos , pero mucho menos estudiadas. [2]
Ejemplos de
A continuación se muestran algunos ejemplos de problemas definidos con la notación anterior. [1]
- - asignando cada uno de trabajos asignados a una de las 2 máquinas idénticas para minimizar el tiempo de procesamiento total máximo en las máquinas. Esta es una versión de optimización del problema de la partición.
- 1 | prec | - Asignar a una sola máquina, procesos con restricción de precedencia general, minimizando la máxima demora.
- R | pmtn | - Asignar tareas a un número variable de máquinas paralelas no relacionadas, lo que permite la preferencia y minimiza el tiempo total de finalización.
- J3 || - 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.
- P || - 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 la programación de tareas paralelas .
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 perturbar de forma aleatoria. [2]
enlaces externos
- Scheduling zoo (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.
Referencias
- ^ a b Graham, RL; Lawler, EL; Lenstra, JK; Rinnooy Kan, AHG (1979). "Optimización y aproximación en secuenciación determinista y programación: 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.
- ^ a b c 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 . ISSN 0927-0507 .CS1 maint: varios nombres: lista de autores ( enlace )
- ^ B. Chen, CN Potts y GJ Woeginger . "Una revisión de la programación de máquinas: complejidad, algoritmos y aproximabilidad". 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 (conjunto)
- ^ 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 .