Ordonnancement : entre th eorie et applicationsejc-gdr-ro.event.univ-lorraine.fr/docs/rapine.pdf · 3 Trois ingr edients fondamentaux Desactivit es a r ealiser Desressourcespour les

1

Ordonnancement : entre theorie et applications

Christophe RAPINELaboratoire LGIPM, universite de Lorraine

Ecole des Jeunes Chercheurs du GDR-RO


2

Qu’est-ce que l’ordonnancement ?

Organiser la realisation d’un ensemble detaches

⇒ Planification dans le temps

⇒ En respectant des contraintes

⇒ Pour optimiser un critere (finir le plus vitepossible, en faire le plus possible avantune date limite, sans trop de retard, . . .)


3

Trois ingredients fondamentaux

• Des activites a realiser

• Des ressources pour les realiser

• Le temps

Qui fait Quoi et Quand ?


4

Terminologie

Donnees d’un probleme d’ordonnancement

Un probleme d’ordonnancement est defini par

• Un ensemble de ressourceshommes, machines, camions, budget . . .

• Un ensemble d’activites necessitant ces ressourcestaches d’un projet, produits a usiner, commandes a livrer, . . .

• Un ensemble de contraintes a respectercapacites des ressources, precedences entre les taches. . .

• Un objectiffinir au plus vite, minimiser les retards, . . .


5

Decisions attendues

Probleme d’ordonnancementIl faut decider :• De l’allocation des ressources aux activites

• Du sequencement des activites sur chaqueressource → date de debut des activites


6

Visualisation d’un ordonnancement

Diagramme de Gantt

Representation ressources/temps de l’ordonnancement

Nomme d’apres Henry Gantt (1861-1919)


7

Les domaines de l’ordonnancement

• Production,

• Gestion de projets,

• Logistique, transport

• Emplois du temps, gestion des ressources humaines, hopitaux

• Informatique, . . .


8

Exemple du menuisier

Un menuisier doit realiser 4 commandes

a livrer dans temps de travail

1 table 4 jours 2 jours6 chaises 6 jours 5 jours1 vaisselier 7 jours 2 jours1 commode 5 jours 4 jours

• Minimiser le plus grand retard

• Minimiser le nombre de commandes enretard

→ Ordonnancement sur une ressource


9

Exemple : Ordonnancement en transport routier

• Des clients a livrer en direct depuisun entrepot

• Une flotte de camions a disposition

• Comment effectuer les livraisons ...


10

Exemple : Ordonnancement en transport routier

Livraison a effectuer dans la journee

duree A/R + Chargement fenetre de livraison

client 1 90 mn 6h - 8h30client 2 80 mn 7h - 8hclient 3 70 mn 7h - 9hclient 4 120mn 7h30 - 9h30. . . . . . . . .

• Livrer toutes les commandes a l’heure

• Minimiser les penalites de retard/avance

→ Ordonnancement sur machines paralleles


11

Gestion de quais de dechargement

• Porte-containers/cargos a decharger

• Des quais avec des equipements et des longueurs differentes

• Comment gerer le plan d’ammarrage ?

• Pour maximiser le debit du port, minimiser les tempsd’attente des cargos, obtenir un ammarrage equitable

→ Ordonnancement multi-ressource : RCPSP


12

Ordonnancement d’atelier

• Atelier de montage/Ligne deproduction

• Les produits passent d’un poste aun autre : jobs avec un ensembled’operations a realiser

• Machines specifiques (dediees)pour realiser les operations

• Allocation fixee des ressources auxoperations

→ Ordonnancement sur machines en serie : flowshop/jobshop


13

Vocabulaire


14

Types de Ressources

RessourceUne ressource est un moyen materiel (machine, homme, argent)necessaire pour executer les taches.

Une ressource peut etre

• a capacite limiteepar exemple au plus une tache peut l’utiliser a chaqueinstant : ressource unitaire

• renouvelablerendue apres son utilisation (outil, main dœuvre, machine, . . .)

• non renouvelableson utilisation consomme la ressource (budget)


15

