.. _2020ordonnancementrst:

================================
Algo - Problème d’ordonnancement
================================


.. only:: html

    **Links:** :download:`notebook <2020_ordonnancement.ipynb>`, :downloadlink:`html <2020_ordonnancement2html.html>`, :download:`python <2020_ordonnancement.py>`, :downloadlink:`slides <2020_ordonnancement.slides.html>`, :githublink:`GitHub|_doc/notebooks/td1a_home/2020_ordonnancement.ipynb|*`


Un `problème
d’ordonnancement <https://fr.wikipedia.org/wiki/Th%C3%A9orie_de_l%27ordonnancement>`__
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.

.. code:: ipython3

    from jyquickhelper import add_notebook_menu
    add_notebook_menu()






.. contents::
    :local:





.. code:: ipython3

    %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.

.. code:: ipython3

    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)






.. raw:: html

    <div id="M12baf769060046d7b95890a7452472f5-cont"><div id="M12baf769060046d7b95890a7452472f5" style="width:100%;height:100%;"></div></div>
    <script>

    require(['http://www.xavierdupre.fr/js/vizjs/viz.js'], function() { var svgGraph = Viz("digraph{ \n  rankdir=\"LR\";\n  size=\"4,4\";\n  0;\n  1;\n  2;\n  3;\n  4;\n  0 -> 1;\n  0 -> 2;\n  0 -> 3;\n  1 -> 2;\n  1 -> 4;\n  2 -> 4;\n  3 -> 4;\n}");
    document.getElementById('M12baf769060046d7b95890a7452472f5').innerHTML = svgGraph; });

    </script>



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 :math:`F_{i}` où *i* est la tâche. :math:`F_{i}=t` signifie qu’au
temps *t*, la tâche *i* est finie.

.. code:: ipython3

    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)




.. parsed-literal::
    [0, 1, 2, 1, 3]



On vérifie sur un graphe plus compliqué.

.. code:: ipython3

    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)






.. raw:: html

    <div id="Mcda392631ad048068d2157a0b70dfa3b-cont"><div id="Mcda392631ad048068d2157a0b70dfa3b" style="width:100%;height:100%;"></div></div>
    <script>

    require(['http://www.xavierdupre.fr/js/vizjs/viz.js'], function() { var svgGraph = Viz("digraph{ \n  rankdir=\"LR\";\n  size=\"4,4\";\n  0;\n  1;\n  2;\n  3;\n  4;\n  5;\n  0 -> 1;\n  0 -> 2;\n  0 -> 3;\n  1 -> 2;\n  1 -> 4;\n  2 -> 4;\n  3 -> 4;\n  5 -> 0;\n}");
    document.getElementById('Mcda392631ad048068d2157a0b70dfa3b').innerHTML = svgGraph; });

    </script>



.. code:: ipython3

    order_same_weight(mat2)




.. parsed-literal::
    [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``.

.. code:: ipython3

    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])




.. parsed-literal::
    [0, 1, 2, 1, 3]



.. code:: ipython3

    order_any_weight(mat, durations=[1, 2, 1, 1, 1])




.. parsed-literal::
    [0, 1, 3, 1, 4]