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. $\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] $C_{\max}$

Minimizar la suma de los tiempos de finalización

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 . $\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 por orden ascendente de la relación . ^[2]^{: lección 1, parte 2} $\suma 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} $\suma w_{j}C_{j}$

Minimizar el coste de la tardanza

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} $L_{\max}$ $estilo de visualización d_ {j}}$ $L_{j}:=C_{j}-d_{j}$ $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} $h_{\max}$ $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} $L_{\max}$ $L_{\max}$

Maximizar el beneficio de la precocidad

En entornos con plazos, 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 plazos es NP-hard; Sahni ^[3] presenta algoritmos de tiempo exponencial exactos y un algoritmo de aproximación de tiempo polinomial.

Maximizar el rendimiento

El problema 1|| $\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|| $\suma 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| | $d_{j}=d$ $\suma 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}}$ $\suma U_{j}$ generaliza 1|| $\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 polinomial. Tiene varias variantes:

La variante de optimización ponderada, 1| | $r_{j},p_{j}=p$ $\suma w_{j}U_{j}$ , se puede resolver en el tiempo . ^[5] $Estilo de visualización O(n^{7})}$
La variante de optimización no ponderada, que maximiza el número de trabajos que terminan a tiempo, denotada 1| | $r_{j},p_{j}=p$ $\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] $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] $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.

Trabajos con duración no constante

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.

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 .
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]

Duración basada en la hora de inicio

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

