Replanification avec perturbation minimale
Thierry Moisan,Claude-Guy Quimper,
Jonathan Gaudreault,
et Sébastien Michaud
Université Laval, consortium de recherche FORAC

6 février 2015

Thierry Moisan, Claude-Guy Quimper, Jonathan Gaudreault, et Sébastien Michaud

Replanification avec perturbation minimale

1 / 37

Plan de la présentation1

Problématique2

Mesures de distance3

Programmation linéaire4Modèle linéaire à partie entière5Expériences et résultats

Thierry Moisan, Claude-Guy Quimper, Jonathan Gaudreault, et Sébastien Michaud

Replanification avec perturbation minimale

2 / 37

Problèmes avec la replanification

Nous sommes dans un contexte de production.
Supposons qu’un plan de production existe déjà.
Une nouvelle commande arrive et nous devons replanifier.
Le plan de production résultant peut être très différent de l’original.
Cela crée des problèmes sur le plancher lorsque du travail doit être fait
avant la production.
I Cela peut être encore pire après plusieurs replanifications.

IThierry Moisan, Claude-Guy Quimper, Jonathan Gaudreault, et Sébastien Michaud

Replanification avec perturbation minimale

3 / 37

Planification et ordonnancement des opérations de finition
du boisUn ensemble de commandes à remplir est connu.

La plupart des commandes ne peuvent pas être remplies à l’aide del’inventaire.
Notre but est de planifier et ordonnancer les opérations de production
pour satisfaire ces demandes.
Planifier: choisir les actions à utiliser durant la production.
Ordonnancement: quand et qui doit exécuté ces actions.
Thierry Moisan, Claude-Guy Quimper, Jonathan Gaudreault, et Sébastien Michaud

Replanification avec perturbation minimale

4 / 37

Planification et ordonnancement des opérations de finition
du boisLes processus sont des opérations créant plusieurs produits à partir d’unintrant.
Chaque produit peut être obtenu avec un processus alternatif.
Output A

Input X

Operation 1

Output B

Output C

Input Y

Operation 2

Output D

Output E

Il y a des contraintes de configurations qui restricte le séquencement desopérations.
Nous minimisons le retard des commandes (backorders).
Le plan de production est modélisé à l’aide d’un programmemathématique à valeur entières (MIP).
Thierry Moisan, Claude-Guy Quimper, Jonathan Gaudreault, et Sébastien Michaud

Replanification avec perturbation minimale

5 / 37

Replanification

Après une première planification nous obtenons un plan de production
optimal.
Nous ajoutons des contraintes pour fixer une borne supérieure sur lenombre backorders à chaque période.
Nous incluons ensuite les nouvelles commandes dans le jeu de donnéeset nous réoptimisons afin de minimiser les backorders.
Cette replanification cré un plan optimal qui respecte les commandes déjàexistantes.
Mais plusieurs plans optimaux existent. Comment pouvons-nous choisir leplus proche de l’original?

Thierry Moisan, Claude-Guy Quimper, Jonathan Gaudreault, et Sébastien Michaud

Replanification avec perturbation minimale

6 / 37

Objectif/Méthodologie

L’objectif est de modéliser la re-planification du plan de production.
Méthodologie
12

3

4

Minimiser les backorders.
Fixer les backorders optimaux sous forme de bornes supérieures dans lemodèle.
Change la fonction objective pour la distance entre le plan de productiond’origine et le nouveau plan.
Obtenir le nouveau plan de production qui minimise cette distance.

Thierry Moisan, Claude-Guy Quimper, Jonathan Gaudreault, et Sébastien Michaud

Replanification avec perturbation minimale

7 / 37

Mesures de distance

Period:

123

2x3
8’

10’

12’

456

2x6

2x4

8’ 12’

10’

Nous considérons le choix de famille de bois à chaque période commeétant un caractère d’un mot.
Nous utilisons trois métriques de distance pour mesurer la similarité dedeux plans de production.
Distance de Hamming (Hamming 1950)
Distance d’édition (Levenshtein 1966)
I Distance de Damerau-Levenshtein (Damerau 1964)
II

Thierry Moisan, Claude-Guy Quimper, Jonathan Gaudreault, et Sébastien Michaud

Replanification avec perturbation minimale

8 / 37

Plan de production et mot

Period:1232x34562x6

2x4
10’

8’

10’

12’

8’ 12’AAAB

Thierry Moisan, Claude-Guy Quimper, Jonathan Gaudreault, et Sébastien MichaudCC

