Master Académique,

Domaine : Mathématiques et Informatique

Spécialité : Big Data Analytics, (BigDataA)

Matière : Théorie de l’ordonnancement (THOR)

(2023/2024)

Chapitre 1 :
Introduction
 Ordonnancer c’est programmer l’exécution d’un ensemble de tâches (travaux, tasks ou jobs
en Anglais) en attribuant des ressources aux tâches et en fixant leurs dates d’exécution. Les
problèmes d’ordonnancement apparaissent dans le suivi des projets, les ateliers de production,
les emplois du temps, en informatique, etc. En effet, les tâches peuvent représenter des pièces
mais également des projets, des programmes ou encore des activités, etc. De même, les res-
sources peuvent représenter des machines industrielles mais également des processeurs ou des
personnes, etc. Une ressource est donc un moyen matériel, financier ou humain à disposition
pour la réalisation d’une tâche. Les différentes données d’un problèmes d’ordonnancement
sont, donc, les tâches, les contraintes, les ressources et les objectifs.
Tâche Ressource
Production : pièce machine à outil
Informatique : programme processeur
Construction : plomberie plombier
maçonnerie maçon
.. .. ..
Hôpital : opération chirurgien
Restaurant : repas cuisinier
Recherche : projet chercheur

1
Les contraintes représentent les limites imposées par l’environnement, tandis que l’objectif est
le critère d’optimisation.

Si tous les paramètres des tâches sont connus a priori, le problème est dit déterministe.

Dans les problèmes de l’ordonnancement classique, deux hypothèses importantes sont com-
munément considérées :
(a) à chaque instant, une machine ne peut traiter qu’une seule tâche à la fois et
(b) à chaque instant, une tâche ne peut être traitée que par, au plus, une machine.

En pratique, on rencontre de nombreuses situations où ces hypothèses sont à lever (machines
à traitement par batch, tâches multiprocesseurs, ...).

Les ordonnancements sont généralement représentés par des diagrammes dits de Gantt (voir
l’exemple ci-dessous). Ceux-ci indiquent, selon une échelle temporelle donnée, l’occupation
des machines par les différentes tâches, les temps morts et les éventuelles indisponibilités des
machines dues aux changements de tâches, d’outils, etc.

2
Exemple 1 : Nous voulons traiter 5 tâches T1, T2, T3, T4 et T5 sur 3 machines identiques M1,
M2 et M3 en temps minimal. Supposons que les temps de traitement des tâches sont 3, 5, 2, 1 et
2 et que chaque tâche doit être traitée sans préemption : c’est-à-dire qu’une fois le traitement
d’une tâche commencé on ne s’arrête qu’à l’achèvement de ce dernier. Le diagramme de Gantt
suivant donne une solution optimale.

Machines

M1 T2

M2 T3 T5 T4
✟✟
temps inutilisé
✟✟
M3 T1 ✟✟
✙
✟
✲

0 1 2 3 4 5 temps

Les problèmes de l’ordonnancement sont l’exemple même de problèmes combinatoires où le

nombre de solutions envisageables est si élevé que leur énumération complète ou même leur
évaluation n’est pas envisageable. Ils sont considérés comme des problèmes d’optimisation
combinatoire difficiles.

Leur résolution consiste à trouver un algorithme efficace pour ordonnancer l’exécution des
tâches de façon à optimiser une mesure de performance donnée.

3
1 Illustrations

Exemple n°1 : On désire fabriquer 5 pièces T1, T2, T3, T4, T5 sur 3 machines M1, M2, M3. Les
durées de traitement sont :

pièce T1 T2 T3 T4 T5
durée de traitement 3 5 2 1 2

Quatre hypothèses sont à noter :

- Les machines sont toutes identiques et peuvent exécuter chaque tâche.
- Pas plus d’une tâche par machine au même moment.
- Pas plus d’une machine par tâche au même moment.
- Une fois lancée, la tâche doit être complétée.

On veut terminer les tâches aussi vite que possible.

4
Le diagramme de Gantt suivant représente une solution optimale.

Machines

M1 T2

M2 T3 T4 T5
✟✟
temps mort
✟✟
M3 T1 ✟✟
✙
✟
✲

0 1 2 3 4 5 temps

5
Exemple n°2 : Neuf programmes informatiques T1, T2, . . . , T9 sont à exécuter sur deux pro-
cesseurs identiques M1, M2. Les durées de traitement sont :

programme T1 T2 T3 T4 T5 T6 T7 T8 T9
durée 3 2 2 5 3 4 1 3 4

Il existe des contraintes de précédence entre les programmes : Ti −→ Tj indique que le pro-
gramme Ti s’exécute avant le programme Tj :

T1 ❍❍ ✯
✟ T6 ❍❍
❍❍ ✟✟ ❍❍
✟✟
❍❍ ❍❍
✟
❥
✯
✟ T4 ✟
❍ ❥
✯
✟ T8
✟ ❍❍ ✟✟
✟✟ ❍❍ ✟✟
T2 ✟ ❥
❍ T7 ✟

T3 ✲ T5 ✲ T9

Avec les mêmes hypohèses que l’exemple n° 1, on veut minimiser la durée totale de traitement.

6
Le diagramme de Gantt suivant représente une solution optimale.

M1 T1 T4 T6 T8

M2 T2 T3 T5 T9 T7
✲

0 5 10 15 temps

7
Exemple n°3 : Un menuisier possède un cahier de charges au début d’une période de produc-
tion : 4 commandes {T1, T2, T3, T4} qui correspondent respectivement à 1 table, 5 chaises, 1
armoire et 1 fauteuil.

Le travail doit se faire sur une seule tâche à la fois. Les clients imposent une date au plus tard
avec des pénalités en cas de retard.
Commande Ti prix date échue di durée de production pi pénalité wi/jour
(DA) (jours) (jours) DA/jour
T1 - 1 table 2000 4 2 200
T2 - 5 chaises 3000 6 5 100
T3 - 1 armoir 7000 10 7 400
T4 - 1 fauteuil 4000 5 4 200

Le menuisier cherche à maximiser le profit ou à minimiser les pénalités.

8
Une première solution consiste à ordonnancer les tâches dans l’ordre de leurs indices. On
obtient le diagramme de guantt suivant :

T1 T2 T3 T4
✲

0 5 10 15 20 temps
4
P
La date de fin de traitement est égale à 18 = pi .
i=1

Ti date de fin ci retard ti pénalité wi × ti

T1 2 0 0
T2 7 1 1×100 = 100
T3 14 4 4×400 = 1600
T4 18 13 13×200 = 2600
total = 4300

Nous avons ti = max{ci − di, 0}.

Le profit est égal à 16000 - 4300 = 11700 DA.

9
Pour déterminer un ordonnancement optimal, il suffit de trouver une permutation de tâches qui
4
P
maximise la quantité (somme des prix - les pénalités) = 16000 − wi × ti. Donc qui minimise
i=1
4
P
wi × ti. La séquence de tâches T1, T4, T3, T2 est optimale. Le diagramme de guantt est :
i=1

T1 T4 T3 T2
✲

0 5 10 15 20 temps
La date de fin de traitement est 18 (inchangée).
Ti ci ti w i × ti
T1 2 0 0
T2 18 12 1200
T3 13 3 1200
T4 6 1 200

Les pénalités sont de 2600 DA

Le profit maximal est donc égal à 16000 - 2600 = 13400 DA

10
Exemple n° 4 : Un site d’une entreprise logistique est constitué de deux entrepôts : l’un de
déchargement (entrepôt D) et l’autre de chargement (entrepôt C). Le matin, à 7h30, 7 ca-
mions se présentent, chacun contenant un nombre de caisses connu, indiqué dans le tableau ci-
dessous. Chacun de ces camions doit être intégralement vidé dans l’entrepôt D avant d’accéder
à l’entrepôt C, où il sera à nouveau chargé avec un nombre de caisses connu, indiqué également
dans le tableau ci-dessous.

Entreprise
D C
✻ ✻

✲
① ①

Pour des raisons liées aux effectifs en personnel et aux contraintes de manutention, un seul ca-
mion peut être traité à la fois par chaque entrepôt, et lorsqu’on commence à traiter un camion,
on ne peut interrompre cette opération.

11
On souhaite finir au plus tôt le traitement des 7 camions, sachant que le temps de chargement
et de déchargement est exactement proportionnel au nombre de caisses : 1 minute par caisse.
On néglige le temps pour se rendre d’un entrepôt à l’autre. A quelle heure peut-on avoir fini
au plus tôt ?

Camions : 1 2 3 4 5 6 7
Nombre de caisses à décharger : 3 1 10 2 7 6 2
Nombre de caisses à charger : 6 2 5 3 6 6 3

12
C’est un atelier à 2 machines et à cheminement unique .
L’ordre 2, 4, 7, 1, 6, 5, 3 est optimal.

&
)3& 1& D& E& 3& 5& 4& 0& &
)1& & 1& D& E& 3& 5& 4& & 0&
&&&&&&2&&&&&&&&&&&&&&&&&4&&&&&&&&&&&&&&&&&32&&&&&&&&&&&&&&&&34&&&&&&&&&&&&&&&12&&&&&&&&&&&&&&&&14&&&&&&&&&&&&&&&02&&&&&&&&&&&&&&&&04&

La durée totale est de 36mn. On finit à 08h06.

13
2 Définitions

L’ensemble des n tâches (tasks, jobs) est noté T = {T1, T2, . . . , Tn}.

L’ensemble des m machines (machines, processors) est noté M = {M1, M2, . . . , Mm}.

2.1 Caractérisation des machines

il existe deux grandes classes de machines :

- Les machines parallèles

- Les machines spécialisées

14
Les machines parallèles (parallel machines) : Ces machines exécutent les mêmes traitements
et sont donc capables de traiter n’importe quelle tâche. En fonction de la vitesse de traitement,
nous distinguons trois types de machines parallèles :

— Les machines identiques (identical machines) : Pour ces machines, les vitesses de trai-
tement des tâches sont toutes égales.

— Les machines uniformes (uniform machines) : Pour ces machines, les vitesses de trai-
tement des tâches sont différentes mais que la vitesse de chaque machine est constante
et ne dépend pas des tâches de T .

— Les machines générales (unrelated machines) : Pour ces machines, la vitesse de traite-
ment d’une machine dépend de la tâche qui est traitée.

15
Les machines spécialisées ou dédiées (dedicated machines) : Ces machines sont spécialisées
à l’exécution de certaines tâches. Dans le cas de machines spécialisées, nous distinguons trois
types de configuration des machines ou modes de traitement :

— Ateliers à cheminement unique ou ateliers en ligne (Flow shop) : les tâches de T doivent
être traitées par toutes les machines dans un même ordre. Le même ordre de traitement
pour toutes les tâches.

— Ateliers à cheminement libre (Open shop) : les tâches de T doivent être traitées par
toutes les machines mais aucun ordre de traitement n’est imposé pour les tâches.

— Ateliers à cheminements multiples (Job shop) : le sous-ensemble de machines devant

traiter une tâche et l’ordre du traitement sont arbitraires, mais doivent être spécifiés à
l’avance.

16
2.2 Description des tâches

Dans le cas de machines parallèles, chaque tâche peut être traitée par n’importe quelle ma-
chine.

Si les machines sont spécialisées, chaque tâche Ti ∈ T est divisée en un nombre fini d’opérations
Oi1, Oi2, . . . , Oiki . Chacune pouvant nécessiter une machine différente (ki étant le nombre
d’opérations de la tâche Ti) :

17
Chaque tâche Ti ∈ T peut être caractérisée par les données suivantes :

1. Un vecteur temps de traitement (processing time) pi = {pi1, . . . , pim} : pij est le temps
de traitement nécessaire à la machine Mj pour terminer le traitement de la tâche Ti.
(durée de traitement)
— Dans le cas de machines identiques, nous avons : pij = pi pour j = 1, . . . , m.
— Dans le cas de machines uniformes, nous avons : pij = pi/bj pour j = 1, . . . , m où
bj est le facteur vitesse de traitement de la machine Mj et pi un temps de traitement
standard (correspondant à bj = 1)).

2. Une date d’arrivée, de disponibilité ou de début au plus tôt (release date) ri : c’est la
date à laquelle la tâche Ti est prête à être traitée. Si pour toutes les tâches de T , les
dates d’arrivée sont toutes égales, on pose ri = 0 pour i = 1, . . . , n.

3. Une date échue ou de fin au plus tard (due date) di : si le traitement de la tâche Ti doit
être achevé avant la date di.

4. Une date limite ou absolue (deadline) d˜i : si le traitement de la tâche Ti doit obligatoi-
rement être achevé avant la date d˜i.

5. Un poids (weight) wi : qui exprime une priorité relative (une pénalité, un profit, etc.) de
la tâche Ti.

18
Donnons maintenant quelques définitions concernant les préemptions et les contraintes de
précédence entre les tâches.

Définition 1 Un mode de traitement est dit préemptif ou avec préemption (preemptive) si chaque
tâche (ou opération dans le cas de machines spécialisées) peut être arrêtée à tout instant pour
terminer son exécution plus tard sans aucun coût, peut être sur une autre machine (on parlera
aussi de tâches morcelables ou interruptibles). Si ce n’est pas la cas, on dira que le mode de
traitement est non préemptif ou sans préemption (nonpreemptive).

