Aller au contenu

Ordonnancement (Bac 🎯)⚓︎

Licence Creative Commons
Ce cours est mis à disposition selon les termes de la Licence Creative Commons Attribution - Pas d'Utilisation Commerciale - Partage dans les Mêmes Conditions 4.0 International.

programme

Sources et crédits pour ce cours

Pour préparer ce cours, j'ai utilisé :

🔖 Synthèse de ce qu'il faut retenir pour le bac

Un problème d'optimisation⚓︎

Problème d'ordonnancement

On dispose d'une liste de tâches à effectuer successivement. Deux tâches ne peuvent être exécutées en même temps, comme par exemple des processus sur un processeur. Chaque tâche est caractérisée par un couple d'attributs : (longueur, priorité). La valeur de la priorité est d'autant plus grande que la tâche est importante. On doit définir un ordonnancement de ces tâches c'est-à-dire un ordre d'exécution.

Critère d'ordonnancement : On souhaite terminer chaque tâche le plus tôt possible et achever le plus vite possible les tâches prioritaires.

Exemple

On doit ordonnancer trois tâches :

Tâche Longueur Priorité
A 4 3
B 5 2
C 6 1

Une tâche est achevée lorsque son exécution et celles de toutes les précédentes sont terminées, il est donc naturel de définir le temps de complétion d'une tâche comme la somme de sa longueur et de celles de toutes les précédentes.

Prenons par exemple l'ordonnancement A -> B -> C :

Tâche Longueur Temps de complétion Priorité
A 4 4 3
B 5 9 2
C 6 15 1

La qualité de cet ordonnancement peut être mesurée par la somme des temps de complétion pondérés par les priorités, qui se calcule ainsi :

\(4 \times 3 + 9 \times 2 + 15 \times 1 = 45\).

Considérons désormais l'ordonnancement C -> B -> A :

Tâche Longueur Temps de complétion Priorité
C 6 6 1
B 5 11 2
A 4 15 3

Le temps de complétion moyen pondéré par les priorités est supérieur au premier ordonnancement :

\(6 \times 1 + 11 \times 2 + 15 \times 3 = 73\).

Ce n'est pas surprenant, il vaut mieux traiter la taĉhe A en premier car elle est plus courte et de plus haute priorité.

Muni de notre fonction d'objectif calculant la somme des temps de complétion pondérés par les priorités, notre problème devient un problème d'optimisation dont la spécification est la suivante :

  • Entrée du problème : une liste de tâches caractérisées par des couples (longueur, priorite)
  • Sortie du problème : un ordonnancement des tâches minimisant la fonction d'objectif

Exercice 5

Ordonnancement dans deux cas particuliers.

Question 1

Si toutes les tâches ont la même longueur, doit-on traiter d'abord les moins prioritaires ou les autres pour minimiser la fonction d'objectif ?

Si toutes les tâches ont la même longueur, les coefficients de la fonction d'objectif (somme des produits temps de complétion \(\times\) priorité) liés aux temps de complétion ne dépendent pas de l'ordonnancement. Minimiser la fonction d'objectif équivaut donc à traiter les priorités dans l'ordre décroissant.

Question 2

Si toutes les tâches ont la même priorité, doit-on traiter d'abord les plus courtes ou les plus longues pour minimiser la fonction d'objectif ?

Si toutes les tâches ont la même priorité, les coefficients de la fonction d'objectif (somme des produits temps de complétion \(\times\) priorité) liés aux priorités ne dépendent pas de l'ordonnancement. Minimiser la fonction d'objectif équivaut donc à traiter les tâches dans un ordre qui minimise la somme des temps de complétion : cela revient à traiter les tâches par longueur croissante car plus une tâche est traitée tôt plus sa longueur contribue aux temps de complétion (au sien et à tous les suivants).

Heuristiques gloutonnes⚓︎

Plusieurs heuristiques gloutonnes

Un ordonnancement peut être vu comme une succession de choix. Il peut donc sembler naturel de définir un critère de choix glouton pour construire une solution au problème par une heuristique gloutonne.

