PROBLME DE
BIN-PACKING
Bencheikh.Ghita
Universit Sidi Mohamed Ben Abdellah
Facult des Sciences et Techniques-Fs
Encadr par : Pr Ahmed EL HILALI ALAOUI
Plan
Introduction de loptimisation combinatoire
Prsentation du problme
Le Bin Packing une dimension
Le bin Packing deux dimensions
Le bin Packing trois dimensions
Bin Packing une dimension
Modle mathmatique
Mthodes de rsolution
Bin Packing deux dimensions
Formulation mathmatique
Mthodes de rsolution
Application
07/05/2014 2 Bencheikh.Ghita
Optimisation combinatoire
Branche de la recherche oprationnelle
Traite des problmes rels
Consiste trouver la meilleur solution dans un ensemble fini
Champ dapplication
Lconomie
La finance
Le marketing
Planification dentreprise
Systmes de sant
Environnement
07/05/2014 Bencheikh.Ghita 3
Prsentation du problme
Problme doptimisation combinatoire
Ranger un ensemble dobjets dans des boites
Types de Bin Packing
o Bin Packing une dimension
o Bin Packing deux dimensions
o Bin Packing trois dimensions
Caractristiques du problmes
o Le nombre de dimensions
o Le type de tche
o Caractristique de objets
o Caractristiques des bins
07/05/2014 Bencheikh.Ghita 4
Bin Packing une dimensions 1BP
Objets sont caractriss par une seule variable
On distingue deux types de rangement :
Plusieurs bins
Un seul bin
07/05/2014 Bencheikh.Ghita 5
Plusieurs bins
07/05/2014 Bencheikh.Ghita 6
Minimiser le nombre de bins
objets
bins
Exemple dapplication
07/05/2014 Bencheikh.Ghita 7
Avant de formater votre PC, vous souhaitez faire des sauvegardes des fichiers importants sur des CD.
comment rpartir ces fichiers sur les supports de faon minimiser le nombre de CD utilises?
Bin Packing une dimension
Autres dapplication
Dcoupe de cbles
Dcoupe de bois
Chargement des camions, avec une seule contrainte (Poids, volume, )
Prparation de valise
07/05/2014 Bencheikh.Ghita 8
Modle mathmatique
La modlisation se fait par des tapes:
Le choix des variables.
Dterminer lobjectif.
tablir les contraintes.
Rsoudre le problme.
07/05/2014 Bencheikh.Ghita 9
Donnes :
o n : le nombre dobjets ranger
o : le poids de lobjet j
o : la capacit maximal du bin i
07/05/2014 Bencheikh.Ghita 10
1. Choix des variables
07/05/2014 Bencheikh.Ghita 11
2. Dterminer lobjectif.
Minimiser le nombre de bin utiliss
07/05/2014 Bencheikh.Ghita 12
3. tablir les contraintes.
1
re
contrainte :
on ne doit pas dpasser la capacit maximal du bin
2
me
contrainte :
chaque objets doit tre rang dans un seul bin
07/05/2014 Bencheikh.Ghita 13
Rsoudre le problme.
Next Fit (N.F)
First Fit (F.F)
Best Fit (B.F)
07/05/2014 Bencheikh.Ghita 14
heuristiques plus connues :
Next Fit (N.F)
07/05/2014 Bencheikh.Ghita 15
Next Fit (N.F)
07/05/2014 Bencheikh.Ghita 16
Next Fit (N.F)
07/05/2014 Bencheikh.Ghita 17
Next Fit (N.F)
07/05/2014 Bencheikh.Ghita 18
Next Fit (N.F)
07/05/2014 Bencheikh.Ghita 19
Next Fit (N.F)
07/05/2014 Bencheikh.Ghita 20
Next Fit (N.F)
07/05/2014 Bencheikh.Ghita 21
Next Fit (N.F)
07/05/2014 Bencheikh.Ghita 22
Next Fit (N.F)
07/05/2014 Bencheikh.Ghita 23
Next Fit (N.F)
07/05/2014 Bencheikh.Ghita 24
5 bins
First Fit (F.F)
07/05/2014 Bencheikh.Ghita 25
First Fit (F.F)
07/05/2014 Bencheikh.Ghita 26
First Fit (F.F)
07/05/2014 Bencheikh.Ghita 27
First Fit (F.F)
07/05/2014 Bencheikh.Ghita 28
First Fit (F.F)
07/05/2014 Bencheikh.Ghita 29
First Fit (F.F)
07/05/2014 Bencheikh.Ghita 30
First Fit (F.F)
07/05/2014 Bencheikh.Ghita 31
First Fit (F.F)
07/05/2014 Bencheikh.Ghita 32
First Fit (F.F)
07/05/2014 Bencheikh.Ghita 33
First Fit (F.F)
07/05/2014 Bencheikh.Ghita 34
4 bins
Best Fit (B.F)
07/05/2014 Bencheikh.Ghita 35
First Fit (F.F)
07/05/2014 Bencheikh.Ghita 36
First Fit (F.F)
07/05/2014 Bencheikh.Ghita 37
First Fit (F.F)
07/05/2014 Bencheikh.Ghita 38
First Fit (F.F)
07/05/2014 Bencheikh.Ghita 39
First Fit (F.F)
07/05/2014 Bencheikh.Ghita 40
First Fit (F.F)
07/05/2014 Bencheikh.Ghita 41
First Fit (F.F)
07/05/2014 Bencheikh.Ghita 42
3 bins
Un seul bin
07/05/2014 Bencheikh.Ghita 43
Chaque objet possde une taille et une valeur
Objectif : maximiser la valeur du bin, en ne dpassant pas la taille autorise
Valeurs : 1 3 3 5 4 3 5 4 2 1 3
Un seul bin
07/05/2014 Bencheikh.Ghita 44
Chaque objet possde une taille et une valeur
Objectif : maximiser la valeur du bin, en ne dpassant pas la taille autorise
Valeurs : 1 3 3 5 4 3 5 4 2 1 3
1
3
4
5
13 Valeur du bin
Exemple dapplication
Prparation de au voyage
un tudiant souhaite partir avec ses amis, en voyage
07/05/2014 Bencheikh.Ghita 45
Modle mathmatique
Donns
n : nombre dobjets
P : capacit du bin
le valeur de lobjet j
la poids de lobjet i
Variables
07/05/2014 Bencheikh.Ghita 46
Modle mathmatique
Contrainte :
Objectif :
07/05/2014 Bencheikh.Ghita 47
Disposition Image avec lgende
Lgende
07/05/2014 48 Bencheikh.Ghita
MERCI DE VOTRE ATTENTION
07/05/2014 49 Bencheikh.Ghita