Activite

ActiviteUne activite (ou tache) est une operation elementaire dont larealisation necessite un certain nombre d’unites de temps (duree dela tache) et d’unites de chaque ressources.

Notations

• Un ensemble de n taches a ordonnancer, numerotees de 1 a n

• La duree de la tache i est pi

• A determiner : la date de debut ti de la tache i , ou sa date defin Ci .


16

Contraintes

ContraintesSpecifient quels sont les ordonnancements realisables, ce qu’il estpossible de faire (en respectant les capacites physiques, lesengagements contractuels, les objectifs commerciaux, etc).

Types de contraintes :

1 Contraintes potentielles (ou de potentiels)

2 Contraintes disjonctives

3 Contraintes cumulatives


17

Contraintes Potentielles

Formes generales

Si i et j sont 2 taches, containtes ti − tj ≥ aij

• Date de disponibilite : i ne peut debuter avant une certainedate ri (livraison de matiere premiere, . . .)

• Date butoir : j doit etre terminee avant une certaine date di

• Contrainte d’anteriorite (precedence) : i doit attendre que jsoit achevee pour debuter.


18

Contraintes Disjonctives

DefinitionDeux taches i et j sont en disjonction si elles ne peuvent etreexecutees simultanement.

• Leurs intervals d’execution doivent etre disjoints

• Contrainte ti − tj ≥ pj ou tj − ti ≥ pi

⇒ Cas de 2 taches demandant une meme ressource unitaire pours’executer.


19

Contraintes Cumulatives

• Generalisation des contraintes disjonctives a des ressourcesnon unitaire

• Generalement chaque ressource k a une capacite ak(t)

• A chaque instant t, l’ensemble des activitees executees ne doitpas requerir plus que la capacite ak(t) de la ressource k .

• Par exemple, la consommation electrique ne peut depasser atout instant la puissance disponible


20

Notation 3 champs

Notation α|β|γ• α Description des ressources

nombre de ressources, type de ressource : {1, P3,F 2, . . .}• β Caracteristique des taches

precedences, date d’arrivee, . . .

• γ Critere a optimiserExprime en fonction de la date de fin Ci des taches

On considere que les taches et leurs caracteristiques sont connueslors de l’ordonnancement→ problemes off-lineProblemes tres souvent NP-difficiles (Complexity results forscheduling problems)http://www.informatik.uni-osnabrueck.de/knust/class/


21

Ordonnancement sur une ressource

Une seule ressource unitaire• une machine qui doit realiser un ensemble de taches

Sequencement

Il faut decider :

• l’ordre d’execution des taches sur la ressource


22

Probleme 1||Cmax

Makespan Cmax• Objectif : minimiser la duree totale de

l’ordonnancement

• Cmax = maxi Ci

• 4 taches a ordonnancer

A B C D

pi 5 2 1 3

• Toute sequence est optimale !

• Minimiser le makespan devient NP-difficile sur machineparallele (P2||Cmax)


23

Probleme 1||∑

Ci

Total flow time∑

Ci

• Objectif : minimiser la date de finmoyenne des taches

• attente moyenne des clients dans une file

• stocks d’encours devant la ressource


24

Quai de dechargement

Une grande entreprise de metallurgie possede un site en bord demer. L’approvisionnement en matiere premiere (minerais, charbon)s’effectue par voie maritime.

• Le quai de dechargement du site nepeut acceuillir qu’un seul navire ala fois.

• Les autres navires doivent attendreen mer.

• un jour d’attente d’un navire estfacture 5000 euros

• Comment gerer le pland’ammarrage ?


25

Probleme 1||∑

Ci

• 4 taches a ordonnancer

A B C D

pi 5 2 1 3

• Sequence σ = ABCD valeur∑

Ci = 31

A B DC

temps

5 87 11• Sequence σ′ = CBDA valeur

∑Ci = 21 optimal ?

C B D A

temps

3 6 111


26

Comment prouver l’optimalite d’une politique ?

Argument d’echange

• On considere 2 taches successives

• On cherche a quelle condition un echange ameliorel’ordonnancement

