4.3 Pro blèmes d’ordon nan ce ment en ges tion de pro jets
115
© Dunod – Toute reproduction non autorisée est un délit.
« opé ra tions »), elles- mêmes sou mises à un ensemble de contraintes. La durée de
chaque tâche est suppossér connue : d i pour la tâche i.
Les contraintes aux quelles sont sou mises les diverses tâches qui concourent à la
réa li sa tion de l’objec tif sont de divers types. On dis tingue :
– les contraintes du type poten tiel, qui sont des contraintes de loca li sa tion tem -
po relle (la tâche i ne peut pas com men cer avant telle date ou, au contraire, doit
être ache vée pour telle date), ou les contraintes de suc ces sion (la tâche j ne peut
pas com men cer avant que la tâche i ne soit ter mi née, ou sim ple ment, par ve nue à
un cer tain degré d’achè ve ment) ; Si i com mence à la date t i (et j à t j ) et dure d i , il
vient : t i 1 d i < t j soit d i < t j 2 t i . Dans cette inéga lité, les inconnues t i et t j n’inter
viennent que par leur dif fé rence ; par ana lo gie avec les dif fé rences de poten tiel en
élec tri cité, les inconnues t i , t j sont nommées “poten tiels”.
– les contraintes du type dis jonc tif, impo sant la dis jonc tion de deux inter valles
de temps, rela tifs, par exemple, à l’exé cu tion de deux tâches i et j, qui ne peuvent être réa li sées simul ta né ment (par exemple si elles uti lisent une même
res source). Si les tâches i et j sont en dis jonc tion (exclu sion mutuelle), on a :
3t i , t i 1 d i 4 d 3t j , t j 1 d j 4 5 [
– les contraintes du type cumu la tif, concer nant l’évo lu tion dans le temps du volume
total des moyens humains et maté riels consa crés à l’exé cu tion des tâches. Il est
plus déli cat de tenir compte de telles contraintes : on se contente, le plus sou vent,
de solu tions appro chées, obte nues par des heu ris tiques.
Quand le pro ces sus de réa li sa tion d’un objec tif est décom po sé en tâches,
1
ces tâches
étant sou mises à des contraintes diverses, il importe de déter mi ner un calen drier d’exé -
cu tion des tâches, com pa tible avec les contraintes. Trou ver un tel calen drier, c’est obte -
nir une solu tion du pro blème d’ordon nan ce ment. Tou te fois, parmi les diverses solu -
tions, il en est de meilleures et de moins bonnes rela ti ve ment à un cri tère donné.
Ainsi, il exis tera pro ba ble ment une solu tion moins coû teuse, une autre plus rapide,
une troi sième plus équi li brée que les autres. Au sens de la recherche opé ra tion nelle,
résoudre un problème d’ordonnancement c’est choi sir, parmi toutes les solu tions, une
solu tion opti male (ou, du moins, proche de l’optimum si une heuristique doit être
employée), par rap port à un cri
tère fixé à l’avance. Dans la plu part des cas, ce cri tère
consiste à réa li ser l’objec tif le plus tôt pos sible. C’est celui adopté ci-dessous.
Jus qu’à 1958, les pra ti ciens de l’ordon nan ce ment ne dis po saient guère que du
plan ning à barres, dit encore gra phique de Gantt, pour abor der ce genre de pro -
blèmes (de manière appro chée, non sys té ma tique). De plus, les chercheurs opé ra -
tion nels connais saient les algo rithmes de Johnson, appli cables dans quelques cas
bien par ti cu liers (tâches à exé cu ter sur deux ou trois machines suc ces si ve ment, sou -
mises donc seule ment à des contraintes dis jonc tives).
C’est donc avec un grand inté rêt qu’on a vu appa raître à cette époque simul -
ta né ment et indé pen dam ment, deux méthodes nou velles, fon dées sur la théo rie
1. Pour le moment, nous n’exa mi nons pas com ment cette décom po si tion est réa li sée ; nous pou
vons, par exemple, nous bor ner à consi dé rer toutes les tâches « élé men taires ».
115
© Dunod – Toute reproduction non autorisée est un délit.
« opé ra tions »), elles- mêmes sou mises à un ensemble de contraintes. La durée de
chaque tâche est suppossér connue : d i pour la tâche i.
Les contraintes aux quelles sont sou mises les diverses tâches qui concourent à la
réa li sa tion de l’objec tif sont de divers types. On dis tingue :
– les contraintes du type poten tiel, qui sont des contraintes de loca li sa tion tem -
po relle (la tâche i ne peut pas com men cer avant telle date ou, au contraire, doit
être ache vée pour telle date), ou les contraintes de suc ces sion (la tâche j ne peut
pas com men cer avant que la tâche i ne soit ter mi née, ou sim ple ment, par ve nue à
un cer tain degré d’achè ve ment) ; Si i com mence à la date t i (et j à t j ) et dure d i , il
vient : t i 1 d i < t j soit d i < t j 2 t i . Dans cette inéga lité, les inconnues t i et t j n’inter
viennent que par leur dif fé rence ; par ana lo gie avec les dif fé rences de poten tiel en
élec tri cité, les inconnues t i , t j sont nommées “poten tiels”.
– les contraintes du type dis jonc tif, impo sant la dis jonc tion de deux inter valles
de temps, rela tifs, par exemple, à l’exé cu tion de deux tâches i et j, qui ne peuvent être réa li sées simul ta né ment (par exemple si elles uti lisent une même
res source). Si les tâches i et j sont en dis jonc tion (exclu sion mutuelle), on a :
3t i , t i 1 d i 4 d 3t j , t j 1 d j 4 5 [
– les contraintes du type cumu la tif, concer nant l’évo lu tion dans le temps du volume
total des moyens humains et maté riels consa crés à l’exé cu tion des tâches. Il est
plus déli cat de tenir compte de telles contraintes : on se contente, le plus sou vent,
de solu tions appro chées, obte nues par des heu ris tiques.
Quand le pro ces sus de réa li sa tion d’un objec tif est décom po sé en tâches,
1
ces tâches
étant sou mises à des contraintes diverses, il importe de déter mi ner un calen drier d’exé -
cu tion des tâches, com pa tible avec les contraintes. Trou ver un tel calen drier, c’est obte -
nir une solu tion du pro blème d’ordon nan ce ment. Tou te fois, parmi les diverses solu -
tions, il en est de meilleures et de moins bonnes rela ti ve ment à un cri tère donné.
Ainsi, il exis tera pro ba ble ment une solu tion moins coû teuse, une autre plus rapide,
une troi sième plus équi li brée que les autres. Au sens de la recherche opé ra tion nelle,
résoudre un problème d’ordonnancement c’est choi sir, parmi toutes les solu tions, une
solu tion opti male (ou, du moins, proche de l’optimum si une heuristique doit être
employée), par rap port à un cri
tère fixé à l’avance. Dans la plu part des cas, ce cri tère
consiste à réa li ser l’objec tif le plus tôt pos sible. C’est celui adopté ci-dessous.
Jus qu’à 1958, les pra ti ciens de l’ordon nan ce ment ne dis po saient guère que du
plan ning à barres, dit encore gra phique de Gantt, pour abor der ce genre de pro -
blèmes (de manière appro chée, non sys té ma tique). De plus, les chercheurs opé ra -
tion nels connais saient les algo rithmes de Johnson, appli cables dans quelques cas
bien par ti cu liers (tâches à exé cu ter sur deux ou trois machines suc ces si ve ment, sou -
mises donc seule ment à des contraintes dis jonc tives).
C’est donc avec un grand inté rêt qu’on a vu appa raître à cette époque simul -
ta né ment et indé pen dam ment, deux méthodes nou velles, fon dées sur la théo rie
1. Pour le moment, nous n’exa mi nons pas com ment cette décom po si tion est réa li sée ; nous pou
vons, par exemple, nous bor ner à consi dé rer toutes les tâches « élé men taires ».