Définition 2 Dans l’ensemble T , nous pouvons établir des contraintes de précédence (prece-
dence constraints) entre les tâches :
Ti < Tj veut dire que le traitement de la tâche Ti doit être achevé avant que celui de Tj ne
commence. L’ensemble T des tâches est ainsi ordonné par la relation <. Si au moins deux
tâches de T sont comparables, on dit que les tâches de T sont dépendantes. Sinon les tâches
de T sont dites indépendantes.

Un ensemble de tâches ordonné par une relation de précédence est habituellement représenté
comme un graphe orienté dans lequel les sommets représentent les tâches et les arcs les
contraintes de précédence.

19
Considérons l’instance ci-dessous avec 10 tâches et 3 machines identiques où la préemption
n’est pas autorisée. Les temps de traitement, les dates de disponibilité et les dates échues sont
données dans la table ci-dessous. La figure représente les contraintes de précédence.

Ti T1 T2 T3 T4 T5 T6 T7 T8 T9 T10
pi 2 3 1 2 4 1 2 6 2 1
ri 0 0 0 0 3 3 3 4 5 0
di 3 4 3 2 7 5 6 10 8 11
★✥ ★✥ ★✥ ★✥

T1 T2 T3 T4
✧✦ ✧✦ ✧✦ ✧✦
❆ ✁◗◗ ❆ ✁
❆ ✁ ◗ ❆ ✁
❆ ✁ ◗ ❆ ✁
◗
❆ ✁ ◗ ❆ ✁
❆ ✁ ◗ ❆ ✁
◗
❆★✥ ❆★✥
❆ ✁ ◗ ❆ ✁
✁ ◗ ✁
❆❯ ✁☛ ◗ ❆❯ ✁☛
◗
T 5 T
◗◗s 6
✧✦ ✧✦
❅ ❅
❅ ❅
❅ ❅
❅ ❅
❅ ❅

❅ ★✥ ❅ ★✥
❅ ❅

❅ ❅
T7 ❘
❅ ✠ T8 ❘
❅
✧✦ ✧✦

★✥
❄ ★✥

T9 T10
✧✦ ✧✦

20
2.3 Ordonnancement

Un ordonnancement est l’allocation des machines de M aux tâches de T en un temps tel que
les conditions suivantes soient satisfaites :

