Gourmand séquentielle ou parallèle de la planification des tâches

Question

Nous avons N les tâches qui doivent être prévues pour le traitement.Chaque tâche se compose de deux parties qui doivent exécutés dans l'ordre.Le premier est protégée par un mutex et une seule tâche peut être de l'exécution de la présente partie à la fois.La deuxième partie n'a pas cette contrainte et un certain nombre de tâches peuvent être en cours d'exécution en même temps.Pour la tâche i nous savons combien de temps il a besoin de passer dans chaque partie, à savoir m_j' pour le surveillé partie, et un_j' pour la partie qui peuvent être exécutées en parallèle.

Le problème est de trouver une permutation des tâches telles que le temps nécessaire pour l'exécution de tous d'entre eux est réduite au minimum.

Mon intuition dit que cela peut être résolu avec un algorithme glouton, en planifiant les tâches en descendant une_j' ordre.

Par exemple, étant donné les tâches avec:
m₁ = 3, un₁ = 9
m₂ = 2, un₂ = 7
m₃ = 6, un₃ = 10

La solution optimale est la permutation 3, 1, 2.

Cependant, j'ai du mal à prouver que la gourmande solution est optimale.Toutes les idées sur la façon de le faire?

Answer 1

J'ai un assez salissante la preuve.Je suis sûr que cela peut être nettoyé avec un peu de travail.Laissez-moi savoir si vous avez besoin de moi pour simplifier la preuve.

Pour l'amour de la preuve, permet de réorganiser tous les termes tels que $a_1 \geq a_2 \geq a_3 \ldots$.Laissez $f(1), f(2), \ldots, f(N)$ certains annexe.Le temps total passé pour n'importe quel horaire $f$ est donnée par la suite.$$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)} + a_{f(N)} \}$$.

Pour l'amour de la contradiction, supposons que votre avidité méthode n'est pas la solution optimale.Il existe un certain calendrier $\phi$ tels que $T(Id) > T(\phi)$ (ici $Id$ est l'identité).Choisir $k$ tels que $\sum_{i = 1}^k m_{i} + a_k = T(Id)$.Laissez $h$ être le plus petit nombre tel que $\{1,\ldots, k\} \subset \{\phi(1), \ldots, \phi(h)\}$.Notez que $\phi(h) \leq k$.Parce que $\{1,\ldots, k\} \subset \{\phi(1), \ldots, \phi(h)\}$, $\sum_{i = 1}^h m_{\phi(i)} \geq \sum_{i = 1}^k m_i$.Parce que $a_1 \geq a_2 \geq \ldots$, nous savons que $a_{\phi(h)} \geq a_k$.Cela signifie que $$\sum_{i = 1}^k m_i + a_k \leq\sum_{i = 1}^h m_{\phi(i)} + a_{\phi(h)}$$ Mais $T(Id) = \sum_{i = 1}^k m_i + a_k \leq \sum_{i = 1}^h m_{\phi(i)} + a_{\phi(h)} \leq T(\phi)$.C'est une contradiction.