j i

i j

C iC j

C’ i C’ j

D F

Cj + Ci = D + pj + F

C ′i + C ′j = D + pi + F


27

Dominance

Definition (Dominance)

Une propriete D est une dominance si pour toute solution π,il existe une solution π′ au moins aussi bonne que π et verifiant lapropriete D.

Solutionsréalisables

Solutionsoptimales

Propriété D


28

Probleme 1||∑

Ci

DominanceDeux taches successives sont ordonnancees dans l’ordre des tempsoperatoires croissants

si i et j se succedent, alors pi ≤ pj

temps

i j


29

Regle SPT

SPTLa regle SPT (Shortest Processing Time) sequencant les tachespar duree operatoire croissante est optimale pour 1||

∑Ci

• Il doit exister une sequence optimale verifiant la dominance

• Seule la sequence SPT verifie la dominance


30

Stretch

Dans la file d’attente aux caisses d’un supermarche, nous sommesnaturellement plus disposer a patienter si l’on a achete un groscaddie plutot que si l’on a trois articles dans la main.

• Le temps d’attente “acceptable”est proportionnel au temps deservice

• Le stretch d’une tache est definicomme son temps dans le systemedivise par sa duree

• Si = Ci/pi

Comment minimiser le stretch moyen d’une file d’attente∑

i Si ?


31

Probleme 1||∑

wiCi

On peut generaliser la regle SPT en presence de poids wi > 0associes a chaque tache

• cout financier (stockage)

• importance, criticite de la tache (attente client)

Exemple de 5 taches a ordonnancer sur une ressource :

A B C D E

pi 1 2 4 5 6wi 2 1 3 5 4

wSPTLa regle wSPT sequencant les taches par ratio pi/wi croissant estoptimale pour 1||

∑wiCi


32

Quai de dechargement (suite)

Tous les navires n’arrivent pas en meme temps sur le site !

• Le planning d’arrivee des bateauxest connu sur une perioderelativement longue.

• Date ri (release date)d’arrivee/disponibilite de la tache i

⇒ Des temps d’inactivite (idle time) peuvent apparaıtre sur laressource


33

Ordonnancement semi-actif

DefinitionUn ordonnancement est semi-actif si il n’est pas possible d’avancerl’execution des taches sans remettre en cause l’ordre d’execution

⇒ Sequence calee a gauche

Les ordonnancements semi-actif sont dominants pour les criteresreguliers. . . mais pas necessairement optimaux


34

Algorithme de Liste

Algorithme 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


35

Algorithme de Liste

Propriete

Les algorithmes de liste construisent des ordonnancementssemi-actifs

Selon le probleme d’ordonnancement :

• Toutes les listes conduisent a un ordonnancement optimal

• Il existe des listes conduisant a l’optimal

• Aucune liste ne permet d’etre optimal sur toutes les instances

Listes optimales

1||∑

Ci liste SPT

1|ri |Cmax ∀ liste L


36

Optimalite pour 1|ri |Cmax

Montrons que tout algorithme de liste L minimise le makespan. Lemakespan Cmax(L) est imposee par la derniere tache, l .Elle ne commence pas plus tot car :

• soit elle n’est pas disponible avant

• soit la ressource est occuppee avant

BlocDans un ordonnancement, on appelle bloc une suite (maximale) detaches sans temps mort.

Cmax

lk


37


Propriete

Dans un ordonnancement semi-actif, la premiere tache d’un blocest executee a sa date de disponibilite (ou a l’instant 0).

Cmax

lk

• La duree de l’ordonnancement est Cmax(L) = rk + p(B)

• Borne inferieure : l’ordonnancement optimal a une duree

C ∗max ≥ mini∈S

ri + p(S) ∀S ensemble de taches


38


Propriete

Dans un ordonnancement obtenu par un algorithme de liste,aucune tache d’un bloc n’est disponible avant le debut du bloc.

Cmax

lk

ri ≥ rk pour toute tache i du dernier block

• Il suffit d’ecrire la borne inferieure pour S = B, le dernier bloc

