Algo - Problème d’ordonnancement

Links: notebook, html, python, slides, GitHub

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.

from jyquickhelper import add_notebook_menu
add_notebook_menu()

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

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)

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.

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)

[0, 1, 2, 1, 3]

On vérifie sur un graphe plus compliqué.

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)

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

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

[0, 1, 2, 1, 3]

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

[0, 1, 3, 1, 4]