Problème d’ordonnancement#
Un problème d’ordonnancement est un problème dans lequel il faut déterminer le meilleur moment de démarrer un travail, une tâche alors que celles-ci ont des durées bien précises et dépendent les unes des autres.
[1]:
%matplotlib inline
Enoncé#
On définit un problème d’ordonnancement un peu plus simple dans lequel toutes les tâches ont la même durée qu’on représente par une matrice d’adjacence non symétrique.
[16]:
import uuid
import numpy
import matplotlib.pyplot as plt
from IPython.display import HTML
def plot_network(mat):
# Dessine un graph à l'aide du language DOT
# https://graphviz.org/doc/info/lang.html
rows = ["digraph{ ", ' rankdir="LR";', ' size="4,4";']
for i in range(max(mat.shape)):
rows.append(" %d;" % i)
for i in range(mat.shape[0]):
for j in range(mat.shape[1]):
if mat[i, j] > 0:
rows.append(" %d -> %d;" % (i, j))
rows.append("}")
dot = "\n".join(rows)
# print(dot) # décommenter cette ligne pour voir le résultat
hdot = dot.replace("\n", "\\n").replace('"', '\\"')
uid = uuid.uuid4()
text = f"""
<script src="https://sdpython.github.io/js/viz-lite.js"></script>
<div id="{uid}"></div>
<script>
var svgGraph = Viz("{hdot}");
document.getElementById('{uid}').innerHTML = svgGraph;
</script>
"""
return HTML(text)
mat = numpy.array(
[
[0, 1, 1, 1, 0],
[0, 0, 1, 0, 1],
[0, 0, 0, 0, 1],
[0, 0, 0, 0, 1],
[0, 0, 0, 0, 0],
]
)
plot_network(mat)
[16]:
Le graphe se lit comme suit : pour faire la tâche 2, il faut faire la tâche 0 et 1 d’abord.
Q1 : écrire un algorithme qui détermine dans quel ordre on peut exécuter les tâches.#
Il peut y avoir plusieurs tâches en parallèle. Quelle forme pourrait prendre le résultat ?
[ ]:
Q2 : Et si les tâches n’ont plus la même durée ?#
Ne pourrait-on pas réutiliser ce qu’on a fait avec une petite astuce…
Réponses#
Q1#
Comment représenter le résultat ? Une idée consiste à créer un tableau fin 
où i est la tâche. 
signifie qu’au temps t, la tâche i est finie.
[4]:
def order_same_weight(mat):
# matrice la fin de chaque tâche
# au début, on suppose qu'elles se terminent toutes à l'origine des temps
fin = [-1 for i in range(mat.shape[0])]
for j in range(mat.shape[1]):
if mat[:, j].sum() == 0:
# si la tâche j ne dépend d'aucune autre tâche
# alors on peut commencer en 0
fin[j] = 0
update = True
while update:
update = False
for i in range(mat.shape[0]):
for j in range(mat.shape[1]):
if mat[i, j] == 0 or fin[i] == -1:
continue
# indique la j dépend de la tâche i
if fin[j] < fin[i] + 1:
update = True
fin[j] = fin[i] + 1
# fin[j] = max(fin[j], fin[i] + 1)
return fin
order_same_weight(mat)
[4]:
[0, 1, 2, 1, 3]
On vérifie sur un graphe plus compliqué.
[17]:
mat2 = numpy.array(
[
[0, 1, 1, 1, 0, 0],
[0, 0, 1, 0, 1, 0],
[0, 0, 0, 0, 1, 0],
[0, 0, 0, 0, 1, 0],
[0, 0, 0, 0, 0, 0],
[1, 0, 0, 0, 0, 0],
]
)
plot_network(mat2)
[17]:
[6]:
order_same_weight(mat2)
[6]:
[1, 2, 3, 2, 4, 0]
[ ]:
Q2#
Une astuce… Une tâche deux fois plus longue, c’est comme si on avait deux tâches, la seconde dépend uniquement de la première ou alors simple tenir compte de la durée lorsqu’on calcule le maximum. Voir la ligne ########### ligne changée.
[18]:
def order_any_weight(mat, durations):
# mat est la matrice précédente
# duractions est la durée de chaque tâche (les durées sont entières)
# matrice la fin de chaque tâche
# au début, on suppose qu'elles se terminent toutes à l'origine des temps
fin = [-1 for i in range(mat.shape[0])]
for j in range(mat.shape[1]):
if mat[:, j].sum() == 0:
# si la tâche j ne dépend d'aucune autre tâche
# alors on peut commencer en 0
fin[j] = 0
update = True
while update:
update = False
for i in range(mat.shape[0]):
for j in range(mat.shape[1]):
if mat[i, j] == 0 or fin[i] == -1:
continue
# indique la j dépend de la tâche i
new_end = fin[i] + durations[i] ########### ligne changée
if fin[j] < new_end:
update = True
fin[j] = new_end
# fin[j] = max(fin[j], fin[i] + 1)
return fin
order_any_weight(mat, durations=[1, 1, 1, 1, 1])
[18]:
[0, 1, 2, 1, 3]
[19]:
order_any_weight(mat, durations=[1, 2, 1, 1, 1])
[19]:
[0, 1, 3, 1, 4]
[ ]: