Programación de una sola máquina

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

La programación de una sola máquina es un caso especial de programación de máquinas idénticas , que a su vez es un caso especial de programación óptima de trabajos . Muchos problemas, que son NP-hard en general, se pueden resolver 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 con 1 en el primer campo. Por ejemplo, " 1|| " 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. ${\displaystyle \suma C_{j}}$

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

El problema 1|| tiene como objetivo minimizar la suma de los tiempos de finalización. Puede resolverse de manera óptima mediante la regla del tiempo de procesamiento más corto primero ( SPT ): los trabajos se programan en orden ascendente de su tiempo de procesamiento . ${\displaystyle \suma C_{j}}$$estilo de visualización p_ {j}}$

El problema 1|| tiene como objetivo minimizar la suma ponderada de los tiempos de finalización. Puede resolverse de manera óptima mediante la regla del tiempo de procesamiento más corto ponderado primero ( WSPT ): los trabajos se programan en orden ascendente de la relación . ^{[2] : lección 1, parte 2}${\displaystyle \sum w_{j}C_{j}}$$estilo de visualización p_ {j}/w_ {j}}$

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

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

El problema 1|prec| generaliza el problema 1|| de dos maneras: primero, permite restricciones de precedencia arbitrarias sobre los trabajos; segundo, permite que cada trabajo tenga una función de costo arbitraria h _j , que es una función de su tiempo de finalización (la tardanza 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}${\displaystyle h_{\max}}$${\displaystyle L_{\max}}$

El problema 1| |$estilo de visualización r_ {j}}$ generaliza el problema 1|| al permitir que cada trabajo tenga un tiempo de liberación diferente en el que esté disponible para su procesamiento. La presencia de tiempos de liberación significa que, en algunos casos, puede ser óptimo dejar la máquina inactiva, para esperar un trabajo importante que aún no se ha liberado. Minimizar la demora máxima en esta configuración es NP-hard. Pero en la práctica, se puede resolver utilizando un algoritmo de ramificación y acotación . ^{[2] : lección 2, parte 3}${\displaystyle L_{\max}}$${\displaystyle L_{\max}}$

En entornos con fechas límite, es posible que, si el trabajo se completa antes de la fecha límite, haya una ganancia p _j . De lo contrario, no hay ganancia. El objetivo es maximizar la ganancia. La programación de una sola máquina con fechas límite es NP-hard; Sahni ^[3] presenta algoritmos de tiempo exponencial exactos y un algoritmo de aproximación de tiempo polinomial.

El problema 1||${\displaystyle \suma U_{j}}$ tiene como objetivo minimizar la cantidad de trabajos que se retrasan, independientemente de la cantidad de retrasos. Se puede resolver de manera óptima mediante el algoritmo de Hodgson-Moore. ^{[4] [2] : lección 3, parte 1} También se puede interpretar como la maximización de la cantidad 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-hard, ya que el caso especial en el que todos los trabajos tienen la misma fecha límite (indicada 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| |$estilo de visualización r_ {j}}$${\displaystyle \suma U_{j}}$ generaliza 1||${\displaystyle \suma U_{j}}$ al permitir que diferentes trabajos tengan diferentes tiempos de liberación . El problema es NP-hard. Sin embargo, cuando todas las duraciones de los trabajos son iguales, el problema se puede resolver en tiempo polinómico. 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 en el tiempo . ^[5]${\displaystyle O(n^{7})}$
• La variante de optimización no ponderada, que maximiza el número de trabajos que terminan a tiempo, denotada 1| |${\displaystyle r_{j},p_{j}=p}$${\displaystyle \suma U_{j}}$ , se puede resolver en el tiempo utilizando programación dinámica, cuando todos los tiempos de lanzamiento y fechas límite son números enteros. ^{[6] [7]}${\displaystyle O(n^{5})}$
• La variante de decisión (decidir si es posible que todos los trabajos dados se completen a tiempo) se puede resolver mediante varios algoritmos, ^[8] el más rápido de ellos se ejecuta a tiempo . ^[9]${\displaystyle O(n\log n)}$

Los trabajos pueden tener intervalos de ejecución . Para cada trabajo j , hay 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 de los intervalos se superponen, no todos los trabajos pueden completarse. El objetivo es maximizar el número de trabajos completados, es decir, el rendimiento . En términos más generales, cada trabajo puede tener varios intervalos posibles y cada intervalo puede estar asociado con una ganancia diferente. El objetivo es elegir como máximo un intervalo para cada trabajo, de modo que se maximice la ganancia total. Para obtener más detalles, consulte la página sobre programación de intervalos .

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

Los trabajadores y las máquinas suelen cansarse después de trabajar durante un tiempo determinado, lo que hace que sean más lentos a la hora de procesar trabajos futuros. Por otro lado, los trabajadores y las máquinas pueden aprender a trabajar mejor, lo que los hace más rápidos a la hora de procesar trabajos futuros. En ambos casos, la duración (tiempo de procesamiento) de un trabajo no es constante, sino que depende de los trabajos procesados ​​antes. En este contexto, incluso minimizar el tiempo máximo de finalización deja de ser una tarea trivial. Hay dos formas habituales de modelar el cambio en la duración del trabajo.

