Chapitre 1
Problèmes d'ordonnancement
Problèmes d'ordonnancement 4
Introduction
Ce chapitre se propose de présenter les constituants et
la classification des problèmes d'ordonnancement ainsi qu'une
codification très répandue dans la littérature. Quelques
notions de complexitésont exposées afin de mieux comprendre la
difficultéde la résolution de certains problèmes. Nous
présenterons le problème considérédans ce
présent mémoire ainsi que ces particularité. La fin de se
chapitre se focalise sur un état de l'art pour les problèmes de
type Flow Shop et les méthodes de résolution utilisées
dans la littérature.
1.1 Notions préliminaires 1.1.1
Définitions
En logistique de production comme en gestion de projets, il
est difficile de se passer de l'ordonnancement vue son rôle capital,
intervenant dans des niveaux de décision à la fois tactiques et
opérationnels. L'ordonnancement vise à contrôler, à
court ou moyen terme, l'activitéd'un ensemble de ressources disponibles
en quantitélimitée, en gérant les conflits d'utilisation
que pose la réalisation d'un ensemble d'activités sur un horizon
de temps généralement imposé.[47]
Plusieurs définitions d'un problème
d'ordonnancement sont données dans la littérature, nous retenons
ici celle proposée par P. Esquirol [19] :
« Le problème d'ordonnancement consiste à
organiser dans le temps la réalisation de tâches, compte tenu de
contraintes temporelles (délais, contraintes d'enchaînement, ...)
et de contraintes portant sur l'utilisation et la disponi-bilitéde
ressources requises.»
Un problème d'ordonnancement peut être
considérécomme un sous-problème de planification dans
lequel il s'agit de décider de l'exécution opérationnelle
des tâches (jobs) planifiées, et ainsi d'établir leur
planning d'exécution et leur allouer des ressources visant à
satisfaire un ou plusieurs objectifs sous une ou plusieurs contraintes. En se
basant sur les concepts de tâche, ressource, contrainte et objectif,
l'ordonnancement peut également être défini comme :
« Ordonnancer un ensemble de tâches, c'est
programmer leur exécution en leur allouant les ressources requises et en
fixant leur date de début.»[9]
Problèmes d'ordonnancement 5
FIGURE 1.1 - Problèmes d'ordonnancement d'atelier
d'après J.C Billaut [4]
Un job i, appartenant à un ensemble J
de jobs à ordonnancer, est une
entitéélémentaire de travail représentée
dans le temps par une date d'entrée dans l'atelier et une date de sortie
de l'atelier, caractérisée par une gamme de production et un
ensemble de ressources spécifiques à sa réalisation.
La réalisation d'un job nécessite l'exploitation
d'un ensemble de ressource de disponibilitélimitée dont une
gestion optimale de leurs utilisations représente le but de la
résolution de certains problèmes d'ordonnancement.
Notons que dans le cas de l'ordonnancement d'atelier, le terme
machine est généralement utiliséà la place
de ressource.[47]
1.1.2 Classification
La classification des problèmes d'ordonnancement se
fait généralement selon la nature des variables mises en jeu, la
nature des contraintes, ou encore le type d'organisation ainsi que les gammes
de production.
Nous retenons une classification proposée par J.C Billaut
[4], qui a étécitée à plusieurs reprises
dans la littérature.
Problèmes d'ordonnancement 6
On peut distinguer plusieurs types de problèmes
d'ordonnancement d'atelier dont:
- le problème à une machine
oùchaque job est assimiléà une
opération unique, exécutée par une seule et même
machine.
- le problème Job Shop oùchaque job
a sa propre gamme opératoire.
- le problème Flow Shop oùtous les
jobs ont la même gamme de production.
Un Flow Shop Hybrid FSH se compose d'une série
d'étages de production, dont chacun comprend des machines
parallèles. Certains étages peuvent avoir une seule machine, mais
au moins un étage doit avoir plusieurs machines.
Le passage des jobs dans l'atelier est unidirectionnel, et chaque
job est exécutésur une seule machine par étage [17]. Les
machines à chaque étage peuvent
être identiques, uniformes ou non reliées.
En revanche, s'il n'y a qu'une seule machine à chaque
étage, alors on se ramène à un problème
traditionnel de flow shop sériel .
1.1.3 Codification
Plusieurs codifications ont étéproposées
dans la littératures, elles servent à décrire l'atelier et
ses caractéristiques (nombres de machines, nombre d'étage, type
de machine, etc . . .), les contraintes et les
spécificités des jobs et leurs natures d'exécution
(préemption, ressources auxiliaires, contraintes de
précédence, date de disponibilité, etc . . .), et
aussi les critères d'optimisation considérés (minimisation
des coûts, du temps, du retard, etc . . .).
Nous utiliserons la codification à trois champs
proposée par R. Graham [31] et reprise ensuite par Blazewicz [5] :
á â ã.
Le champ á correspond à la description
physique de l'atelier (machine environment) , ce champ est
généralement composéde deux éléments
décrivant le type de l'atelier et le nombre des machines
utilisées.
Par exemple, pour á = Pm
: atelier à m machines parallèles
identiques, et pour á = F2 : Flow shop à deux
machines .
Le deuxième champ â décrit les
contraintes et les caractéristiques des jobs (Job
characteristics). Il peut être vide, comme il peut contenir
plusieurs champs.
Par exemple, pour â = ri
: chaque job i a sa propre date de
disponibilitéri, et pour â =
qi : c'est le délais de livraison, indique que
chaque job i a une durée donnée à passer avant de
quitter l'atelier.
Problèmes d'ordonnancement 7
Le troisième champ renseigne sur les critères
d'optimisation choisis, ces
critères se basent généralement sur les
indicateurs suivants :
- Ci : date de sortie du job i de l'atelier
- Li et Ti = max(Li, 0) : le
retard du job i
- Ui : indiquant si le job i est en retard ou
non
Ces critères varient selon l'objectif de l'optimisation
à savoir la minimisation du coût de production, de stockage, du
respect des délais de livraisons ou le taux du temps d'immobilisation
des ressources.
Notons ici que le critère le plus utiliséest
celui de la minimisation de la durée totale d'achèvement
(makespan).
| 
