Programación de tareas secuenciales codiciosas / paralelas

Question

Tenemos tareas N que deben programarse para su procesamiento. Cada tarea consta de dos partes que deben ejecutarse en orden. El primero está protegido por un mutex y, por lo tanto, solo una tarea puede estar ejecutando esta parte a la vez. La segunda parte no tiene tal restricción y cualquier número de tareas puede ejecutar esto al mismo tiempo. Para la tarea i, sabemos cuánto tiempo necesita gastar en cada parte, a saber, M _{i para la parte vigilada, y una i para la parte que se puede ejecutar en paralelo .}

El problema es encontrar una permutación de las tareas de la que se minimiza el tiempo necesario para ejecutar a todos.

Mi intuición dice que esto puede resolverse con un algoritmo codicioso, programando las tareas en descender un orden _{i .}

Por ejemplo, dadas las tareas con:

m _{1 = 3, a 1 = 9
m 2 = 2, a 2 = 7
m 3 = 6, A 3 = 10}

La solución óptima es la permutación 3, 1, 2.

Sin embargo, tengo problemas para demostrar que la solución codiciosa es óptima. ¿Alguna idea sobre cómo hacer eso?

Answer 1

Tengo una prueba bastante desordenada. Estoy seguro de que esto se puede limpiar con un poco de trabajo. Déjame saber si necesitas que simplifique la prueba.

Por el bien de la prueba, reorganice todos los términos de modo que $ A_1 \ GEQ A_2 \ GEQ A_3 \ LDOTS $ . Deje que $ f (1), f (2), \ ldots, f (n) $ sea algún horario. El tiempo total empleado para cualquier horario $ f $ está dado por los siguientes. $$ t (f)=max \ {m_ {f (1)} + a_ {f (1)}, m_ {f (1)} + m_ {f (2 )} + a_ {f (2)}, \ ldots, \ sum_ {i= 1} ^ n m_ {f (i) ^ n m_ {f (i)} + a_ {f (n)} \ _ {f (n)} \ _ $$ .

Por el bien de la contradicción, suponga que su método codicioso no es la solución óptima. Existe algunos horarios $ \ phi $ de tal que $ t (id)> t (\ phi) $ (aquí $ id $ es la identidad). Elija $ k $ tal que $ \ sum_ {i= 1} ^ k m_ {i} + a_k= t (id ) $ . Deje que $ H $ sea el número más pequeño de tal manera que $ \ {1, \ ldots, k \ \ \ subsetots \ {\ PHI (1), \ LDOTS, \ PHI (H) \} $ . Tenga en cuenta que $ \ phi (h) \ leq k $ . Porque $ \ {1, \ ldots, k \ \ phi (1), \ ldots, \ phi (h) \} $ , $ \ sum_ {i= 1} ^ h m _ {\ phi (i)} \ geq \ sum_ {i= 1} ^ k M_I $ . Porque $ A_1 \ GEQ A_2 \ GEQ \ LDOTS $ , sabemos que $ a _ {\ phi (h)} \ geq A_K $ . Esto significa que $$ \ sum_ {i= 1} ^ k m_i + a_k \ leq \ sum_ {i= 1} ^ h m _ {\ phi (i)} + a _ {\ phi (h )} $$ Pero $ t (id)=sum_ {i= 1} ^ k m_i + a_k \ leq \ sum_ {i= 1} ^ h m _ {\ phi (i)} + a_ {\ phi (h)} \ leq t (\ phi) $ . Esta es una contradicción.