• On en deduit que C ∗max ≥ rk + p(B) = Cmax(L)


39

Probleme 1|ri |∑

Ci

A B C D

pi 5 2 1 3ri 0 9 1 8

• Liste SPT CBDA valeur∑

Ci = 35 Quelle que soit la liste !

A

5 11 temps

C BD

6 8 13• Sequence CABD valeur

∑Ci = 33

11 temps

BD

8 131 2 7

AC


40

Probleme 1|ri |∑

Ci

Dans la sequence optimale, il peut etre necessaire de laisser laressource inoccuppee meme si des taches sont disponibles

• Tout algorithme de liste peut etre arbitrairement mauvais

• Par exemple si on doit ordonnancer 1 tache tres longueimmediatement disponible, et des taches tres courtes quiarrivent juste apres.


41

Probleme 1|ri |∑

Ci

Propriete

Le probleme 1|ri |∑

Ci est NP-difficile (au sens fort)

Il n’existe pas de regle ”simple” pour trouver l’optimum

• Algorithme exacte d’enumeration (Branch & Bound)

• Heuristiques, Algorithmes d’approximation


42

Borne inferieure ?

Comment obtenir une borne inferieure ?

• Resoudre a l’optimum une relaxation du probleme,

• Suppression des precedences, des dates de disponibilite,

• Ajouter des ressources additionnelles, augmenter la vitesse,

• Autoriser la preemption, . . .


43

Probleme 1|ri |∑

Ci

5 taches a ordonnancer :

A B C D E

pi 10 4 1 1 2ri 0 2 4 6 8

Quelle borne inferieure ?

• Infinite de ressources ?

• Sans date de disponibilite ?


44

Preemption

DefinitionLa preemption est la possibilite d’interrompre l’execution d’unetache pour la reprendre ulterieurement.

• Dans certaines situations (usinage d’une piece, service) lapreemption n’est pas envisageable, ou alors a un cout treseleve

• Dans d’autres cas, elle peut entrainer des tempssupplementaires (reglages, context swap, reprise partielle)


45

Probleme 1|ri , pmtn|∑

Ci

5 taches a ordonnancer pour minimiser la date moyenne de fin :

A B C D E

pi 10 4 1 1 2ri 0 2 4 6 8

Avec la preemption, le probleme devient “facile” :

SRPTLa regle SRPT (Shortest Remaining Processing Time)ordonnancant a chaque instant la tache disponible de plus petittemps restant est optimale pour 1|ri , pmtn|

∑Ci


46

SRPT : Exemple

5 taches a ordonnancer :

A B C D E

pi 10 4 1 1 2ri 0 2 4 6 8 C

A

B

D

0 2 4 6 8 10

E

Algorithme SRPT,∑

i Ci (SRPT ) = 48


47

Probleme 1|ri |∑

Ci : Approximation

Algorithme de Phillips Stein & Wein

Ordonnancer les taches dans l’ordre de leur date de fin Cpreempti

dans l’ordonnancement SRPT preemptif

Ordonnancement SRPT, z∗ = 48

115 7 8 18

C AD B E


48

Probleme 1|ri |∑

Ci : Approximation

• Ordonnancement SRPT, z∗ = 48

• Ordonnancement PSW : CDBEA, z = 59

23

5 7 8 18

C AD B E

11

5 7 11 13


49

Probleme 1|ri |∑

Ci : Approximation

Algorithme de Stein

L’algorithme de Phillips Stein & Wein a une garantie 2

PreuvePour toutes les taches, C PSW

i ≤ 2Cpreempti

Remarque

La garantie 2 est a priori. On peut sur chaque instance regarder lagarantie a posteriori on se comparant a la relaxation preemptive.∑

i

C PSWi /OPT ≤ 59/48 ' 1, 23


50


Un menuisier doit realiser 4 commandes

a livrer dans temps de travail

1 table 4 jours 2 jours6 chaises 6 jours 5 jours1 vaisselier 7 jours 2 jours1 commode 5 jours 4 jours

• Minimiser le plus grand retard