Replanification avec perturbation minimale

9 / 37

Distance de Hamming

Compte le nombre de caractères différents à chaque position(substitutions).
Peut seulement être appliquée aux mots de même longueur.

T A B A B A C D

A B A B A T D C
Distance de Hamming de 8Thierry Moisan, Claude-Guy Quimper, Jonathan Gaudreault, et Sébastien Michaud

Replanification avec perturbation minimale

10 / 37Distance d’édition
Compte le nombre de caractères différents à chaque position(substitutions).
Considère aussi le nombre de suppression et d’insertion de caractères.
Peut être appliquée à des mots de longueurs différentes.

(suppression)

T A B A B A C D

A B A B A T D C(insertion)

Distance d’édition de 4Thierry Moisan, Claude-Guy Quimper, Jonathan Gaudreault, et Sébastien Michaud

Replanification avec perturbation minimale

11 / 37Distance de Damerau-Levenshtein
Compte le nombre de caractères différent à chaque position(substitutions).
Considère aussi le nombre de suppression et d’insertion de caractères.
La permutation de deux caractères adjacents a une distance de 1.

(suppression)

T A B A B A C D(permutation)A B A B A T D C(insertion)

Distance de Damerau-Levenshtein de 3

Thierry Moisan, Claude-Guy Quimper, Jonathan Gaudreault, et Sébastien Michaud

Replanification avec perturbation minimale

12 / 37

Plan

1

Problématique2

Mesures de distance3

Programmation linéaire4Modèle linéaire à partie entière5Expériences et résultats

Thierry Moisan, Claude-Guy Quimper, Jonathan Gaudreault, et Sébastien Michaud

Replanification avec perturbation minimale

13 / 37

Exemple de programmation linéaire

Supposons qu’un marchand vend deux types de produit: du jus depommes et du jus d’ananas.
Il souhaite trouver un inventaire maximisant la quantité détenue mais en
prenant en compte des contraintes.
Le jus de pommes vaut 4$ le litre.
Le jus d’ananas vaut 8$ le litre.
L’inventaire doit contenir une majorité de jus d’ananas.
Le marchand veut garder plus d’un litre de jus de pommes.
L’inventaire contient au maximum une valeur de 50$.
Quelle quantité de jus de chaque catégorie doit-il garder?

Thierry Moisan, Claude-Guy Quimper, Jonathan Gaudreault, et Sébastien Michaud

Replanification avec perturbation minimale

14 / 37

Exemple de programmation linéaire

x: quantité de jus d’ananas
y : quantité de jus depommes
Maximisex +ysujet àx ≥yy ≥18x + 4y ≤ 50x ≥0y ≥0Thierry Moisan, Claude-Guy Quimper, Jonathan Gaudreault, et Sébastien Michaud

Replanification avec perturbation minimale

15 / 37

Exemple de programmation linéaire
x: quantité de jus d’ananas
y : quantité de jus depommes
Maximisex +ysujet àx ≥yy ≥1
8x + 4y ≤ 50x ≥0y ≥050
Solution optimale: x = 12,50
y = 12Thierry Moisan, Claude-Guy Quimper, Jonathan Gaudreault, et Sébastien Michaud

Replanification avec perturbation minimale

16 / 37

Simplexe

Le simplexe permet de résoudre ce type de problème.
L’idée principale est de se déplacer sur les frontières de l’espace desolution.
L’espace de solution étant un polytope convexe, lorsqu’une solution
localement optimale est trouvée, il s’agit de la solution globalement
optimale.

Thierry Moisan, Claude-Guy Quimper, Jonathan Gaudreault, et Sébastien Michaud

Replanification avec perturbation minimale

17 / 37

Nombre entiers

x: quantité de jus d’ananas
y : quantité de jus depommes
Maximisex +ysujet àx ≥yy ≥18x + 4y ≤ 50x ≥0y ≥0Thierry Moisan, Claude-Guy Quimper, Jonathan Gaudreault, et Sébastien Michaud

Replanification avec perturbation minimale

18 / 37

Nombre entiers
x: quantité de jus d’ananas
y : quantité de jus depommes
Maximisex +ysujet àx ≥yy ≥18x + 4y ≤ 50x ∈Ny ∈N

Le problème devientNP-Complet.

Thierry Moisan, Claude-Guy Quimper, Jonathan Gaudreault, et Sébastien Michaud

Replanification avec perturbation minimale

19 / 37

Nombre entiers

Maximise

