Upload
lionel-bousquet
View
105
Download
0
Embed Size (px)
Citation preview
GDR MACS Nantes, 25-26 Mars 2004
Proposition d'extensions pour le RCPSP Proposition d'extensions pour le RCPSP
Corinne Boutevin, Michel Gourgand, Sylvie Norre
Université Blaise Pascal - Clermont-Ferrand II
LIMOS CNRS UMR 6158
2GDR MACS Nantes, 25-26 Mars 2004
Plan Plan
Le problème du RCPSP dans la littérature
Proposition d'extensions : applications industrielles et notations
Proposition de méthodes de résolution
Résultats
Conclusions et perspectives
3GDR MACS Nantes, 25-26 Mars 2004
Le problème du RCPSP dans la littérature Le problème du RCPSP dans la littérature
Ordonnancement d'un ensemble d'activités à réaliser à l'aide de ressources de
différents types disponibles en nombre limité dans le but d'optimiser un ou
plusieurs critères :
- makespan,
- retard total,
- taux d'utilisation des ressources,
- …
RCPSP (Resource-Constrained Project(s) Scheduling Problem) :
4GDR MACS Nantes, 25-26 Mars 2004
Le problème du RCPSP dans la littérature Le problème du RCPSP dans la littérature
Les activités : contraintes de précédence
dates de début au plus tôt (ES) et au plus tard (LS)
dates de fin au plus tôt (EF) et au plus tard (LF)
un à plusieurs modes opératoires un mode = une durée d'exécution et une quantité de ressources requise de chaque type
Les ressources : ressources renouvelables (renewable resources)
ressources non renouvelables (nonrenewable resources)
ressources dédiées (dedicated resources)
ressources à disponibilité variable (resources with varying over time limits)
…
5GDR MACS Nantes, 25-26 Mars 2004
Le problème du RCPSP dans la littérature Le problème du RCPSP dans la littérature
SMRCPSP : Single-Mode RCPSP
GRCPSP : Generalized RCPSP (SMRCPSP avec contraintes de précédence généralisées)
PRCPSP : Preemptive RCPSP (SMRCPSP avec préemption autorisée)
MMRCPSP : Multi-Mode RCPSP (plusieurs modes opératoires, préemption et contraintes de précédence généralisées)
Plusieurs modèles :
6GDR MACS Nantes, 25-26 Mars 2004
Notation pour le RCPSP : | |
besoin en ressources
caractéristiques des activités
critère
(Kan, 1976)
(Brucker et al., 1999) Cmax, Lmax
pj = 1, pj, …prec, temp, …
PSm, , ; , , nombre de types de ressources renouvelables
nombre de types de ressources non renouvelables
quantité de ressources
renouvelables de chaque type
quantité de ressources non renouvelables de
chaque type
quantité maximale requise de chaque type
de ressources renouvelables
quantité maximale requise de chaque
type de ressources non renouvelables
Le problème du RCPSP dans la littérature Le problème du RCPSP dans la littérature
7GDR MACS Nantes, 25-26 Mars 2004
Le problème du RCPSP dans la littérature Le problème du RCPSP dans la littérature
Extensions du modèle classique :
- (Dauzère-Pérès et al., 1998) : les ressources sont choisies parmi un ensemble de ressources candidates
- (Néron et Bellenguez, 2003) : notion de compétencesl'exécution d'une activité nécessite une ou plusieurs compétencesles compétences sont détenues par les ressources
8GDR MACS Nantes, 25-26 Mars 2004
Le problème du RCPSP dans la littérature Le problème du RCPSP dans la littérature
Les méthodes de résolution :
Méthodes exactes :
- formalisation mathématique (Kolisch & Sprecher, 1996)
- Branch-and-Bound (Talbot & Patterson, 1978) (Sprecher et al., 1994)
(Hartmann & Kolisch, 2000)
Méthodes approchées :
- heuristique (Sowinski et al., 1994) (Özdamar & Usuloy, 1995) (Norbis & Smith, 1988)
- métaheuristique (Özdamar, 1996) (Hartmann, 1997)
algorithme génétique
9GDR MACS Nantes, 25-26 Mars 2004
Proposition d'extensions – Le double découpage temporel Proposition d'extensions – Le double découpage temporel
Extension 1 : double découpage temporel
Dans le RCPSP classique : notion de période (un seul découpage temporel)
Proposition : gestion de deux découpages temporels
- les séquences de périodes
- les périodes
Exemple : séquence = jour, période = heure
Prise en compte d’une nouvelle contrainte :
une activité doit être entièrement réalisée à l'intérieur d'une séquence
10GDR MACS Nantes, 25-26 Mars 2004
Application industrielle : Planification d'essais automobiles
- un essai requiert un circuit, un pilote et un véhicule
- les essais sont soumis à des contraintes de précédence
- les essais sont soumis à des dates de fin de traitement au plus tôt à respecter, et des dates de fin au plus tard souhaitées
- but : ordonnancer les essais (déterminer le jour et les heures de traitement) tout en respectant les contraintes
- objectif : minimiser le makespan
Proposition d'extensions – Le double découpage temporel Proposition d'extensions – Le double découpage temporel
11GDR MACS Nantes, 25-26 Mars 2004
: inchangé
: trois sous-champs :
- 1 = pj
- 2 = prec
- 3 = ( vecteur donnant le nombre de périodes par séquence)
: inchangé
| pj, prec, | Cmax,PSm,
Proposition d'extensions – Le double découpage temporel Proposition d'extensions – Le double découpage temporel
Proposition d'une notation :
12GDR MACS Nantes, 25-26 Mars 2004
Extension 2 : variation de la quantité requise de ressources durant l'exécution des activités
Dans le RCPSP classique, une activité a un besoin constant en ressources
Proposition : variation de la demande en ressources au cours du traitement d'une activité
- l'activité est divisée en plusieurs sous-activités (ou étapes)
- attente possible entre deux étapes consécutives (durée de chaque étape connue, mais durée totale de traitement de l'activité inconnue)
- si augmentation de la demande : conservation des ressources (d'un type donné) entre deux étapes consécutives (et affectation de la quantité manquante)
- si diminution de la demande : libération du nombre nécessaire de ressources (d'un type donné) entre deux étapes consécutives
Proposition d'extensions – Proposition d'extensions – Variation de la quantité requise de ressources Variation de la quantité requise de ressources
13GDR MACS Nantes, 25-26 Mars 2004
Application industrielle : Ordonnancement du traitement de convois de pièces sur un chantier
- le chantier est découpé en surfaces
- un convoi requiert des ressources humaines (monteurs, opérateurs) et matérielles (surfaces, pinces et rails de différents types)
- le nombre de ressources nécessaires et les temps d'exécution dépendent du type du convoi et de sa disposition sur le chantier)
partie haute
partie basse
Proposition d'extensions – Proposition d'extensions – Variation de la quantité requise de ressources Variation de la quantité requise de ressources
14GDR MACS Nantes, 25-26 Mars 2004
- le traitement d'un convoi est divisé en trois étapes :
- but : ordonnancer les différents convois
- objectif : minimiser le makespan
3 2 1
Fabrication AttenteAttente Installation Désinstallation
4 6 7
affectation des ressources
début installation
fin installation : libération des
monteursdemande des opérateurs
fin fabrication : libération des
opérateursdemande des
monteurs
affectation des monteurs
début désinstallation
fin désinstallation : libération des
surfaces, monteurs, pinces
et rails
demande des surfaces,
monteurs, pinces et rails
Attente
affectation des opérateurs
début fabrication
5
Proposition d'extensions – Proposition d'extensions – Variation de la quantité requise de ressources Variation de la quantité requise de ressources
15GDR MACS Nantes, 25-26 Mars 2004
: trois sous-champs :
- 1 = m
- 2 =
- 3 = (e) ( matrice donnant le besoin maximal en ressources pour chaque étape)
: inchangé
: inchangé
| pj, prec | Cmax
ρ(e)σ,m,PS
Proposition d'extensions – Proposition d'extensions – Variation de la quantité requise de ressources Variation de la quantité requise de ressources
Proposition d'une notation :
16GDR MACS Nantes, 25-26 Mars 2004
Extension 3 : identification des ressources
Dans le RCPSP classique, les ressources sont regroupées par type
Proposition : identification des ressources (gestion des unités de ressources et non des types de ressources)
Prise en compte de nouvelles contraintes :
- incompatibilités entre activités et unités de ressources
- incompatibilités entre unités de ressources
- variation de la disponibilité des unités de ressources
Proposition d'extensions – Identification des ressources Proposition d'extensions – Identification des ressources
17GDR MACS Nantes, 25-26 Mars 2004
Application industrielle : Planification d'essais automobiles
- indisponibilité de certains pilotes (dues aux périodes de congés ou maladies)
- incompatibilités entre pilotes et véhicules
- incompatibilités entre pilotes et essais, entre véhicules et essais
Proposition d'extensions – Identification des ressources Proposition d'extensions – Identification des ressources
18GDR MACS Nantes, 25-26 Mars 2004
: quatre sous-champs :
- 1 = m
- 2 = (u, q) ( matrice donnant l'indisponibilité des unités de ressources selon les périodes)
- 3 =
- 4 = (1)(u1, u2) ((1) matrice donnant les incompatibilités entre unités de ressources)
: trois sous-champs : - 1 = pj
- 2 = prec
- 3 = (2)(j, u) ((2) matrice donnant les incompatibilités entre unités de ressources et activités)
: inchangé
| pj, prec, (2) (j, u) | Cmax )u,(uλρ,q),σ(u,m, 21
(1)PS
Proposition d'extensions – Identification des ressources Proposition d'extensions – Identification des ressources
Proposition d'une notation :
19GDR MACS Nantes, 25-26 Mars 2004
Proposition de méthodes de résolutionProposition de méthodes de résolution
pour chacune des extensions :
- modèle linéaire en nombres entiers
- heuristiques de priorité
pour l'extension sur la variation de la quantité requise de ressources : - métaheuristiques : descente stochastique, recuit simulé, kangourou, …
20GDR MACS Nantes, 25-26 Mars 2004
Proposition de méthodes de résolutionProposition de méthodes de résolution
Extension 1 : double découpage temporel
Idée générale de l'heuristique :
- les ressources sont testées par ordre lexicographique
- les séquences de périodes ainsi que les périodes sont parcourues par numéro
croissant
- les activités réalisables à la période q (celles dont tous les prédécesseurs sont
ordonnancés et ont terminé leur traitement avant q ou lors d'une séquence
antérieure) sont étudiées par date au plus tard croissante
- les activités possédant la même date au plus tard sont triées selon une règle de
priorité choisie
21GDR MACS Nantes, 25-26 Mars 2004
Proposition de méthodes de résolutionProposition de méthodes de résolution
- détermination de la priorité de chaque activité - pour chaque séquence de périodes t faire - pour chaque période q de la séquence t faire - les activités réalisables à la période q sont triées par date de fin au plus tard croissante puis
selon la priorité choisie (en cas d'égalité)- pour chaque activité réalisable j faire - si j peut être entièrement traitée durant la séquence t alors - pour chaque type de ressources k faire- si il est impossible d'affecter la quantité requise (indisponibilité) alors - l'activité j n'est pas ordonnançable - on passe à une autre activité- fin si - fin pour - j est ordonnancée durant la séquence t et débute son traitement à la période q (affectation
des ressources)- fin si- fin pour- fin pour- fin pour
Algorithme de principe de l'heuristique :
22GDR MACS Nantes, 25-26 Mars 2004
Proposition de méthodes de résolutionProposition de méthodes de résolution
par ordre lexicographique
Descendants' Weight (DW) (cf. P | prec | Cmax) :
PRIOR(j) =
Longest Path (LP) (cf. P | prec | Cmax)
PRIOR(j) =
jj'
j j'p
desdescendant
)(PRIOR
sinonpj'
successeurdepasan'jsip
j
jj'
j
)PRIOR(max
desuccesseur
Règles de priorité sur les activités :
23GDR MACS Nantes, 25-26 Mars 2004
Proposition de méthodes de résolutionProposition de méthodes de résolution
Extension 2 : variation de la quantité requise de ressources durant l'exécution des activités
- heuristique pour le problème d'ordonnancement des convois : privilégier les convois dont l'ensemble des ressources requises sont
disponibles
- heuristique pour le problème d'affectation des surfaces : heuristique 1 : privilégier les surfaces ayant le taux d'utilisation le plus faible heuristique 2 : privilégier les surfaces se situant sur la partie haute du chantier
- heuristique pour les problèmes d'ordonnancement et d'affectation : parcours des convois puis des surfaces selon l'ordre donné par les listes de priorité ci-dessus
24GDR MACS Nantes, 25-26 Mars 2004
Proposition de méthodes de résolutionProposition de méthodes de résolution
Système de voisinage pour l'affectation : - la disposition du convoi est choisie aléatoirement (si le convoi peut être placé sur le chantier selon deux dispositions)
- si la disposition du convoi requiert transversalement deux surfaces, alors seule la position longitudinale du convoi peut être modifiée
Système de voisinage pour l'ordonnancement : - voisinage 1: insertion d'un convoi choix aléatoirement d'un convoi dans l'ordonnancement et d'une nouvelle position pour insérer ce convoi - voisinage 2 : permutation de deux convois : choix aléatoirement de deux convois à permuter
2 dispositions possibles
25GDR MACS Nantes, 25-26 Mars 2004
Proposition de méthodes de résolutionProposition de méthodes de résolution
Extension 3 : identification des ressources
Idée générale :
- les ressources sont testées par ordre lexicographique - les unités de ressources sont testées par ordre lexicographique- les périodes sont parcourues par numéro croissant- les activités réalisables à la période t (celles dont tous les prédécesseurs sont
ordonnancés et ont terminé leur traitement avant t) sont étudiées par date au plus
tard croissante- les activités possédant la même date au plus tard sont triées selon une de règle de
priorité choisie
26GDR MACS Nantes, 25-26 Mars 2004
Proposition de méthodes de résolutionProposition de méthodes de résolution
- détermination de la priorité de chaque activité - pour chaque période t faire - les activités réalisables à la période t sont triées par date de fin au plus tard croissante puis selon
la priorité choisie- pour chaque activité réalisable j faire- pour chaque type de ressources k faire- pour chaque unité u de ressources de type k faire - si u n'est pas utilisée à t et u est disponible à t et u est compatible avec j et u est compatible
avec toutes les autres unités de ressources précédemment affectées à j alors affectation de l'unité u de type k à l'activité j
- fin si- si la quantité requise de ressources de type k est affectée à j alors on passe à un nouveau type - fin pour- fin pour - si il existe un type de ressources pour lequel il est impossible d'affecter la quantité requise alors
l'activité j n'est pas ordonnançable (libération des unités préalablement affectées à j) sinon l'activité j débute son traitement à la période t
- fin pour- fin pour
Algorithme de principe de l'heuristique :
27GDR MACS Nantes, 25-26 Mars 2004
RésultatsRésultats
Extensions 1 et 3 : double découpage temporel et identification des ressources
Nombre d'activités
Taux d'incom-patibilité
Taux d'indispo-
nibilitéSMRCPSP
SMRCPSP avec double
découpage temporel
SMRCPSP avec identification des ressources
SMRCPSP avec identification des
ressources et double découpage temporel
4 1.83 0.50 16 16 16 19 20 21 22 25
5 1.83 0.50 18 18 18 18 18 18 20 24
10 2.62 0.37 19 19 20 20 22 22 24 27
12 2.87 0.37 19 20 20 20 19 19 20 20
17 5.91 0.73 29 29 33 35 30 30 33 33
18 6.55 0.73 31 31 32 33 31 33 34 34
26 8.09 1.09 48 51 53 56 49 49 53 56
30 10.18 1.09 48 58 53 60 53 54 58 60
makespan optimal makespan obtenu avec une heuristique
28GDR MACS Nantes, 25-26 Mars 2004
RésultatsRésultatsExtension 2 : variation de la quantité requise de ressources durant l'exécution des activités 90 convois
Cas Méthodes Valeur du makespan
Moyenne Ecart-type Amélioration
Evaluation du makespan <E> 16780
Affectation des ressources fixée et détermination de
l'ordonnancement des convois<E>+<H(O)> <DS2(O)> 16090.00 0.00 4.1 %
Ordonnancement des convois fixé et détermination de
l'affectation des ressources
<E>+<H1(A)> 10900 35.0 %
<E>+<H2(A)> 10960 34.7 %
Détermination de l'ordonnancement des convois
et de l'affectation des ressources
<E>+<H(O)> <DS(A)> 10916.00 125.88 34.9 %
<E>+<H(O)> <DS1(O)+ DS(A)> 10303.50 52.84 38.6 %
<E>+<H(O)> <DS2(O)+DS(A)> 10328.50 68.62 38.4 %
<E>+<H(O)> <RS1(O)+RS(A)> 10275.50 59.95 38.8 %
<E>+<H(O)> <RS2(O)+RS(A)> 10278.75 57.35 38.8 %
29GDR MACS Nantes, 25-26 Mars 2004
RésultatsRésultats
Cas Méthodes Valeur du makespan
Moyenne Ecart-type Amélioration
Evaluation du makespan <E> 32990
Affectation des ressources fixée et détermination de
l'ordonnancement des convois<E>+<H(O)> <DS2(O)> 32090.50 112.59 2.7 %
Ordonnancement des convois fixé et détermination de
l'affectation des ressources
<E>+<H1(A)> 20980 36.4 %
<E>+<H2(A)> 2164034.4 %
Détermination de l'ordonnancement des convois
et de l'affectation des ressources
<E>+<H(O)> <DS(A)> 22806.00 328.83 30.9 %
<E>+<H(O)> <DS1(O)+ DS(A)> 20941.00 182.47 36.5 %
<E>+<H(O)> <DS2(O)+DS(A)> 20930.00 237.97 36.6 %
<E>+<H(O)> <RS1(O)+RS(A)> 21056.50 330.00 36.2 %
<E>+<H(O)> <RS2(O)+RS(A)> 20926.50 308.91 36.6 %
180 convois
30GDR MACS Nantes, 25-26 Mars 2004
Conclusions et perspectivesConclusions et perspectives
Conclusions :
- proposition de nouvelles extensions pour le modèle classique du RCPSP
- meilleure modélisation de cas réels
- proposition de différents types de méthodes (modèles mathématiques, heuristiques, métaheuristiques)
Perspectives :
- extension 1 : approche Timetabling (problème d'emploi du temps)
- proposition de méthodes de résolution intégrant les trois extensions
- proposition de nouvelles règles de priorité pour les heuristiques
- étude détaillée des systèmes de voisinage