51

Date echue

• Chaque taches doit etre idealementterminee a une date donnee, au delade laquelle elle est consideree en retard

• Date echue di (due date)

• On veut bien sur eviter le retard destaches. . .


52

Les indicateurs de retard

Pour un ordonnancement fixe et une tache i :

• Tardiness Ti = max{Ci − di , 0}retard de la tache i par rapport a sa date echue

• Lateness Li = Ci − di retard algebrique

• Ui , indicatrice de retard

Ti

Cdi i

i


53

Criteres classiques de retard

A partir des retards individuels des taches, on peut construire desmesures globales de retard pour l’ordonnancement :

• Tmax = maxi Ti , le plus grand retard

•∑

Ti retard total, ou moyen

•∑

i Ui nombre de taches en retard

• Lmax = maxi Li , le plus grand retard algebrique

On peut bien sur ponderer ces criteres


54

Probleme 1||Tmax

• Objectif : minimiser le plus grand retard maxi Ti

A B C D

pi 5 2 1 3di 8 7 3 6

• Sequence σ = ABCD valeur Tmax = 5

A B DC

temps

5 87 11


55

Regle EDD

EDDLa regle EDD (Earliest Due Date) sequencant les taches par dateechue croissante est optimale pour 1||Tmax

Remarque. Regle tres naturelle : plus urgent d’abord.Ce qui est remarquable : ne depend pas des temps de process


56

Contraintes de precedence

Contraintes inherentes aux activites a realiser :

• On ne peut plus commencer par n’importe quelle tache

• Certaines taches doivent attendre la terminaison d’autrestaches pour pouvoir debuter

• Precedence i → j : la tache j ne peut commencer avant la finde i .

i j


57

Contraintes de precedence

On decrit l’ensemble des precedences par un graphe

• nœuds : taches a realiser

• arc : precedences i → j entre taches

• le graphe doit etre acyclique

A

B

C

D

E

Precedences

A→ CA→ DB → DC → E


58

Algorithme de Lawler

• Plutot que de passer en revue les differents criteres que nousconnaissons

• Nous allons voir un algorithme, propose par Lawler, optimalpour toute une classe de criteres

• Ce sont les criteres qui sont bottleneck et regulier


59

Criteres Reguliers

Critere Regulier

Un critere f est regulier si il est croissant avec les dates Ci

Si la date de fin de chaque tache augmente, alors la valeur ducritere pour l’ordonnancement augmente

Ci (π) ≥ Ci (π′) ∀ tache i ⇒ f (π) ≥ f (π′)

Pour un critere regulier, on est incite a finir au plus tot chaquetache, c-a-dire a ne pas laisser inutilement la machine inoccupee(idle)


60

Criteres Bottleneck

La plupart des criteres pour un ordonnancement sont des fonctionsde la mesure individuelle des taches fi (Ci ). C’est a dire

f (π) = g (f1(C1), . . . , fn(Cn))

Les criteres les plus usuels considere la plus grande des valeurs oula somme de ces valeurs.

• fmax(C ) = maxi fi (Ci ) bottleneck

• fsum(C ) =∑

i fi (Ci ) sum

Ces criteres sont reguliers simplement si la mesure fi pour chaquetache i est croissante avec la date de fin Ci


61

Problemes 1|prec|fmax

Critere bottleneck regulier fmax, par exemple Tmax


1 Partir de la fin de l’ordonnancement (t =∑

pi )

2 Placer en dernier la tache i sans successeur (non ordonnance)qui minimise fi (t)

3 Retrancher pi a t et retourner a l’etape 2 si t > 0

Propriete

L’algorithme de Lawler est optimal pour tout critere regulier fmax

Sa complexite est O(n2).


62

Algorithme de Lawler : Exemple

On veut minimiser le plus grand retard (1|prec |Tmax)

A

B

C

D

E

A B C D E

pi 2 3 1 2 4di 8 7 3 6 11

• Quelle sequence donne l’algorithme de Lawler ?

• Ordonnancement ACBDE, retard maximal de 2 pour D