X +Ysujet àx ≥yy ≥18x + 4y ≤ 50x ∈Ny ∈N

Le problème devient
NP-Complet.

Thierry Moisan, Claude-Guy Quimper, Jonathan Gaudreault, et Sébastien Michaud

Replanification avec perturbation minimale

20 / 37

Programmation linéaire à partie entièreBranch & boundLe modèle est résolu à l’aide du simplexe en supposant que toutes lesvariables sont continues.
I Si la variables x est de type entier et la solution du simplex est x = 5.2 oncrée deux branche.
1
En ajoutant la contrainte x ≤ 5.
2
En ajoutant la contrainte x ≥ 6.
II

Des bornes sur les solutions possibles sont obtenus et permettent deréduire la taille de l’espace de recherche.

En cas d’échec (aucune solution ou solution non-optimale) on retourne enarrière (backtrack) et on continue la recherche.

Thierry Moisan, Claude-Guy Quimper, Jonathan Gaudreault, et Sébastien Michaud

Replanification avec perturbation minimale

21 / 37

Plan1

Problématique2

Mesures de distance3

Programmation linéaire4

Modèle linéaire à partie entière5Expériences et résultats

Thierry Moisan, Claude-Guy Quimper, Jonathan Gaudreault, et Sébastien Michaud

Replanification avec perturbation minimale

22 / 37

Modèle de la distance de Hamming

Cette distance est modélisée comme un somme.
Ce concept a déjà été étudié (Brown et coll. 1997).
Soit X un mot composé des caractères x1 , x2 , . . . , xn et Y un motcomposé des caractères y1 , y2 , . . . , yn .
nHamming (X , Y ) =∑ I (xi 6= yi ).

i =1Thierry Moisan, Claude-Guy Quimper, Jonathan Gaudreault, et Sébastien Michaud

Replanification avec perturbation minimale

23 / 37

Modèle de la distance d’édition
La distance est équivalente au chemin le plus court dans un graphe etpeut être résolu en temps polynomial.

C1AB

C

111

1011A

11101101110110111011110111B

1011Thierry Moisan, Claude-Guy Quimper, Jonathan Gaudreault, et Sébastien Michaud

1011
Replanification avec perturbation minimale

24 / 37

Les transitions verticales et horizontales représentent, respectivement, lessuppressions et les insertions.
Les transitions diagonales représentent l’égalité ou l’inégalité de chaquepaire d’éléments.

di −1,j −1

di −1,j0
1
1

di ,j −1

1

di ,j

ijsi j = 0si i = 0di ,j = di −1,j + 1,sinonmind+1,
i ,j −1di −1,j −1 + I (xi 6= yj )Thierry Moisan, Claude-Guy Quimper, Jonathan Gaudreault, et Sébastien Michaud

Replanification avec perturbation minimale

25 / 37

Exemple de la distance d’édition

C1A

B

C

11

1

10

11A

11

10

1101110

1

10

1

1
10

11

1
10

1

11B

1011

Thierry Moisan, Claude-Guy Quimper, Jonathan Gaudreault, et Sébastien Michaud

1011

Replanification avec perturbation minimale

26 / 37

Exemple de la distance d’édition

CA

B

C

111111A111011111011101111B

1111111Thierry Moisan, Claude-Guy Quimper, Jonathan Gaudreault, et Sébastien Michaud

11Replanification avec perturbation minimale

27 / 37

Exemple de la distance d’édition

CAB

C

111111A

1110
1

Thierry Moisan, Claude-Guy Quimper, Jonathan Gaudreault, et Sébastien Michaud

11111011101111B11111111Replanification avec perturbation minimale

28 / 37

Modèle de la distance de Damerau-Levenshtein
A1B11C1110111111111111111011111

100
1

1001R

10

10

1

101A

B

1

Thierry Moisan, Claude-Guy Quimper, Jonathan Gaudreault, et Sébastien Michaud

1

Replanification avec perturbation minimale

29 / 37

Modèle de la distance de Damerau-Levenshtein
La distance est modélisée comme une extension du chemin de ladistance d’édition.
La plus longue transition diagonale représente la permutation decaractères subséquents.

di −2,j −2

1

di −1,j −1

di ,j −101

di −1,j1

1

di ,j
i

j 



d+1,


i−1,j







d+1,i,j−1
min
di ,j =
di −1,j −1 + I (xi 6= yj ), 




d+1

i −2,j −2
 di −1,j + 1,