— A chaque instant t ∈ [0, +∞[ (ordonnancement classique),

chaque machine est allouée à au plus une tâche (une machine est libre ou exécute exac-
tement une tâche) et
chaque tâche est traitée par au plus une machine (une tâche est non affectée ou exécutée
par exactement une machine).

— Chaque tâche Ti est traitée dans l’intervalle de temps [ri, +∞[. Une tâche est exécutée
quand elle est disponible.

— Pour chaque pair (Ti, Tj ) de tâches telles que Ti < Tj , le traitement de Tj ne commence
que quand celui de Ti est achevé.

— Dans le cas d’ordonnancement non préemptif, aucune tâche n’est préemptée. Sinon le
nombre de préemptions par tâche est fini.

21
Un ordonnancement pour l’instance précédente est donné à la figure ci-dessous.

Machines

M1 T1 T5

M2 T2 T6 T8 T10

M3 T3 T4 T7 T9
✲

0 1 2 3 4 5 6 7 8 9 10 11 temps

22
2.4 Critères d’optimalité

Les paramètres suivants peuvent être calculés pour chaque tâche Ti, i = 1, . . . , n ; traitée dans
un ordonnancement (admissible ou réalisable) donné :

— Une date d’achèvement (Completion time) ci : c’est la date de fin de traitement de la

tâche Ti.

— Une durée de flot ou de séjour (Flow time) fi : c’est la somme du temps d’attente et du
temps de traitement. C’est aussi la différence entre la date d’achèvement et la date d’ar-
rivée. fi = ci − ri.

— Une tardiveté, décalage temporel ou retard algébrique (lateness) li : c’est la différence

entre la date d’achèvement et la date échue. li = ci − di.

— Un retard (tardiness) ti : ti = max{li, 0}


1 si ci > di
— Un indicateur de retard ui : ui =
0 sinon

23
Les différents paramètres de l’instance précédente sont :

Ti T1 T2 T3 T4 T5 T6 T7 T8 T9 T10
ci 2 3 1 3 7 4 9 10 11 11
fi 2 3 1 3 4 1 6 6 6 11
li -1 -1 -2 1 0 -1 3 0 3 0
ti 0 0 0 1 0 0 3 0 3 0
ui 0 0 0 1 0 0 1 0 1 0

24
Pour évaluer des ordonnancements nous utilisons différents critères où on cherche à minimi-
ser :

1. La longueur de l’ordonnancement (schedule length ou makespan) : Cmax = max {ci}

1≤i≤n
n
1
P
2. Le temps de flot moyen (mean flow time) : F = n
fi
i=1
3. La grande tardiveté (maximum lateness) : Lmax = max {li}
1≤i≤n
n
P
4. Le nombre de tâches en retard (number of tardy jobs) : NT = ui
i=1

25
Pour l’ordonnancement admissible de la figure précédente, nous avons :

— Cmax = max{2, 3, 3, 2, 7, 4, 9, 10, 11, 11} = 11. Cet ordonnancement est optimal.

— F = (2 + 3 + 3 + 2 + 4 + 1 + 6 + 6 + 6 + 11)/10 = 43/10. Cet ordonnancement n’est

pas optimal.

— Lmax = max{−1, −1, −2, 1, 0, −1, 3, 0, 3, 0} = 3. Cet ordonnancement est optimal.

— NT = 0 + 0 + 0 + 1 + 0 + 0 + 1 + 0 + 1 + 0 = 3. Cet ordonnancement n’est pas optimal

(NT optimal = 2).

D’autres critères sont aussi utilisés :

26
 n
1
P
1. Le temps de fin de traitement moyen (mean completion time) : C = n ci
i=1
n
P
wi fi
i=1
2. Le temps de flot moyen pondéré (mean weighted flow time) : Fw = Pn
wi
i=1

3. Le temps de fin de traitement moyen pondéré (mean weighted completion time) :

n  n 
P P
Cw = wi ci / wi
i=1 i=1
4. Le grand temps de flot (maximum flow time) : Fmax = max {fi}
1≤i≤n

5. Le grand retard (maximum tardiness) : Tmax = max {ti}

1≤i≤n
n
1
P
6. La tardiveté moyenne (mean lateness) : L = n li
i=1
n
  n 
P P
7. La tardiveté moyenne pondérée (mean weighted lateness) : Lw = wili / wi
i=1 i=1
n
1
P
8. Le retard moyen (mean tardiness) : T = n ti
i=1
n
  n 
P P
9. Le retard moyen pondéré (mean weighted tardiness) : Tw = w i ti / wi
i=1 i=1
10. etc.

27
Remarque 1 Quelques relations entre les différents critères :

1. Les critères Cw , Fw et Lw sont équivalents et en particulier C, F et L.

2. En général, les critères Cmax, Fmax et Lmax ne sont pas équivalents.
3. Un ordonnancement optimal pour Lmax est aussi optimal pour Tmax.

Preuve : (Exercices)

28
3 Classification
Etant donné la diversité des problèmes de l’ordonnancement, un formalisme permettant de
distinguer les différents problèmes de l’ordonnancement entre eux et de les classifier est utilisé.
Ce formalisme comporte trois champs α|β|γ permettant de décrire les différentes entités d’un
problème d’ordonnancement.

3.1 Champ α : ressources

Ce champ α décrit les machines utilisées : type de machines, nombre de machines et type
d’atelier. Il est composé de deux sous-champs et désigné par α = α1α2.
— α1 ∈ {1, P, Q, R, O, F, J} décrit le type de machine.
— α1 = 1 : Une seule machine.
— α1 = P : machines parallèles identiques.
— α1 = Q : machines parallèles uniformes.
— α1 = R : machines parallèles générales.
— α1 = O : machines spécialisées (système open shop).
— α1 = F : machines spécialisées (système flow shop).
— α1 = J : machines spécialisées (système job shop).

— α2 ∈ {∅, k} dénote le nombre de machines pour α1 6= 1.

— α2 = ∅ : le nombre de machines est variable.
— α2 = k : le nombre de machines est égal à k (k est un entier positif non nul).
29
3.2 Champ β : contraintes
Ce champ β décrit les tâches et les contraintes liées à ces dernières. Il est composé de 5 sous-
champs et désigné par β = β1, β2, β3, β4, β5.
— β1 ∈ {∅, pmtn} : indique la possibilité de préemption des tâches.
— β1 = ∅ : la préemption des tâches n’est pas autorisée.
— β1 = pmtn : la préemption des tâches est autorisée.

— β2 ∈ {∅, prec, tree, chains, ...} : indique le type de contraintes de précédence.

— β2 = ∅ : pas de contraintes de précédence (les tâches sont indépendantes).
— β2 = prec : les contraintes de précédence sont quelconques.
— β2 = tree : les contraintes de précédence sont sous forme d’une arborecence.
— β2 = chains : les contraintes de précédence sont données sous forme de chaı̂nes.
— d’autres types de graphes orientés peuvent aussi être utilisés.

— β3 ∈ {∅, ri} : décrit les dates de disponibilité.

— β3 = ∅ : toutes les dates de disponibilité sont nulles.
— β3 = ri : il existe des dates de disponibilité pour les tâches. Non toutes identiques

— β4 ∈ {∅, pi = p, . . .}.
— β4 = ∅ : les temps de traitement des tâches sont quelconques et non tous identiques.
— β4 = pi = p : les temps de traitement des tâches sont tous égaux à p (constants).

30
 — β5 ∈ {∅, di, d˜i}.
— β5 = ∅ : il n’y a pas des dates échues pour les tâches ou il existe des dates échues pour
les tâches dans le cas où le critère d’optimisation est en fonction de ces dernières.
— β5 = di : il existe des dates échues pour les tâches.
— β5 = d˜i : il existe des dates limites pour les tâches.

Remarque 2 La notation ∅ signifie qu’il ne faut mettre aucun symbole.

3.3 Champ γ : critère d’optimalité

Le troisième champ γ décrit le critère d’optimalité. On cherche à minimiser γ avec : γ ∈

{Cmax, C, Cw , Tmax , T , Tw , Lmax, U , Uw , −, . . .}.

”γ = −” signifie qu’on cherche une solution réalisable.

31
3.4 Exemples
Considérons les problèmes suivants :
P ||Cmax : Il indique qu’on veut traiter un ensemble de tâches indépendantes et
non interruptibles ayant des temps de traitement arbitraires et des dates
de disponibilité nulles sur des machines parallèles identiques en temps
minimal.

O3|pmtn, ri|F : Il indique qu’on veut traiter un ensemble de tâches indépendantes sur
trois machines spécialisées dans un système open shop. Les opérations
sont préemptibles et caractérisées par des temps de traitement et des
dates de disponibilité arbitraires. L’objectif est la minimisation du
temps de flot moyen.

1|ri, pi = 1|Lmax : Il indique qu’on veut traiter un ensemble de tâches indépendantes et

non interruptibles ayant des temps de traitement unitaires et des dates
de disponibilité et des dates échues arbitraires sur une seule machine.
L’objectif est la minimisation de la grande tardiveté.

Q2|tree|Cmax : Il indique qu’on veut traiter un ensemble de tâches dépendantes, où les
contraintes de précédences sont données sous forme d’un arborescence,
et non interruptibles ayant des temps de traitement arbitraires sur deux
machines parallèles uniformes. L’objectif est la minimisation de la date
de fin de traitement.

32
4 Réduction entre problèmes d’ordonnancement

Nous donnons ci-dessous quelques réductions (transformations polynomiales) entre problèmes

d’ordonnancement.

4.1 Machines

4.2 Contraintes sur les tâches

4.3 Critères

33
 R
✒❅
■
❅
❅
❅
❅
❅
Q Rk
✒❅
■ ✒
❅
❅
❅
J
❅ ✻
❅
P Qk
❅
■ ✒ F O
❅
❅
❅
❅
❅
Pk
✻ Machines spécialisées

Machines parallèles

35
 prec
✻

tree ri
✻ ✻
∅ pmtn
chain ∅
✻
Préemption
∅ Dates de disponibilité

Contraintes de précédence

38
 ∅
✻

di p ≤ pi ≤ p
✻ ✻

∅ pi = p
✻

Dates échues pi = 1

Temps de traitement

40
Cw ✲
Tw Uw Nous avons :
✻ ✻ ✻ — Σfi se réduit à Σwifi en posant wi = 1 pour i =
1, . . . , n.
✲
C T U Donc C, T et U se reduisent respectivement à Cw , Tw
✻ ✒
et Uw .
Lmax
✻ — Cmax, C et Cw se réduisent respectivement à Lmax, T
et Tw en posant di = 0 pour i = 1, . . . , n.
Cmax
Critères — Lmax se réduit à T et U (Exercice).

42