63

Lateness

Un autre critere : le retard algebrique (lateness)

• A chaque tache est associe un temps de latence qi

• Une fois la tache i traitee par la ressource, il faut attendre undelai qi avant de pouvoir disposer de la tache

• Pendant le delai la tache ne consomme aucune ressource

• La lateness Li de la tache i est la date :

Li = Ci + qi

pi

0 C

q

Li i

i


64

Probleme 1||Lmax

Le temps de latence qi peut representer :

• Un temps de sechage dans un process depeinture

• Un temps de refroidissement

• Un temps d’acheminement par la posted’une commande vers le client

• Temps de post-traitement sur unemachine de capacite infinie.


65

Probleme 1|ri |Lmax, latence maximale

Regle de Jackson

La regle de Jackson sequencant les taches par qi decroissant estoptimale pour 1||Lmax.

Mauvaise NouvelleLe probleme 1|ri |Lmax est NP-difficile.


66

En autorisant la preemption

Est-ce que la preemption rend toujours le probleme plus facile ?

• Non. En particulier la preemption peut etre inutile.

• Dans le cas d’un critere de type bottleneck, on a un resultatsimilaire a l’algorithme de Lawler :

TheoremeLe probleme 1|ri , pmtn|fmax peut etre resolu en temps O(n2) pourtout critere bottleneck regulier fmax


67

Probleme 1|ri , pmtn|fmax

Pour un critere regulier avec la preemption :

• Il est dominant de ne pas laisser la ressource inoccuppee siune tache est disponible

• L’optimal a la structure de block, obtenu par tout algorithmede liste

C(B)r(B)

B

k


68


Considerons un bloc de l’optimal :

• Forme de l’ensemble de tache B• Finissant a la date t = C (B)

Borne inferieureSi l est la tache de B de plus petite valeur fi (t), on a :

OPT (B) ≥ max{ OPT (B\{l}), fl(t) }


69


Idee de l’algorithme :

• On construit un ordonnancement qui realise la borneinferieure.

Principe de fonctionnement :

• On traite separement chaque block B, obtenu par la sequencedes ri croissant (ou tout algorithme de liste)

• Sur le block B, on identifie la tache l minimisant fi (C (B))

• On determine recursivement l’ordonnancement optimal pourles taches de B\{l}

• On ordonnance preemptivement l en bouchant les trous pourfinir a la date C (B)


70

Probleme 1|ri , pmtn|Lmax

• Sur notre exemple :

A B C D E

ri 0 1 2 4 5pi 4 2 1 2 3qi 3 2 4 5 6

• On obtient un seul block :

E

4

temps

7 9 12

A B C D

• La tache a retirer est B


71


A B C D E

ri 0 1 2 4 5pi 4 2 1 2 3qi 3 2 4 5 6

• On trouve de nouveau un seul block. On ecarte la tache A

• On obtient 2 block, C et ED

• L’ordonnancement (preemptif) optimal est :

B

temps

A C A D E D A


72


Dans le cas particulier de la lateness maximale, on retrouve la reglede Jackson, appliquee dynamiquement a chaque arrivee d’unetache :

ResultatLe probleme 1|ri , pmtn|Lmax est resolu optimalement enordonnancant a chaque instant la tache disponible de plus grandelatence (regle de Jackson).


73


Un menuisier doit realiser une commande pour un salon

• Certaines planches commandees n’ont pas encore ete livrees,

• Chaque meuble doit etre vernis

livraison planches temps de travail sechage vernis

1 table 1 jour 2 jours 2 jours6 chaises en stock 5 jours 1 jour1 vaisselier 6 jours 2 jours 2 jours1 commode 6 jours 4 jours 3 jours

Quel ordonnancement minimise la date delivraison de la commande ?


74

Probleme 1||maxi wiTi

• Un poids wi peut etre associe a chaque tache, traduisantl’impatience du client pour chaque unite de temps de retard

• On souhaite minimiser le plus grand mecontentement d’unclient, maxi wiTi

• L’algorithme de Lawler construit la sequence optimale(bottleneck reguliers)