${\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

${\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. $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.

Longitud basada en la suma de los tiempos de procesamiento

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

${\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: $\pi(l)$ ${\estilo de visualización l}$ ${\estilo de visualización \pi}$

$\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:

${\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.

Véase también

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.

Referencias

^ 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: varios nombres: lista de autores ( enlace )
^ abcdefgh Grinshpoun, Tal (2020). "Asignaturas en la programación". www.youtube.com . Consultado el 12 de septiembre de 2021 .
^ Sahni, Sartaj K. (1 de enero de 1976). "Algoritmos para la programación de tareas independientes". Revista de la ACM . 23 (1): 116–127. doi : 10.1145/321921.321934 . ISSN 0004-5411. S2CID 10956951.
^ Lawler, EL (1 de julio de 1994). "Problemas de planificación tipo mochila, el algoritmo Moore-Hodgson y la propiedad de la 'torre de conjuntos'". Modelado matemático y computacional . 20 (2): 91–106. doi : 10.1016/0895-7177(94)90209-7 . ISSN 0895-7177.
^ Baptiste, P. (1999). "Algoritmos de tiempo polinomial para minimizar el número ponderado de trabajos tardíos en una sola máquina con tiempos de procesamiento iguales". Journal of Scheduling . 2 (6): 245–252. doi :10.1002/(SICI)1099-1425(199911/12)2:6<245::AID-JOS28>3.0.CO;2-5.
^ Chrobak, Marek; Durr, Christoph; Jawor, Wojciech; Kowalik, Łukasz; Kurowski, Maciej (1 de febrero de 2006). "Una nota sobre la programación de trabajos de igual duración para maximizar el rendimiento". Diario de programación . 9 (1): 71–73. arXiv : cs/0410046 . doi :10.1007/s10951-006-5595-4. ISSN 1099-1425. S2CID 7359990.
^ Chrobak, Marek; Durr, Christoph; Jawor, Wojciech; Kowalik, Lukasz; Kurowski, Maciej (12 de mayo de 2021). "Una nota sobre la programación de trabajos de igual duración para maximizar el rendimiento". arXiv : cs/0410046 . {{cite journal}}: Requiere citar revista |journal=( ayuda )
^ Simons, Barbara (16 de octubre de 1978). "Un algoritmo rápido para la programación de un solo procesador". Actas del 19.º Simposio Anual sobre Fundamentos de la Ciencia de la Computación . SFCS '78. EE. UU.: IEEE Computer Society: 246–252. doi :10.1109/SFCS.1978.4. S2CID 10284575.
^ Garey, MR; Johnson, DS; Simons, BB; Tarjan, RE (1981-05-01). "Programación de tareas de tiempo unitario con tiempos de liberación y plazos arbitrarios". SIAM Journal on Computing . 10 (2): 256–269. doi :10.1137/0210018. ISSN 0097-5397.
^ Bar-Noy, Amotz; Bar-Yehuda, Reuven; Freund, Ari; (Seffi) Naor, Joseph; Schieber, Baruch (1 de septiembre de 2001). "Un enfoque unificado para aproximar la asignación y programación de recursos". Revista de la ACM . 48 (5): 1069–1090. doi :10.1145/502102.502107. ISSN 0004-5411. S2CID 12329294.
^ ab Cheng, TC E; Ding, Q; Lin, BM T (1 de enero de 2004). "Un estudio conciso de la programación con tiempos de procesamiento dependientes del tiempo". Revista Europea de Investigación Operativa . 152 (1): 1–13. doi :10.1016/S0377-2217(02)00909-8. ISSN 0377-2217.
^ Chang, Pei-Chann; Chen, Shih-Hsin; Mani, V. (1 de enero de 2009). "Una nota sobre la asignación de fecha de vencimiento y la programación de una sola máquina con un efecto de aprendizaje/envejecimiento". Revista Internacional de Economía de la Producción . 117 (1): 142–149. doi :10.1016/j.ijpe.2008.10.004. ISSN 0925-5273.
^ Cheng, TCE; Ding, Q. (1999-07-01). "El problema de la amplitud de la máquina dependiente del tiempo es fuertemente NP-completo". Computers & Operations Research . 26 (8): 749–754. doi :10.1016/S0305-0548(98)00093-8. ISSN 0305-0548.
^ Cheng, TCE; Ding, Q. (1998-06-01). "La complejidad de la programación de una sola máquina con dos fechas límite distintas y tasas decrecientes idénticas de tiempos de procesamiento". Computers & Mathematics with Applications . 35 (12): 95–100. doi :10.1016/S0898-1221(98)00099-6. ISSN 0898-1221.
^ ab Cheng, TCE; Ding, Q. (29 de enero de 1998). "La complejidad de programar tareas dependientes del tiempo de inicio con tiempos de liberación". Information Processing Letters . 65 (2): 75–79. doi :10.1016/S0020-0190(97)00195-6. ISSN 0020-0190.
^ Kubiak, Wieslaw; van de Velde, Steef (agosto de 1998). "Programación de trabajos deteriorados para minimizar el tiempo de fabricación". Naval Research Logistics . 45 (5): 511–523. doi :10.1002/(SICI)1520-6750(199808)45:5<511::AID-NAV5>3.0.CO;2-6. ISSN 0894-069X.
^ Gawiejnowicz, Stanisław (25 de marzo de 1996). "Una nota sobre la programación en un solo procesador cuya velocidad depende de una cantidad de tareas ejecutadas". Information Processing Letters . 57 (6): 297–300. doi :10.1016/0020-0190(96)00021-X. ISSN 0020-0190.
^ Gordon, VS; Potts, CN; Strusevich, VA; Whitehead, JD (1 de octubre de 2008). "Modelos de programación de una sola máquina con deterioro y aprendizaje: manejo de restricciones de precedencia mediante generación de prioridades". Journal of Scheduling . 11 (5): 357–370. doi :10.1007/s10951-008-0064-x. ISSN 1099-1425. S2CID 31422825.
^ Wang, Ji-Bo; Wang, Li-Yan; Wang, Dan; Wang, Xiao-Yuan (1 de agosto de 2009). "Programación de una sola máquina con un deterioro dependiente del tiempo". Revista internacional de tecnología de fabricación avanzada . 43 (7): 805–809. doi :10.1007/s00170-008-1760-6. ISSN 1433-3015. S2CID 110043439.
^ Rudek, Radosław (1 de marzo de 2012). "Algunos problemas de programación de una sola máquina con el efecto de envejecimiento basado en la suma extendida del tiempo de procesamiento". Revista internacional de tecnología de fabricación avanzada . 59 (1): 299–309. doi : 10.1007/s00170-011-3481-5 . ISSN 1433-3015.