I.3.2 Typologie des problèmes d'ordonnancement
Le premier point de choix, en vue d'établir une
classification des problèmes d'ordonnancement peut se poser au niveau de
la nature des tâches, on distingue ainsi les problèmes
préemptifs [Slow 82], qui se séparent en deux classes selon que
l'interruption des tâches s'effectue avec ou sans mémorisation du
travail partiellement accompli, et les problèmes
non-préemptifs.
Dans le cadre des problèmes non
préemptifs, B.Roy[Roy , 71] propose une classification selon la nature
des inconnues. Une tâche est décrite par trois sortes de
caractéristiques (T, D, W) qui représentent respectivement la
date de début des taches, leur durée, les ressources
utilisées
19
(nature et quantité). Il dégage ainsi
cinq type de problèmes en fonction de la famille de
caractéristiques inconnues : les problèmes de type T, W, (T, D),
(T, W) et (T, D, W), les problèmes de types W où les
caractéristiques concernant les ressources sont inconnues, constituant
les problèmes d'affectation, dans le cas où la durée ne
dépend que de la ressource utilisée, les problèmes de
types (T, D, W) peuvent être rangés dans le type
(T,W).
Les problèmes de type T ou seules les dates de
début des tâches sont inconnues constituent ce que l'on peut
appeler les problèmes d'ordonnancements purs.
Ce type de classification, bien qu'étant assez
général, ne fait pas apparaître tout les problèmes
qu'inspire la liste des contraintes évoquées au paragraphe
précèdent.
Ainsi lors de lotissements, les temps de
préparation peuvent être vu comme des tâches dont leur
durée dépend à la fois des tâches antérieures
et des tâches suivantes, il s'agit là d'une catégorie de
problèmes ne rentrant pas dans le cadre de la classification (T, D,
W).
Au sein des problèmes de type T, on peut
établir une classification plus fine. On distingue :
Le cas où l'on ne prend pas en compte les
ressources, appelé problème central de l'ordonnancement
;
Le cas général où les ressources
sont prises en compte ;
Dans le cas général, deux
classifications parallèles sont alors possibles suivant le type de
ressources utilisées dans le problème. On a d'une part
:
y' les problèmes à ressources renouvelables
; y' les problèmes à ressource consommable ; Et
d'autre part :
y' Les problèmes à ressource disjonctives
ou problème disjonctifs ; y' Les problèmes
à ressources cumulatives ou problème cumulatifs ;
Les problèmes à ressources renouvelables
et disjonctifs sont souvent appelés problème d'atelier. Dans ce
cas particulier on parle indifféremment de tâches ou
d'opérations, de ressources ou de
20
machines. Une opération nécessite une
machine pour sa réalisation. Les opérations relatives à la
fabrication d'un produit doivent généralement être
réalisées en séquence et constituent un travail ou «
«job ».
| 
