Programación de una sola máquina

La planificación de una sola máquina o planificación de un solo recurso es un problema de optimización en ciencias de la computación e investigación de operaciones . Se nos dan n trabajos J ₁ , J ₂ , ..., J _n de tiempos de procesamiento variables, que deben planificarse en una sola máquina, de manera que se optimice un objetivo determinado, como el rendimiento .

La planificación de tareas en una sola máquina es un caso especial de la planificación de tareas en máquinas idénticas , que a su vez es un caso especial de la planificación óptima de tareas . Muchos problemas, que en general son NP-difíciles, pueden resolverse en tiempo polinomial en el caso de una sola máquina. ^{[ 1 ] : 10–20}

En la notación estándar de tres campos para problemas de programación óptima de trabajos , la variante de una sola máquina se denota por 1 en el primer campo. Por ejemplo, " 1||${\displaystyle \sum C_{j}}$" es un problema de programación de una sola máquina sin restricciones, donde el objetivo es minimizar la suma de los tiempos de finalización.

El problema de minimización del tiempo de finalización 1||${\displaystyle C_{\max }}$, que es un objetivo común con múltiples máquinas, es trivial con una sola máquina, ya que el tiempo de finalización es siempre idéntico. Por lo tanto, se han estudiado otros objetivos. ^{[ 2 ]}

El problema 1||${\displaystyle \sum C_{j}}$Su objetivo es minimizar la suma de los tiempos de finalización. Se puede resolver de forma óptima mediante la regla del Tiempo de Procesamiento Más Corto Primero ( SPT ): los trabajos se programan en orden ascendente según su tiempo de procesamiento.${\displaystyle p_{j}}$.

El problema 1||${\displaystyle \sum w_{j}C_{j}}$Su objetivo es minimizar la suma ponderada de los tiempos de finalización. Se puede resolver de forma óptima mediante la regla de Tiempo de Procesamiento Más Corto Ponderado Primero ( WSPT ): los trabajos se programan en orden ascendente de la proporción. ${\displaystyle p_{j}/w_{j}}$. ^{[ 2 ] : lección 1, parte 2}

El problema 1|cadenas|${\displaystyle \sum w_{j}C_{j}}$Es una generalización del problema anterior para trabajos con dependencias en forma de cadenas. También puede resolverse de forma óptima mediante una generalización adecuada de WSPT. ^{[ 2 ] : lección 1, parte 3}

El problema 1|prec|${\displaystyle \sum w_{j}C_{j}}$es la versión con restricciones de precedencia del problema original. Se sabe que este problema es fuertemente NP-difícil. Un orden parcial${\displaystyle (N,\rightarrow )}$se define para modelar la restricción de precedencia donde${\displaystyle N}$es el conjunto de todos los trabajos. Este problema es polinomialmente resoluble para clases simples de conjuntos parcialmente ordenados. ^{[ 3 ]} Hay varios algoritmos de aproximación con un factor de aproximación de 2. ^{[ 4 ]}

El problema 1||${\displaystyle L_{\max }}$Su objetivo es minimizar el retraso máximo . Para cada trabajo j , hay una fecha de vencimiento .${\displaystyle d_{j}}$. Si se completa después de su fecha límite, sufre retraso definido como ${\displaystyle L_{j}:=C_{j}-d_{j}}$. 1||${\displaystyle L_{\max }}$Se puede resolver de forma óptima mediante la regla de fecha de vencimiento más temprana ( EDD ): los trabajos se programan en orden ascendente según su fecha de vencimiento.${\displaystyle d_{j}}$. ^{[ 2 ] : lección 2, parte 2}

El problema 1|prec|${\displaystyle h_{\max }}$generaliza el 1||${\displaystyle L_{\max }}$De dos maneras: primero, permite restricciones de precedencia arbitrarias en las tareas; segundo, permite que cada tarea tenga una función de costo arbitraria h _j , que es una función de su tiempo de finalización (el retraso es un caso especial de una función de costo). El costo máximo se puede minimizar mediante un algoritmo voraz conocido como algoritmo de Lawler . ^{[ 2 ] : lección 2, parte 1}

El problema 1|${\displaystyle r_{j}}$|${\displaystyle L_{\max }}$generaliza 1||${\displaystyle L_{\max }}$Al permitir que cada trabajo tenga un tiempo de liberación diferente , momento en el que estará disponible para su procesamiento. La presencia de tiempos de liberación implica que, en algunos casos, puede ser óptimo dejar la máquina inactiva para esperar un trabajo importante que aún no se haya liberado. Minimizar el retraso máximo en este contexto es un problema NP-difícil. Sin embargo, en la práctica, se puede resolver utilizando un algoritmo de ramificación y acotación . ^{[ 2 ] : lección 2, parte 3}