1. La duración del trabajo puede depender de la hora de inicio del trabajo. ^[11] Cuando la duración es una función débilmente creciente de la hora de inicio, se trata de un efecto de deterioro ; cuando es débilmente decreciente, se trata de un 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 denomina efecto de envejecimiento . ^[12]

Cheng y Ding estudiaron la minimización del tiempo de ejecución y la minimización de la demora máxima cuando la duración real del trabajo j programado en el momento s _j está dada por

${\displaystyle {\widehat {p_{j}}}(s_{j})=p_{j}-b\cdot s_{j}}$, donde p _j es la longitud normal de j .

Demostraron los siguientes resultados:

• Cuando los trabajos pueden tener plazos arbitrarios, los problemas son fuertemente NP-difíciles por reducción de 3-partición ; ^[13]
• Cuando los trabajos pueden tener uno de dos plazos, los problemas son NP-completos, por reducción de la partición . ^[14]
• Cuando los trabajos pueden tener tiempos de liberación arbitrarios, los problemas son fuertemente NP-duros , por reducción del problema con plazos arbitrarios. ^[15]
• Cuando los trabajos pueden tener uno de dos tiempos de liberación, 0 o R, los problemas son NP-completos. ^[15]

Kubiak y van-de-Velde ^[16] estudiaron la minimización del tiempo de trabajo cuando la fatiga comienza solo después de una fecha de vencimiento común d . Es decir, la duración real del trabajo j programado en el momento s _j está dada por

${\displaystyle {\widehat {p_{j}}}(s_{j})=\max(p_{j},p_{j}+b_{j}\cdot (s_{j}-d))}$.

Por lo tanto, si el trabajo comienza antes de d , su longitud no cambia; si comienza después de d , su longitud crece a una tasa dependiente del trabajo. Demuestran que el problema es NP-hard, dan un algoritmo pseudopolinomial que se ejecuta en tiempo y dan un algoritmo de ramificación y acotación que resuelve instancias con hasta 100 trabajos en un tiempo razonable. También estudian el deterioro acotado, donde p _j deja de crecer si el trabajo comienza después de una fecha de deterioro máximo común D > d. Para este caso, dan dos algoritmos de tiempo pseudopolinomial. ${\displaystyle O(nd\sum _{j}p_{j})}$

Cheng, Ding y Lin ^[11] analizaron varios estudios sobre un efecto de deterioro, donde la duración del trabajo j programado en el momento s _j es lineal o lineal por partes, y la tasa de cambio puede ser positiva o negativa.

El efecto del envejecimiento tiene dos tipos:

• En el modelo de envejecimiento basado en la posición , el tiempo de procesamiento de un trabajo depende de la cantidad de trabajos procesados ​​antes que él, es decir, de su posición en la secuencia. ^[17]
• En el modelo de envejecimiento basado en la suma del tiempo de procesamiento , el tiempo de procesamiento de un trabajo es una función débilmente creciente de la suma de los tiempos de procesamiento normales (=no afectados por el envejecimiento) de los trabajos procesados ​​antes. ^[18]

Wang, Wang, Wang y Wang ^[19] estudiaron un modelo de envejecimiento basado en la suma del tiempo de procesamiento, donde el tiempo de procesamiento del trabajo j programado en la posición v está dado por

${\displaystyle {\widehat {p_{j}}}(\pi ,v)=p_{j}\cdot \left(1+\sum _{l=1}^{v-1}p_{\pi (l)}\right)^{\alpha }}$

donde es el trabajo programado en la posición , y α es la "característica de envejecimiento" de la máquina. En este modelo, el tiempo máximo de procesamiento de la permutación es:${\displaystyle \pi(l)}$${\estilo de visualización l}$${\estilo de visualización \pi}$

${\displaystyle \sum _{l=1}^{n}{\widehat {p_{\pi (l)}}}(\pi ,l)}$

Rudek ^[20] generalizó el modelo de dos maneras: permitiendo que la fatiga sea diferente del tiempo de procesamiento y permitiendo una característica de envejecimiento dependiente del trabajo:

${\displaystyle {\widehat {p_{j}}}(\pi ,v)=p_{j}\cdot \left(1+\sum _{l=1}^{v-1}f(p_{\pi (l)})\right)^{\alpha _{j}}}$

Aquí, f es una función creciente que describe la dependencia de la fatiga con respecto al tiempo de procesamiento; y α _j es la característica de envejecimiento del trabajo j . Para este modelo, demostró los siguientes resultados:

• Minimizar el tiempo máximo de finalización y minimizar la demora máxima son soluciones de tiempo polinomial.
• Minimizar el tiempo máximo de finalización y minimizar la tardanza máxima son medidas NP-duras si algunos trabajos tienen fechas límite.

• Programación de intervalos

Se han aplicado muchas técnicas de solución para resolver problemas de programación de una sola máquina. Algunas de ellas se enumeran a continuación.

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