Planificación de máquinas idénticas

Minimizar el tiempo promedio de finalización ( P||${\displaystyle \sum C_{i}}$) se puede realizar en tiempo polinomial. El algoritmo SPT (Shortest Processing Time First) ordena los trabajos por su longitud, del más corto al más largo, y luego los asigna al procesador con el tiempo de finalización más temprano hasta el momento. Se ejecuta en tiempo O( n log n ) y minimiza el tiempo promedio de finalización en máquinas idénticas, ^{[ 1 ]} P||${\displaystyle \sum C_{i}}$.

• Puede haber muchos cronogramas SPT; encontrar el cronograma SPT con el menor tiempo de finalización (también llamado OMFT – tiempo medio de finalización óptimo ) es un problema NP-difícil.

Minimizar el tiempo promedio ponderado de finalización es NP-difícil incluso en máquinas idénticas, por reducción del problema de la mochila . ^{[ 1 ]} Es NP-difícil incluso si el número de máquinas es fijo y al menos 2, por reducción del problema de partición . ^{[ 2 ]}

Sahni ^{[ 2 ]} presenta un algoritmo de tiempo exponencial y un esquema de aproximación de tiempo polinomial para resolver ambos problemas NP-difíciles en máquinas idénticas:

• Tiempo medio de finalización óptimo;
• Tiempo promedio ponderado de finalización.

Minimizar el tiempo máximo de finalización ( P||${\displaystyle C_{\max }}$) es NP-difícil incluso para máquinas idénticas , por reducción del problema de partición . Se conocen muchos algoritmos exactos y de aproximación .

Graham demostró que:

• Cualquier algoritmo de planificación de listas (un algoritmo que procesa los trabajos en un orden fijo arbitrario y programa cada trabajo en la primera máquina disponible) es un ${\displaystyle 2-1/m}$aproximación para máquinas idénticas . ^{[ 3 ]} La cota es ajustada para cualquier m . Este algoritmo se ejecuta en tiempo O( n ).
• El algoritmo específico de programación de listas llamado Tiempo de procesamiento más largo primero (LPT), que ordena los trabajos por longitud descendente, es un${\displaystyle 4/3-1/3m}$aproximación para máquinas idénticas . ^{[ 4 ] : sec.5} También se denomina partición de números voraz .

Coffman, Garey y Johnson presentaron un algoritmo diferente llamado algoritmo multifit , que utiliza técnicas de empaquetamiento de contenedores , el cual tiene un factor de aproximación de 13/11≈1,182.

Huang y Lu ^{[ 5 ]} presentaron un algoritmo simple de tiempo polinomial que alcanza una aproximación de 11/9≈1,222 en tiempo O( m log m + n ), a través del problema más general de asignación de tareas de participación maximin .

Sahni ^{[ 2 ]} presentó un PTAS que alcanza (1+ε)OPT en tiempo${\displaystyle O(n\cdot (n^{2}/\epsilon )^{m-1})}$. Es un FPTAS si m es fijo. Para m=2, el tiempo de ejecución mejora a${\displaystyle O(n^{2}/\epsilon )}$El algoritmo utiliza una técnica llamada partición de intervalos .

Hochbaum y Shmoys ^{[ 6 ]} presentaron varios algoritmos de aproximación para cualquier número de máquinas idénticas (incluso cuando el número de máquinas no es fijo):

• Para cualquier r > 0, un algoritmo con una razón de aproximación como máximo (6/5 + 2 ^{− r} ) en tiempo${\displaystyle O(n(r+\log {n}))}$.
• Para cualquier r > 0, un algoritmo con una razón de aproximación como máximo (7/6 + 2 ^{− r} ) en tiempo${\displaystyle O(n(rm^{4}+\log {n}))}$.
• Para cualquier ε >0, un algoritmo con una razón de aproximación como máximo (1+ε) en tiempo${\displaystyle O((n/\varepsilon )^{(1/\varepsilon ^{2})})}$Este es un PTAS . Tenga en cuenta que, cuando el número de máquinas es parte de la entrada, el problema es fuertemente NP-difícil , por lo que no es posible un FPTAS.

Leung ^{[ 7 ]} mejoró el tiempo de ejecución de este algoritmo a${\displaystyle O\left((n/\varepsilon )^{(1/\varepsilon )\log {(1/\varepsilon )}}\right)}$.

Maximizar el tiempo mínimo de finalización ( P||${\displaystyle C_{\min }}$) es aplicable cuando los "trabajos" son en realidad piezas de repuesto necesarias para mantener las máquinas en funcionamiento, y tienen diferentes vidas útiles. El objetivo es mantener las máquinas en funcionamiento el mayor tiempo posible. ^{[ 8 ]} El algoritmo LPT alcanza al menos${\displaystyle {\frac {3m-1}{4m-2}}}$del óptimo.

Woeginger ^{[ 9 ]} presentó un PTAS que alcanza un factor de aproximación de${\displaystyle 1-{\varepsilon }}$a tiempo${\displaystyle O(c_{\varepsilon }n\log {k})}$, dónde${\ Displaystyle c _ {\ varepsilon}}$una constante enorme que es exponencial en el factor de aproximación requerido ε. El algoritmo utiliza el algoritmo de Lenstra para programación lineal entera .

Alon, Azar, Woeginger y Yadid ^{[ 10 ]} consideran una función objetivo más general. Dada una función real positiva f , que depende únicamente de los tiempos de finalización C _i , consideran los objetivos de minimizar${\displaystyle \sum _{i=1}^{m}f(C_{i})}$, minimizando${\displaystyle \max _{i=1}^{m}f(C_{i})}$, maximizando${\displaystyle \sum _{i=1}^{m}f(C_{i})}$y maximizar${\displaystyle \min _{i=1}^{m}f(C_{i})}$Demuestran que, si f es no negativa, convexa y satisface una condición de continuidad estricta que denominan "F*", entonces ambos problemas de minimización tienen un PTAS. De manera similar, si f es no negativa, cóncava y satisface F*, entonces ambos problemas de maximización tienen un PTAS. En ambos casos, el tiempo de ejecución del PTAS es O( n ), pero con constantes exponenciales en 1/ ε.