En entornos con plazos de entrega, es posible que, si el trabajo se completa antes de la fecha límite, se obtenga una ganancia p _j . De lo contrario, no hay ganancia. El objetivo es maximizar la ganancia. La planificación de tareas en una sola máquina con plazos de entrega es NP-difícil; Sahni ^{[ 5 ]} presenta tanto algoritmos exactos de tiempo exponencial como un algoritmo de aproximación de tiempo polinomial.

El problema 1||${\displaystyle \sum U_{j}}$Su objetivo es minimizar el número de trabajos atrasados, independientemente de la cantidad de retraso. Puede resolverse de forma óptima mediante el algoritmo de Hodgson-Moore. ^{[ 6 ] [ 2 ] : lección 3, parte 1} También puede interpretarse como maximizar el número de trabajos que se completan a tiempo; este número se denomina rendimiento .

El problema 1||${\displaystyle \sum w_{j}U_{j}}$tiene como objetivo minimizar el peso de los trabajos atrasados. Es NP-difícil, ya que el caso especial en el que todos los trabajos tienen la misma fecha límite (denotado por 1|${\displaystyle d_{j}=d}$|${\displaystyle \sum w_{j}U_{j}}$) es equivalente al problema de la mochila . ^{[ 2 ] : lección 3, parte 2}

El problema 1|${\displaystyle r_{j}}$|${\displaystyle \sum U_{j}}$ generaliza 1||${\displaystyle \sum U_{j}}$Al permitir que diferentes trabajos tengan diferentes tiempos de lanzamiento . El problema es NP-difícil. Sin embargo, cuando todas las duraciones de los trabajos son iguales, el problema se puede resolver en tiempo polinomial. Tiene varias variantes:

• La variante de optimización ponderada, 1|${\displaystyle r_{j},p_{j}=p}$|${\displaystyle \sum w_{j}U_{j}}$, se puede resolver a tiempo${\displaystyle O(n^{7})}$. ^{[ 7 ]}
• La variante de optimización no ponderada, que maximiza el número de trabajos que terminan a tiempo, se denota con 1|${\displaystyle r_{j},p_{j}=p}$|${\displaystyle \sum U_{j}}$, se puede resolver a tiempo${\displaystyle O(n^{5})}$utilizando programación dinámica , cuando todos los tiempos de lanzamiento y fechas límite son enteros. ^{[ 8 ] [ 9 ]}
• La variante de decisión —decidir si es posible que todos los trabajos dados se completen a tiempo— puede resolverse mediante varios algoritmos, ^{[ 10 ]} el más rápido de ellos se ejecuta en tiempo${\displaystyle O(n\log n)}$. ^{[ 11 ]}

Los trabajos pueden tener intervalos de ejecución . Para cada trabajo j , existe un tiempo de procesamiento t _j y un tiempo de inicio s _j , por lo que debe ejecutarse en el intervalo [ s _j , s _j +t _j ]. Dado que algunos intervalos se superponen, no todos los trabajos pueden completarse. El objetivo es maximizar el número de trabajos completados, es decir, el rendimiento . En general, cada trabajo puede tener varios intervalos posibles, y cada intervalo puede estar asociado a una ganancia diferente. El objetivo es elegir como máximo un intervalo para cada trabajo, de manera que se maximice la ganancia total. Para más detalles, consulte la página sobre planificación de intervalos .

En términos más generales, los trabajos pueden tener ventanas de tiempo , con horas de inicio y fechas límite, que pueden ser mayores que la duración del trabajo. Cada trabajo puede programarse en cualquier momento dentro de su ventana de tiempo. Bar-Noy, Bar-Yehuda, Freund, Naor y Schieber ^{[ 12 ]} presentan una aproximación (1- ε )/2.

Los trabajadores y las máquinas suelen cansarse tras trabajar durante un tiempo determinado, lo que ralentiza su procesamiento de tareas futuras. Por otro lado, pueden aprender a trabajar mejor, lo que les permite procesar tareas más rápidamente. En ambos casos, la duración (tiempo de procesamiento) de una tarea no es constante, sino que depende de las tareas procesadas previamente. En este contexto, incluso minimizar el tiempo máximo de finalización se convierte en una tarea compleja. Existen dos métodos comunes para modelar el cambio en la duración de las tareas.

1. La duración del trabajo puede depender de la hora de inicio del trabajo. ^{[ 13 ]} Cuando la duración es una función débilmente creciente de la hora de inicio, se denomina efecto de deterioro ; cuando es débilmente decreciente, se denomina efecto de aprendizaje .
2. La duración de un trabajo puede depender de la suma de los tiempos de procesamiento normales de los trabajos procesados ​​previamente. Cuando la duración es una función débilmente creciente de esta suma, a menudo se habla de efecto de envejecimiento . ^{[ 14 ]}

• Programación por intervalos

Se han aplicado numerosas técnicas de solución para resolver problemas de programación de máquinas individuales. Algunas de ellas se enumeran a continuación.

• Algoritmos genéticos
• Redes neuronales
• Recocido simulado
• optimización de colonias de hormigas
• Búsqueda tabú