Notes de cours d'ordonnancement

Chapitre I : IntroductionChapitre II : Complexite des problemes d’ordonnancement

Chapitre III : Methodes de ResolutionLes algorithmes approches

Chapitre IV : Ordonnancement sur machines paralleles

Cours d’ordonnancement

Adel ESSAFI

December 7, 2013

Adel ESSAFI Cours d’ordonnancement




PLAN

1 Chapitre I : Introduction

2 Chapitre II : Complexite des problemes d’ordonnancement

3 Chapitre III : Methodes de ResolutionCritere de performancemethodes Exactes

4 Les algorithmes approches

5 Chapitre IV : Ordonnancement sur machines paralleles





Introduction : un ordonnancement c’est quoi?





Definition

Definition

Le probleme d’ordonnancement consiste a organiser dans le tempsla realisation d’un ensemble de taches, compte tenu de contraintestemporelles (delais, contraintes d’enchainements, ...) et decontraintes portant sur l’utilisation et la disponibilite des ressourcesrequises.





Donnees d’un probleme d’ordonnancement

Les taches : Un ensemble de taches avec eventuellement descontraintes ou de carateriques speciales.

Ressources : Un environnement de ressources pour effectuerles taches

Fonction Objectif : Un critere d’optimisation

Objectif : Determiner les ressources sur lesquelles les taches vonts’executer ainsi que les dates de debut d’execution





Exemple : Gestion des projets

Grands Projets

Chantiers de constructions

...........................





Exemple : Ateliers

Ateliers simples (menuisier avec une seule machine )

Ateliers complexes (plusieurs etages sequentiel / Paralleles )

...........................





Exemple : Administration

Gestions des ressources humaines

Emploi de temps

Gestions des pauses dans les centres d’appels

...........................





Exemple : Informatique

Partage des ressources (processeur) entre les processus

Partage des coeurs entre les processus

Gestion des ressources partages

Ordonnancement sur les plateformes de calcul distribues(machines paralleles, grilles, cloud ...)





Taches : proprietes

Duree : depends des ressources / environnement

Ready date (date de debut au plus tot) : c’est la date avantlaquelle la tache ne peut pas etre executees.

Due date: c’est la date buttoire (imposee par des intervenantsexternes : contrainte a respecter).

Nature de la tache : tache simple (s’execute sur uneressources unique), taches avec queue .....

Dependances : Relation de precedence entre les taches





Taches : Illustration





Taches : dependance





Ressources

Machines qui executent les taches

Une ou plusieurs machines

Organisation : parallele / serie (ordre de passage des taches )

Une ressource execute une seule tache a la fois





Objectifs

Quelle est la fonction a optimiser ?Exemples (minimiser le temps):

Temps d’attente devant une chaisse (social?)

Nombre de taches en retards / retard maximal

La date de fin de la derniere tache executee

Moyenne des dates de fin d’execution des taches

Exemples (minimiser l’utilisation des ressources):

Ordonnancement economique : utiliser le nombre minimal deressources

Reseau: Optimiser l’utilisation de la bande passante

Probleme de transport : minimiser les distances parcourues.

....................





Notations et Definition

