<SYSTEM_TASK:>
Given the following text description, write Python code to implement the functionality described below step by step
<END_TASK>
<USER_TASK:>
Description:
 Algo - 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.
Step1:  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.
Step2:  Le graphe se lit comme suit 
Step3:  On vérifie sur un graphe plus compliqué.
Step4:  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.
<ASSISTANT_TASK:>
Python Code:
from jyquickhelper import add_notebook_menu
add_notebook_menu()
%matplotlib inline
Explanation: Algo - 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.
End of explanation
import numpy
import matplotlib.pyplot as plt
from jyquickhelper import RenderJsDot
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
    return RenderJsDot(dot)
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)
Explanation: 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.
End of explanation
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)
Explanation: 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 $F_{i}$ où i est la tâche. $F_{i}=t$ signifie qu'au temps t, la tâche i est finie.
End of explanation
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)
order_same_weight(mat2)
Explanation: On vérifie sur un graphe plus compliqué.
End of explanation
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])
order_any_weight(mat, durations=[1, 2, 1, 1, 1])
Explanation: 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.
End of explanation
<END_TASK>