Programe tareas heterogéneas en máquinas heterogéneas

Question

Tenemos n trabajos y máquinas M. Cada trabajo I tiene un tiempo de lanzamiento r [i]. Procesamiento del trabajo I en la máquina J toma p [i] [j] tiempo. Para un trabajo k, | {p [i] [j] | i == k} | <= c, donde c << m. Definimos el retraso del trabajo I como f [i] - r [i], donde f [i] es el momento en que el trabajo I está terminado. El sistema no es preventivo, es decir, cuando se inicia un trabajo en alguna máquina, no se puede interrumpir antes de que termine. El objetivo es proporcionar un algoritmo de programación que minimice la suma de retraso de todos los trabajos. ¿Alguna idea?

Answer 1

Aquí hay una reducción del Problema de 3 partes.

Sea s = {x₁, …, X_3M} Sea la instancia de 3 partes tal que, por cada i, b/4 <x_i <B/2, donde b = ∑x_i/M es la suma objetivo.

Que haya m idéntico máquinas. En el momento 0, libera 3m trabajos de longitudes x₁, …, X_3M. En cada vez b, b + 1, ..., b + 4mb - 1, liberación m trabajos de longitud 1, para un total de 4m²B Trabajos.

La instancia de 3 partes tiene una solución si y solo si la marca de los trabajos iniciales es menor o igual a B. Si hay una solución, entonces la contribución de los trabajos iniciales al objetivo es como máximo 3 MB. La contribución de los otros trabajos es de 4 m²B.

Si el MakePan es más largo que B, entonces una cadena de trabajos de 4 MB se retrasa al menos una unidad, contribuyendo con 4 MB al objetivo. Por lo tanto, el objetivo es como máximo 3MB + 4m²B Si el problema de 3 partes es solucionable y al menos 4MB + 4m²B Si el problema de 3 partes no se puede solucionar.