mind+1,i ,j −1
di −1,j −1 + I (xi 6= yj )Thierry Moisan, Claude-Guy Quimper, Jonathan Gaudreault, et Sébastien Michaudsi j = 0si i = 0si i , j > 1∧
ai = bj −1 ∧ai −1 = bj

sinon

Replanification avec perturbation minimale

30 / 37

Modèle de la distance de Damerau-Levenshtein
A

1

B

11B

C

11111

10
1

111A

11111

101R

1111

111

Thierry Moisan, Claude-Guy Quimper, Jonathan Gaudreault, et Sébastien Michaud

1111

1

Replanification avec perturbation minimale

31 / 37

Modèle de la distance de Damerau-Levenshtein
A1B

11BC

11111101111A

11111101R

1111111

Thierry Moisan, Claude-Guy Quimper, Jonathan Gaudreault, et Sébastien Michaud

11111

Replanification avec perturbation minimale

32 / 37

Plan1

Problématique2

Mesures de distance3

Programmation linéaire4Modèle linéaire à partie entière5Expériences et résultats

Thierry Moisan, Claude-Guy Quimper, Jonathan Gaudreault, et Sébastien Michaud

Replanification avec perturbation minimale

33 / 37

Plan d’expérimentation

Nous avons utilisé notre méthodologie pour replanifier des opérations del’entreprise forestière Maibec.
Nous optimisons les instances d’origines et nous fixons une borne
supérieure sur la quantité de retard à chaque période.
Nous simulons l’arrivée de groupes de 1 à 15 commandes en se basant
sur les données existantes.
Nous changeons la fonction objectif afin de minimiser la distance entre leplan d’origine et le nouveau plan que nous souhaitons généré.

Thierry Moisan, Claude-Guy Quimper, Jonathan Gaudreault, et Sébastien Michaud

Replanification avec perturbation minimale

34 / 37

Instances provenant d’une compagnie canadienne deproduit forestier

Nous avons travaillé avec les instances suivantes:
65,142 variables
50,238 contraintes
42 variables de décision entière de cardinalité 6Nous avons utilisé le solveur CPLEX 12.5

Thierry Moisan, Claude-Guy Quimper, Jonathan Gaudreault, et Sébastien Michaud

Replanification avec perturbation minimale

35 / 37Temps d’exécution

Moyenne géométrique des temps d’exécution de chaque expérimentation.

Instances faciles
Instances difficiles

Minimisation
desbackorders(secondes)

minimisationdela
distance deHamming(secondes)

Minimisationdeladistanced’édition(secondes)

1.4
564.5

0.7
7.9

4.7
135.8

Thierry Moisan, Claude-Guy Quimper, Jonathan Gaudreault, et Sébastien Michaud

Minimisationdeladistance deDamerauLevenshtein(secondes)
4.2
127.3

Replanification avec perturbation minimale

36 / 37

Plans de production comparés avec la distance deDamerau-Levenshtein
Backorder minimization
Hamming distance minimization
Edit distance minimization
Damerau-Levenshtein distance minimization

Damerau-Levenshtein distance

2520151050123456 7 8 9 10 11 12 13 14 15
Number of new orders

Thierry Moisan, Claude-Guy Quimper, Jonathan Gaudreault, et Sébastien Michaud

Replanification avec perturbation minimale

37 / 37

Conclusion
Nous avons proposé une nouvelle méthodologie de replanification qui
minimise la distance entre deux plans de production.
Nous avons utilisé trois métriques de distance afin de mesurer la similarité
entre deux plans de productions:Distance de Hamming
Distance d’édition
I Distance de Damerau-Levenshtein
II

Nous avons modélisé ces distances dans modèle MIP.
Nous avons expérimenté avec le problème de planification etd’ordonnancement des opérations de finition du bois d’oeuvre.
Satisfiant les nouvelles commandes
Stabilisant la production
I Peut être fait en une fraction du temps nécessaire pour obtenir le premierplan de production.
II

Thierry Moisan, Claude-Guy Quimper, Jonathan Gaudreault, et Sébastien MichaudReplanification avec perturbation minimale

38 / 37

Travaux futurs

Explorer des mesures de distance plus proche des besoins exacts del’industrie.
IPar exemple une distance avec une pénalité exponentielle.

Est-ce que cette approche peut être appliquée à un ensemble demachines parallèles?

Thierry Moisan, Claude-Guy Quimper, Jonathan Gaudreault, et Sébastien Michaud

Replanification avec perturbation minimale

39 / 37