75


On veut minimiser le plus grand retard pondere pour les 3commandes suivantes :

taches A B C

pi 2 3 5di 8 7 5wi 4 3 2

• Quelle sequence donne l’algorithme de Lawler ?

• Ordonnancement CBA, retard maximal pondere de 8.


76

Robustesse : incertitudes sur les poids

• L’impatience d’un client dont la commande est en retard peutetre difficile a evaluer precisement

• On ne connait par avance le poids wi : on sait simplementqu’il prend sa valeur dans un intervalle [w−i ,w

+i ]

• Un scenario S correspond a un ensemble de poids (wSi )i=1,n

• F (π,S) correspond a la valeur objectif de la sequence π sousle scenario S .

L’ensemble des scenarios possibles S = [w−1 ,w+1 ]× . . . [w−n ,w+

n ]est infini


77

Regret

Pour une sequence π fixee

• Le regret pour π dans le scenario S est le rapportF (π,S)/F ∗(S)

• C’est ce que l’on a perdu en choisissant π plutot que lasequence optimale pour le scenario S .

• On ne sait evidemment pas a l’avance quel scenario va serealiser. . .

On souhaite trouver une sequence minimisant le plus grand regretsur tous les scenarios possibles :

minπ

maxS∈S

F (π,S)

F ∗(S)


78

Robustesse : Exemple

On veut minimiser le plus grand regret pour le retard pondere :

taches A B C

pi 2 3 5di 8 7 5wi [3, 5] [2, 4] [1, 2]

• Quel est le regret de la sequence CBA ?

• Regret de 2, pour le scenario S = (5, 2, 1).

• Est-ce le scenario de plus grand regret pour la sequence CBA ?


79

Regret maximal d’une sequence

Approche proposee par Averbackh (2000) pour les problemes deminimisation combinatoire de type bottleneck

Propriete

Le regret maximal d’une sequence π est realise par l’un des nscenario Sj , dans lequel la tache j a le plus grand poids possible, etles autres ont leur plus petit poids possible.

Sj : poids wi = w−i pour i 6= j et wj = w+j

On s’est ramene a un petit ensemble de scenarios a evaluer


80

Regret maximal d’une sequence

taches A B C

pi 2 3 5di 8 7 5wi [3, 5] [2, 4] [1, 2]

On a 3 scenarios a considerer :

1 SA = (5, 2, 1), de valeur optimale 5

2 SB = (3, 4, 1), de valeur optimale 5

3 SC = (3, 2, 2), de valeur optimale 6

Le regret maximale de la sequence CBA est

max{F (CBA,SA)

5,

F (CBA,SB)

5,

F (CBA, SC )

6} = max{10

5,

6

5,

6

6}


81

Sequence minimisant le plus grand regret

TheoremeLa sequence π∗ minimisant le plus grand regret est la sequenceoptimale pour le scenario S∗ :

S∗ = (w+1

F ∗(S1), . . . ,

w+i

F ∗(Si ), . . . ,

w+n

F ∗(Sn))

Remarque. Le scenario S∗ est fictif. Il n’appartient pasnecessairement a l’ensemble S des scenarios possibles.


82

Exemple

taches A B C

pi 2 3 5di 8 7 5wi [3, 5] [2, 4] [1, 2]

1 Le scenario S∗ = (5/5, 4/5, 2/6), soit (1, 0.8, 1/3).

2 La solution π∗ est la sequence BAC , de valeurF (BAC , S∗) = 5/3

3 C’est la solution robuste. Son regret maximal est 5/3.


83

Conclusion

• Domaine tres vaste

• Problemes souvent NP-difficiles : approches exactes,algorithmes d’approximation, meta-heuristiques, propagationde contraintes

• Comment prevoir l’imprevu ? Ordonnancement on-line


Documents

Ordonnancement : entre th eorie et applicationsejc-gdr-ro.event.univ-lorraine.fr/docs/rapine.pdf · 3 Trois ingr edients fondamentaux Desactivit es a r ealiser Desressourcespour les