D'après l'étude des deux cas particuliers de l'exercice 1, pour minimiser la fonction d'objectif (l'optimisation globale), il semble naturel de guider notre choix d'optimum local selon deux principes :

  • traiter d'abord les tâches de plus petite longueur
  • traiter d'abord les tâches de plus haute priorité

Ainsi on recherche un critère de choix glouton de la prochaine tâche qui réduise l'augmentation de la valeur de la fonction d'objectif (on ajoute des valeurs positives) :

  • la valeur du critère doit être d'autant plus petite que la priorité est grande
  • la valeur du critère doit être d'autant plus grande que la longueur est grande

On recherche alors une fonction croissante selon le paramètre longueur et décroissante selon le paramètre priorité. Deux choix sont :

  • la valeur de la différence longueur \(-\) priorité
  • la valeur du quotient longueur \(/\) priorité

Une fois qu'on a défini le critère de choix glouton, l'algorithme glouton est simple :

  • on réalise un prétraitement en triant les tâches selon le critère
  • on sélectionne les tâches dans l'ordre défini par le prétraitement

Pour traiter un ensemble de \(n\) tâches, le coût du tri en prétraitement, en \(O(n \log(n))\) domine celui de la boucle de sélection en \(O(n)\), ce qui donne une complexité en \(O(n \log(n))\).

Il reste à savoir si ces heuristiques gloutonnes sont correctes ...

Exercice 6

💻 Saisir ses réponses sur Capytale

Tri d'une liste avec une fonction clef de tri

Si on affiche la documentation de la fonction sorted avec help(sorted), on obtient :

📋 Texte
Help on built-in function sorted in module builtins:

sorted(iterable, /, *, key=None, reverse=False)
    Return a new list containing all items from the iterable in ascending order.
    
    A custom key function can be supplied to customize the sort order, and the
    reverse flag can be set to request the result in descending order.

On considère un tableau Python tab = [(8, 'MARIE') , (8, 'ISMAEL'), (7.5, 'ANNE'), (7, 'SARAH')] rassemblant les résultats d'un groupe d'élèves à un devoir noté sur 10.

  • sorted(tab) renvoie une copie superficielle du tableau triée dans l'ordre croissant (ordre lexicographique si les éléments sont des tuple) :
🐍 Script Python
[(7, 'SARAH'), (7.5, 'ANNE'), (8, 'ISMAEL'), (8, 'MARIE')]
  • sorted(tab, reverse=True) renvoie une copie superficielle du tableau triée dans l'ordre décroissant :
🐍 Script Python
[(8, 'MARIE'), (8, 'ISMAEL'), (7.5, 'ANNE'), (7, 'SARAH')]

  • On définit une fonction qui va nous servir de clef de tri :

    🐍 Script Python
    def clef(paire):
    return (paire[1], paire[0])
    • sorted(tab, key=clef) renvoie une copie superficielle du tableau triée dans l'ordre croissant en comparant non pas les valeurs des éléments mais les valeurs de leurs images par la fonction clef :
    🐍 Script Python
    [(7.5, 'ANNE'), (8, 'ISMAEL'), (8, 'MARIE'), (7, 'SARAH')]
    • sorted(tab, key=clef, reverse=True) renvoie une copie superficielle du tableau triée dans l'ordre décroissant en comparant non pas les valeurs des éléments mais les valeurs de leurs images par la fonction clef :
    🐍 Script Python
    [(7, 'SARAH'), (8, 'MARIE'), (8, 'ISMAEL'), (7.5, 'ANNE')]

🗝️ Python propose d'autres fonctions built-in d'ordre supérieur qui prennent en paramètre une autre fonction servant de clef paramétrant le traitement : par exemple max et min.

🐍 Script Python
def critere_nom(paire):
    return paire[1]

tab = [(8, 'MARIE') , (8, 'ISMAEL'), (7.5, 'ANNE'), (7, 'SARAH')]
assert min(tab, key=critere_nom) == (7.5, 'ANNE')
assert max(tab,  key=critere_nom) == (7, 'SARAH')

On donne ci-dessous une implémentation de l'algorithme d'ordonnancement glouton :

  • tri_taches réalise le prétraitement en triant les tâches selon le critère de choix glouton qui peut être critere_diff_glouton ou critere_ratio_glouton
  • objectif calcule la valeur de la fonction objectif (somme des temps de complétion pondérés par les priorités) une fois l'ordonnancement réalisé
  • ordonnancement_glouton réalise l'ordonnancement selon un certain critère de choix glouton avec tri_taches et calcule la valeur de la fonction objecti avec objectif, puis renvoie le couple (valeur de l'oobjectif, ordonnancement)

