Programación de máquinas idénticas
La programación de máquinas idénticas es un problema de optimización en informática e investigación de operaciones . Tenemos n trabajos J 1 , J 2 , ..., J n de tiempos de procesamiento variables, que deben programarse en m máquinas idénticas, de modo que se optimice una determinada función objetivo, por ejemplo, se minimice elmakespan .
La programación de máquinas idénticas es un caso especial de programación de máquinas uniforme , que en sí misma es un caso especial de programación óptima de trabajos . En el caso general, el tiempo de procesamiento de cada trabajo puede ser diferente en diferentes máquinas; en el caso de una programación de máquina idéntica, el tiempo de procesamiento de cada trabajo es el mismo en cada máquina. Por lo tanto, la programación de máquinas idénticas es equivalente a la partición de números de varias vías . Un caso especial de programación de máquinas idénticas es la programación de una sola máquina .
En la notación estándar de tres campos para problemas de programación de trabajos óptimos , la variante de máquinas idénticas se denota por P en el primer campo. Por ejemplo, " P|| " es un problema de programación de máquina idéntico sin restricciones, donde el objetivo es minimizar el tiempo máximo de finalización.
En algunas variantes del problema, en lugar de minimizar el tiempo de finalización máximo , se desea minimizar el tiempo de finalización promedio (promedio de todos los n trabajos); se denota por P|| . De manera más general, cuando algunos trabajos son más importantes que otros, se puede desear minimizar un promedio ponderado del tiempo de finalización, donde cada trabajo tiene un peso diferente. Esto se denota por P|| .
La minimización del tiempo promedio de finalización ( P|| ) se puede hacer en tiempo polinomial. El algoritmo SPT (Tiempo de procesamiento más corto primero) clasifica los trabajos por su longitud, primero los más cortos y luego los asigna al procesador con el tiempo de finalización más temprano hasta el momento. Se ejecuta en el tiempo O( n log n ) y minimiza el tiempo promedio de finalización en máquinas idénticas, [1] P|| .
Minimizar el tiempo de finalización promedio ponderado 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]