Graphe de taches G = (V ,E )V : ensemble de taches (instruction selon la granularite)E : ensemble d’arretes (representent les liens entre ces taches(associes au volume des donnees a transferer).Statique : Structures et volume connus a priori Dynamique : levolule des donnees est connu au fur et a mesure du deroulementl’executionrelation de precedence : relation d’ordre partiel

Vi ≺ Vj

La tache Vi doit s’executer entierement avant de commencerl’executuion de Vj





Notations et Definition

Definition

Ordonnancer un systeme de taches, c’est determiner les deuxapplications π et σ ou π associe un processeur a chaque tache et σleur associe un temps de debut d’execution.





Notations

rj : release datedj : due datewj : poid de la tache Cj = σ(j) + pj : date de fin d’executionLj = max(dj − Cj) : retard Ui : date de retard





Ordonnancement realisable

Un ordonnancement est realisable ssi

σ(j) ≥ σ(i) + pi + λ(i , j)

et ce pour tout (i , j) telque i ≺ jλ(i , j) : temps necessaire au transfert de donnee de Vi a Vj





Notation a 3 champs

Le schema de classification propose par (Graham et al, 1979).Classification a trois champs α|β|γα : environnement des machines β : les caracteristiques des tachesγ : critere(s) a optimiser





Le champs α

Caraterise les ressources

Compose de deux sous champs α1α2

Une seule machine ⇒ α1 = et α2 = 1

Machines paralleles : α1 ∈ {P,Q,R} et α2=nombre demachines

Ateliers α1 ∈ {F , J,O}





Le champs β

Caraterise les taches

β = β1β2β3β4....

β1 = pmtn si la preemption des taches est autorisee, sinon β1est absent

S’il y a des contraintes de precedence entre les taches alorsβ2 ∈ {prec , chain, in − tree, out − tree}, sinon β2 est vide

β3 = rj si les dates de debut au plus tot rj (ou dates dedisponibilite) des taches ne sont pas forcement identiques

..................





Le champs γ

fonction objectif : critere de performance

Cmax : Makespan

Lmax : Retard maximal∑WjCj : Somme ponderees des dates de fin∑UJ : Nombre de taches en retards





Introduction

Ordonnancement (pb combinatoire ) : complexite est unequestion importante

Probleme complexe : recherche d’un algorithme efficace(optimal)

Dans le cas contraire, il est pratique de montrer que ceprobleme est NP-difficile





Probleme de calcul

Ordonnancement (pb combinatoire ) : complexite est unequestion importante

Probleme complexe : recherche d’un algorithme efficace(optimal)

Dans le cas contraire, il est pratique de montrer que ceprobleme est NP-difficile





Probleme de calcul

Fonction h qui transforme toute entree x de taille |x | en unesortie h(x).

Mesure d’efficacite : nombre d’instruction pour effectuer cettetransformation

Nombre d’instruction depend de la taille de x

Taille de l’entree : taille de la plus grande valeur enrepresentation binaire

Exemple : un entier a est represente sur log2a bits

Exemple : un tableau de taille m est represente sur mlog2abits ou a est le plus grand entier present

Objectif : Determiner T (n) : Nombre d’instructions de h au piredes cas.





Regles de calcul

Blocks consecutifs : on retient la complexite du plus grandblock

Brachement : On retient la complexite du plus grand blockparmis les blocks alernatifs

Voir cours complexite des algorithmes





Notation en O

on note f = O(g) ssi∃C > 0 , ∃n0 telque ∀n > n0 , |f (n)| ≤ cg(n)





Classes d’algorithmes

Polynomial

Pseudo-polynomial





Probleme de decision

Un probleme de decision est defini par:

un nom

des parametres generiques (Instance)

une question.





Probleme de decision : Exemples

Probleme PARTITION:Instance:A = a1, ....., anQuestion: Existe t-il un sous ensemble B de A telque∑

i∈Bai =

∑i∈A*{B}ai





Probleme de decision : Exemples

Vertex Cover (Couvrant):Instance:Un Graphe G=(V,E)Un Entier k Question: Existe t-il un un sous ensemble V ′ de V detaile k telque chaque arrete de E soit adjacente au moins a unelement de V ′.Vertex Cover:

Minimum Vertex Cover:





Definition des certificats

Etant donne un enonce I de longueur n, on se pose la question:A partir de quelle information sur I , de longueur polynomiale en n,peut-on verifier que I est a reponse ”oui”?On appelle alors certificats de I les informations susceptibles depermettre cette verification.En anglais, si une instance a une reponse oui , elle est noteeyes-instance.





Definition de l’algorithme de verification

On construit un algorithme de verification V , dont les donneessont les couples (I , c) ou c est une instance de I, tel que :

si I est une entree valide du probleme, alors, il existe uncertificat c tel que V repond oui pour la donnee (I,c)

si I n’est une entree valide du probleme, V repond non pourtoute donnee (I,c)

V est de complexite polynomiale la taille de I





Reduction de KARP

Soient L1 et L2 deux langages sur un alphabet Σ.Une fonction τ de Σ∗ vers Σ∗ est une reduction de L1 vers L2 ssi:

∀x ∈ Σ∗, x ∈ L1⇔ τ(x) ∈ L2

τ est une transformation polynomiale





Reduction de problemes

Soient π et π′ deux problemeπ se reduit a π′ , note π ∝ π′ ssi :τ transforme toute instance positive de π en un instance positivede π′ et transforme toute instance negative de π en un instancenegative de π′.⇒ : π′ est au moins aussi difficile que π.La reduction est une relation d’ordre entre les problemes





Critere de performancemethodes Exactes

Ratio d’approximation

Le rapport d’approximation d’un algorithme A pour un problemede minimisation :

ρA = inf {r ≥ 1 tel que ρA(I ) ≤ r}

pour toutes les instances I

ρA(I ) =wA(I )

w∗(A): rapport de la valeur de l’objectif de A a l’optimal

pour l’instance I






Programmation lineaire

Probleme d’affectation des taches aux ressources:Objectif :

min(maxk∑i

aikpi )

Variables d’affectation

aik =

{1 si la tache i est affectee a la machine k

0 sinon.

Contraintes d’affectation : ∀i∑

k aik = 1Une tache est affectee exactement a 1 machineDate de fin sur la machine k :

∑i piaik






Branch and Bound





Algorithmes de liste

Priorite sur les taches : liste L

Sequencement glouton des tachesSi la ressource est libre, sequencer la premiere tache disponiblede la liste

Principe glouton:ne pas laisser la ressource inoccupee si destaches sont disponibles

La liste sert a arbitrer lorsque plusieurs taches sont disponiblesen meme temps





Listes optimales

1||Ci : Liste SPT1||Tmax : Liste EDD1|ri |Cmax :∀ liste L





Algorithme de Liste

Tout algorithme de liste a une garantie 2− 1m pour Pm||Cmax

Borne atteinte avec SPT pour l’instance suivante :

m(m − 1) taches de duree 1

1 tache de duree m

Nous avons alors

Cmax(SPT ) = 2m − 1

C ∗max = m





Algorithme LPT

Placer d’abord les taches les plus longuesListe LPT (Largest Processing Time) : sequence des taches parduree decroissanteL’algorithme de liste LPT a une garantie 4/3− 1/3m pourPm||Cmax et cette borne est atteinteInstance limite:

m machines

2m + 1 taches de tailles(2m − 1, 2m − 1, 2m − 2, 2m − 2, ....,m,m,m)

Pour cette instance nous avons,

Cmax(LPT ) = 4m − 1

C ∗max = 3m






Education

Notes de cours d'ordonnancement