###
import randombksl-nlbksl-nldef tripy-undtaches(listepy-undtaches, clef):bksl-nl """Renvoie le tri de listepy-undtaches bksl-nl selon la fonction de clef de tri"""bksl-nl return sorted(listepy-undtaches, key=clef)bksl-nlbksl-nldef criterepy-undratiopy-undglouton(tache):bksl-nl """Renvoie pour la tache qui est un couple (longueur, priorite)bksl-nl la valeur du quotient longueur / prioritebksl-nl """bksl-nl longueur, priorite = tachebksl-nl return longueur / prioritebksl-nlbksl-nldef criterepy-unddiffpy-undglouton(tache):bksl-nl """Renvoie pour la tache qui est un couple (longueur, priorite)bksl-nl la valeur de la différence longueur - prioritebksl-nl """bksl-nl longueur, priorite = tachebksl-nl return longueur - prioritebksl-nlbksl-nldef objectif(ordopy-undtaches):bksl-nl """bksl-nl Renvoie la valeur de la fonction objectif pour une liste bksl-nl de taches (des couples (longueur, priorite) )bksl-nl La fonction objectif est la somme des temps de complétion pondérésbksl-nl par les prioritésbksl-nl """bksl-nl tempspy-undcompletion = 0bksl-nl somme = 0bksl-nl # à compléter (plusieurs lignes)bksl-nl ...bksl-nl return somme bksl-nlbksl-nlbksl-nldef ordonnancementpy-undglouton(listepy-undtaches, criterepy-undglouton):bksl-nl """Renvoie le couple bksl-nl (valeur de la fonction objectif, ordonnancement des taches selon le critere glouton)"""bksl-nl # à compléter (plusieurs lignes)bksl-nl ...bksl-nlbksl-nlbksl-nldef testpy-undordonnancementpy-undglouton():bksl-nl listepy-undtaches1 = [(7, 2), (46, 3), (10, 6), (36, 10), (17, 6)]bksl-nl assert ordonnancementpy-undglouton(listepy-undtaches1, criterepy-undratiopy-undglouton) == (1338, [(10, 6), (17, 6), (7, 2), (36, 10), (46, 3)])bksl-nl assert ordonnancementpy-undglouton(listepy-undtaches1, criterepy-unddiffpy-undglouton) == (1346, [(10, 6), (7, 2), (17, 6), (36, 10), (46, 3)])bksl-nl print("tests réussis pour ordonnancementpy-undglouton")bksl-nl bksl-nldef comparaison(critere1, critere2, nbpy-undexp):bksl-nl """bksl-nl Pour nbpy-undexp listes de taches aléatoiresbksl-nl Renvoie une liste res :bksl-nl bksl-nl res[0] est le nombre de fois où l'ordonnancement par critere1 et critere2 bksl-nl donnent la même valeur pour la fonction objectifbksl-nl bksl-nl res[1] est le nombre de fois où l'ordonnancement par critere1 est meilleur (plus petit)bksl-nl que celui par critere2bksl-nl bksl-nl res[2] est le nombre de fois où l'ordonnancement par critere1 est meilleur (plus petit)bksl-nl que celui par critere2 bksl-nl """bksl-nl res = [0, 0, 0]bksl-nl for py-und in range(nbpy-undexp):bksl-nl listepy-undtaches = [(random.randint(1, 100), random.randint(1, 10)) for py-und in range(50)]bksl-nl c1, py-und = ordonnancementpy-undglouton(listepy-undtaches, critere1)bksl-nl c2, py-und = ordonnancementpy-undglouton(listepy-undtaches, critere2)bksl-nl if c1 < c2:bksl-nl res[1] += 1bksl-nl elif c2 < c1:bksl-nl res[2] += 1bksl-nl else:bksl-nl res[0] += 1bksl-nl return resbksl-nlbksl-nlbksl-nl#testpy-undordonnancementpy-undglouton()bksl-nl#comparaison(criterepy-undratiopy-undglouton, criterepy-unddiffpy-undglouton, 100)bksl-nl

Question 1

  1. Compléter la fonction objectif puis la fonction ordonnancement_glouton.
  2. Vérifier que le test unitaire test_ordonnancement_glouton est réussi.
  3. Exécuter comparaison(critere_ratio_glouton, critere_diff_glouton, 100). Quelle conjecture peut-on faire sur le meilleur critère de choix glouton parmi les deux ?

Le critère de choix glouton du quotient longueur \(/\) priorité donne un algorithme glouton d'ordonnancement optimal pour la fonction d'objectif calculant la somme des temps de complétion pondérés par les priorités.

La preuve est disponible dans le livre de Tim Roughgarden part 3 : greedy algorithms and dynamic programming, il a également réalisé deux capsules video. La preuve repose sur un argument d'échange classique dans les preuves de correction d'algorithmes gloutons : on démontre qu'on peut modifier une solution optimale en échangeant des tâches dans son ordonnancement pour qu'elle soit une solution construite par l'algorithme glouton.

Video

🐍 Script Python
import random

def tri_taches(liste_taches, clef):
    """Renvoie le tri de liste_taches 
    selon la fonction de clef de tri"""
    return sorted(liste_taches, key=clef)

def critere_ratio_glouton(tache):
    """Renvoie pour la tache qui est un couple (longueur, priorite)
    la valeur du quotient longueur / priorite
    """
    longueur, priorite = tache
    return longueur / priorite

def critere_diff_glouton(tache):
    """Renvoie pour la tache qui est un couple (longueur, priorite)
    la valeur de la différence longueur - priorite
    """
    longueur, priorite = tache
    return longueur - priorite

def objectif(ordo_taches):
    """
    Renvoie la valeur de la fonction objectif pour une liste 
    de taches (des couples (longueur, priorite) )
    La fonction objectif est la somme des  temps de complétion pondérés
    par les priorités
    """
    temps_completion = 0
    somme = 0
    for tache in ordo_taches:
        longueur, priorite = tache
        temps_completion =  temps_completion + longueur
        somme = somme + temps_completion * priorite 
    return somme        


def ordonnancement_glouton(liste_taches, critere_glouton):
    """Renvoie le couple 
    (valeur de la fonction objectif, ordonnancement des taches selon le critere glouton)"""
    ordo = tri_taches(liste_taches,  critere_glouton)
    return (objectif(ordo), ordo)


def test_ordonnancement_glouton():
    liste_taches1 = [(7, 2), (46, 3), (10, 6), (36, 10), (17, 6)]
    assert ordonnancement_glouton(liste_taches1, critere_ratio_glouton) == (1338, [(10, 6), (17, 6), (7, 2), (36, 10), (46, 3)])
    assert ordonnancement_glouton(liste_taches1, critere_diff_glouton) == (1346, [(10, 6), (7, 2), (17, 6), (36, 10), (46, 3)])
    print("tests réussis pour ordonnancement_glouton")
    
def comparaison(critere1, critere2, nb_exp):
    """
    Pour nb_exp listes de taches aléatoires
    Renvoie une liste res :
    
    res[0] est le nombre de fois où l'ordonnancement par critere1 et critere2 
    donnent la même valeur pour la fonction objectif
    
    res[1] est le nombre de fois où l'ordonnancement par critere1 est meilleur (plus petit)
    que celui par critere2
    
    res[2] est le nombre de fois où l'ordonnancement par critere1 est meilleur (plus petit)
    que celui par critere2    
    """
    res = [0, 0, 0]
    for _ in range(nb_exp):
        liste_taches = [(random.randint(1, 100), random.randint(1, 10)) for _ in range(50)]
        c1, _ =  ordonnancement_glouton(liste_taches, critere1)
        c2, _ =  ordonnancement_glouton(liste_taches, critere2)
        if c1 < c2:
            res[1] += 1
        elif c2 < c1:
            res[2] += 1
        else:
            res[0] += 1
    return res


#test_ordonnancement_glouton()
#comparaison(critere_ratio_glouton,  critere_diff_glouton, 100)