La Résolution de Problème de Bin Packing
Rectangulaire avec Contraintes
En Deux Etapes Génétiques Hybrides
Résumé :
Le problème de Bin Packing se retrouve dans plusieurs domaines
d’application, essentiellement dans l’industrie de : tôle, bois, verre, papier etc.
Dans cet article on s’intéresse au problème de découpe rectangulaire, avec la
prise en charge de la contrainte de découpe de bout-en-bout.
L’application des algorithmes génétiques connaît des limites pour la
résolution du problème de bin packing de grande taille. Pour résoudre ce
problème nous proposons une méthode originale qui consiste à subdiviser le
problème initial en deux sous problèmes. La première partie tente d’appliquer
un algorithme génétique hybride, basé sur l’ordre d’apparition des pièces, pour
agencer les pièces sur des niveaux dans une bande infinie en appliquant une
heuristique puissante (BLF2G). La deuxième étape utilise les résultats de la
première, à savoir les niveaux, et tente de les projeter sur les plaques en
appliquant un deuxième algorithme génétique hybride. De plus nous avons
proposé des améliorations à l’algorithme génétique classique pour améliorer les
résultats. Les résultats sont comparés avec d’autres méthodes heuristiques sur
des exemples aléatoires et réels.
Mots Clés : Bin Packing deux dimensionnel, découpe orthogonale,
optimisation combinatoire, heuristique, algorithme génétique hybride.
I) Introduction.
Le problème de placement est un problème d’optimisation dont
l’objectif est de chercher à trouver un bon arrangement de différents objets
dans d’autres plus larges. L’objectif principal est de maximiser l’exploitation
de la matière première, et donc de minimiser les pertes. Ceci est important
pour les industries à production massive où l’optimisation de la matière joue un
rôle important dans la réduction de coûts de fabrication.
Le développement d’un algorithme pour la résolution d’un problème
de placement industriel doit prendre en considération la complexité du
problème déterminée par la forme des objets manipulés, et des contraintes liées
(imposées par le système de production).
Dans notre cas on prend en considération un problème de découpe
orthogonal qui manipule des plaques brutes rectangulaires pour générer des
pièces de forme rectangulaire également. La matière utilisée peut être de la tôle
et les machine de production sont typiquement des cisailles-guillotine (découpe
de bout-en-bout). Pour que notre algorithme ne se limite pas a ce type de
problèmes, et pour qu’il puisse être étendu à d’autres problèmes vérifiant les
contraintes imposées, l’orientation des objets n’est pas autorisée, une telle
contrainte est vérifiée dans plusieurs travaux et laisse l’algorithme abordable
pour un vaste nombre d’applications, tel que le bois, le verre, le tissu, … où on
trouve des motifs ou des décorations, et même dans la mise en page des
journaux, revue, ou page web, où l’orientation est fixée.
II) Les contraintes du problème.
- La découpe orthogonale.
Les découpes sont réalisées en longueur ou en largeur. Les découpes
diagonales ne sont pas réalisables.
Forme non réalisable par la cisaille
2
- La découpe de bout-en-bout.
Cette contrainte est liée directement aux cisaille-guillotines qui sont
les machines typiques pour la manipulation de la tôle pris en
considération par notre approche. Il s’agit d’une contrainte qui assure
la faisabilité des formats de découpe dans l’atelier de production.
Forme réalisable par la cisaille Forme non réalisable par la cisaille
- L’orientation des pièces.
Les pièces garde leurs orientations d’origine, cette contrainte vise à
assurer la faisabilité des formats de découpe réalisée sur des surfaces texturées
ou décorées.
III) Etat de l’art.
Peu des travaux ont utilisé les algorithmes génétiques pour la
résolution de ce problème, récemment E. Hopper & B. Turton se sont intéressé,
à l’application des algorithmes génétiques pour la résolution de ce problème.
Après un état de l’art en 1997 qui recense les travaux réalisés dans ce
domaine[Hop97], ils présentent deux algorithmes génétiques hybridés avec des
heuristiques de placement en 1999[Hop99]. Ces travaux sont couronnés par
une thèse de doctorat en philosophie en 2000[Hop00], d’autres travaux on fait
référence aux algorithmes génétiques pour la résolution du problème on peut
citer [Val01], [Fuj93], [Rai99]…
Un inconvénient commun confirmé par les auteurs, ([Hop00],
[Val01]…), rencontré par les algorithmes génétiques, est le problème de temps
de résolution qui devient de plus en plus grand pour les problèmes de grandes
tailles. Il réduit l’efficacité des algorithmes génétiques en application au
problème de placement pour lesquels ils donnent des résultats nettement moins
bons que les heuristiques simples. Par conséquent il est nécessaire de limiter
3
l’exploration de l’espace de recherche. Notre approche de résolution évite cet
inconvénient grâce aux améliorations que nous avons proposé à l’algorithme
génétique classique.
IV) L’algorithme génétique.
Une vue commune trouvée dans la plupart des algorithmes génétiques
développée pour le problème d’agencement, est l’hybridation de l’algorithme
en deux étapes de résolution [Hop99]. L’algorithme génétique explore l’espace
de recherche pour en générer les individus. Une deuxième étape non génétique
est nécessaire pour évaluer la performance des individus. L’algorithme
génétique offre des solutions basées sur l’ordre d’apparition des pièces au
procédé d’agencement. Le format de découpe exact est donné par la routine de
placement.
La qualité de l’individu dépend essentiellement de l’ordre dans lequel
les pièces sont présentées à la routine de placement adoptée. Le nombre de
combinaisons est trop grand pour être exploré d’une manière exhaustive en un
temps raisonnable. L’algorithme génétique est la stratégie de recherche la plus
efficace [Hop99], en utilisant une représentation basée sur l’ordre. Cette
représentation nécessite une nouvelle définition des opérateurs de croisement et
de permutation, qui sont identique à celles de problème de voyageur de
commerce.
L’opérateur de croisement :
Nous proposons d’appliquer un algorithme génétique hybride basé sur
l’ordre d’apparition des pièces. Le croisement égalé partiel (PMX) est utilisé,
qui est le plus efficace en application aux problèmes basés sur l’ordre
[Mic96][Hop99].
L’opérateur de croisement classique PMX [Gol89] peut donner
naissance à des individus non réalisables, par exemple :
parent 1 : 1234|5678 fils1 : 1234|4321
et donne et
parent 2 : 8765|4321 fils2 : 8765|5678
4
Ces deux nouveaux individus ne représentent pas un ordre valable. Pour
ce faire, on doit corriger les deux fils pour qu’ils soient réalisables. Pour
chaque fils le croisement PMX remplace les doublants par les numéros
manquant dans l’individu selon l’ordre de leurs apparitions dans l’autre parent.
Exemple :
parent 1 : 8167|4253 : 8167|1825 fils 1 : 8167|4325
et donne et on aura
parent 2 : 6437|1825 : 6437|4253 fils 2 : 6473|8251
l’opérateur de mutation :
L’opérateur de mutation peut simplement être présenté comme une
permutation. Il suffit de choisir deux sites dans l’individu et effectuer la
permutation en ces deux sites.
Exemple :
81|67432|5 devient : 81|57432|6
V) La première étape « pré-traitement ».
- La routine de placement.
L’agencement des pièces s’effectue sur une bande infinie subdivisée en
niveaux (Val01). L’agencement s’effectue en appliquant une heuristique
adéquate, il s’agit de l’heuristique BLF (Bottom Left Fill), qui tente de placer
les pièces dans l’endroit le plus bas à gauche possible (Hop99). Contrairement
à la politique BL (Bottom Left), la politique BLF tente d ‘exploiter les résidus
les plus bas possible.
Agencement selon Agencement selon
La politique BL. La politique BLF.
5
Cette phase nous permet de réaliser l’agencement effectif des pièces sur
la bande structurée en niveaux, et elle nous donne une valeur qui est la hauteur
de la bande. Cette valeur définit la qualité de la routine de placement.
1ère pièce placée
niv. i dans le niveau i
niv. i-1
Bande
niv. 0 h=0
La bande est constituée de plusieurs niveaux.
Pour notre problème nous avons développer la routine BLFG qui
applique la politique BLF mais elle réalise l’agencement des pièces en niveaux.
Le « G » pour exprimer (Guillotinable). Notons que l’exploitation des résidus
intra-niveau nécessite un temps de calcul supplémentaire. Pour cela nous avons
défini trois nuances de la politique BLFG, a savoir BLF0G, BLF1G, BLF2G,
définies ainsi :
BLF0G : elle ne réalise aucune exploitation des résidus
intra-niveau (identique à BLG).
Résidus intra niveaux non
exploités selon la politique
BLF0G.
Aucune exploitation des résidus selon la politique BLF0G.
6
BLF1G : elle réalise une exploitation verticale des résidus
intra-niveau.
Pièces placées dans les
résidus selon la politique
BLF1G.
Exploitation des résidus selon la politique BLF1G
BLF2G : elle réalise une exploitation verticale et
horizontale des résidus intra-niveau.
Pièces ajoutées aux résidus
selon la politique BLF2G.
Exploitation des résidus selon la politique BLF2G
VI) La deuxième phase « d’emboîtement ».
Le résultat obtenu à l’étape précédente entre dans cette phase génétique,
il s’agit maintenant de projeter les niveaux, caractérisés par leurs hauteurs sur
les plaques.
- La routine de placement.
Pour chaque individu de la population la routine de placement est
appliquée pour évaluer sa qualité (fitness). L’heuristique BL, qui place le
niveau courant dans la première plaque offrant un résidu suffisant, est
appliquée.
7
VII) L’organigramme.
On schématise notre algorithme par l’organigramme suivant :
Début
Base de ChargerListePieces() ;
données
Le Pré-Traitement
GenererPopInitLP() ;
If(Guider)TrierGenLP() ;
Paramètres Génération := 0 ;
génétiques ;
Non
Garder Le meilleur Génération
< MaxGens
Oui
L’Emboîtement SelectLP() ;
GenererPopInitLN() ; CrossOverLP() ;
If(Guider)TrierGenLN() ; MutateLP() ;
Génération := 0 ; ElitistLP() ;
; ++ génération ;
Non
Génération
< MaxGens Garder Le meilleur
Oui
Visualiser les résultats
SelectLN() ;
CrossOverLN() ;
MutateLN() ;
ElitistLN() ;
Fin
++ génération ;
VIII) Notre contribution.
Notre contribution à la résolution du problème se résume dans les
améliorations suivantes:
1. Guider l’algorithme génétique.
Selon les résultats obtenus, en appliquant les algorithmes génétiques au
problème de placement, on constate que pour les problèmes de moyen et grand
taille les méthodes heuristiques, basées sur le tri selon la décroissance des
longueurs, offrent des résultats meilleurs que les algorithmes génétiques. Notre
8
première amélioration consiste donc à guider la génération initiale en ajoutant,
cet individu trié. De ce fait, notre méthode prend le relais des heuristiques.
Donc notre contribution donne des résultats égaux ou même meilleurs que les
méthodes heuristiques classiques indépendamment de la taille du problème.
2. Optimisation en largeur.
Pour certains exemples où nous avons appliqué notre approche
d’agencement sur la bande en fixant la largeur de la bande, on constate que
l’écart entre les longueurs des pièces est élevé, de ce fait les résultats ne sont
pas satisfaisants. Notre deuxième amélioration sera donc, de procéder à
l’agencement des pièces sur la bande en largeur, i.e. en fixant la longueur de la
bande, et on agence les pièces en largeurs.
On illustre l’agencement en largeur par l’exemple suivant :
Résultat d’agencement
On remarque nettement d’un jeu de pièces
l’apport en longueur
de cette et en largeur.
amélioration pour ce jeu de
pièces. Notons que les pièces garde leurs orientations d’origine, seule la bande
qui change de direction et l’agencement s’effectue en largeur.
Avec cette amélioration, on donne de la souplesse à notre approche, et
l’utilisateur aura le choix entre l’agencement en longueur et l’agencement en
largeur selon le jeu de pièces utilisé.
9
IX) Résultats.
Les premiers résultats apparaissent, ainsi une phase de mise en forme et
d’amélioration est réalisée sur le logiciel.
Pour évaluer notre méthode on à confectionné des jeux de test qui
offrent une exploitation maximale de la matière (0% de chutes) en appliquant la
politique BLF2G, et on gardant l’ordre initial d’apparition des pièces. Il s’agit
de :
Nom Taille Optimal
Msa17 17 200 x 200
Msa35 35 200 x 200
Msa75 75 200 x 200
Msa150 150 200 x 200
Les résultats expérimentaux des quatre jeux de tests en appliquant notre
approche avec une exploitation maximale de la matière sont récapitulés dans le
tableau suivant. Notons que les jeux de test ont été confectionnés en longueur
(i.e. l’agencement en largeur ne garanti pas l’optimal).
Exploitation en longueur Exploitation en largeur
Jeux de Non Guidé DH Non Guidé DW
Test Guidé Guidé
Msa17 200x200 200x200 263x200 200x222 200x222 200x249
Msa35 219x200 215x200 229x200 200x223 200x223 200x226
Msa75 218x200 210x200 210x200 200x217 200x212 200x226
Msa150 224x200 213x200 218x200 200x224 200x212 200x219
10x Msa17 2154x200 2109x200 2139x200 200x2207 200x2115 200x2157
Les résultats montrent que l’algorithme classique atteint l’optimal pour
les petits jeux de test et approche de l’optimal pour les jeux de test de moyenne
taille. Et même donne des résultats meilleurs que l’heuristique basée sur le tri.
En ce qui concerne les jeux de test de grande taille l’heuristique basée sur le tri
donne des résultats meilleurs que l’algorithme classique. L’algorithme guidé
trouve son utilité dans ce cas de figure.
10
X) Améliorations.
1. Guider l’algorithme génétique.
Vu les améliorations apportées par l’insertion d’un individu, trié selon la
décroissance des longueurs, et en vue d’enrichir la méthode, nous avons
proposé d’introduire certains heuristiques basées sur des politiques de tri à la
population initiale.
Il s’agit des quatre politiques suivantes:
a) Trier selon la croissance des longueurs.
Il s’agit d’effectuer un simple tri selon la croissance des longueurs.
b) Trier selon la décroissant puis la croissance des
longueurs.
c) Trier selon la croissance puis la décroissance des
longueurs.
11
d) Trier alternativement selon la décroissance puis la
croissance des longueurs (harmonique).
Les résultats obtenus montre l’apport de cette amélioration sur certains
jeu de test, qui sont représenté sur le tableau suivant :
Exploitation en longueur Exploitation en largeur
Jeux de Test Non Guidé Guidé Non Guidé Guidé
Msa17 200x200 200x200 200x222 200x222
Msa35 219x200 215x200 200x223 200x221
Msa75 218x200 210x200 200x217 200x212
Msa150 224x200 213x200 200x224 200x211
10x Msa17 2154x200 2109x200 200x2207 200x2103
2. La ré-initialisation de la population.
D’après le suivi de l’exécution de traitement on a constaté que
l’algorithme génétique converge vers un optimale locale après un certain
nombre de génération. Et qu’il n’y a plus d’améliorations à partir de ce rang.
Pour remédier à cela et donner plus de vitalité à l’algorithme on a introduit un
nouveau paramètre à l’algorithme. Il sert à ré-initialiser la population courante
en générant une nouvelle population aléatoire et en gardant le meilleur individu
issu des générations précédentes. Ce paramètre ne doit pas altérer le processus
génétique. Une intervention fréquente de ce paramètre dégrade les résultats.
Pour cela on définit un nouveau paramètre nommé Seuil de Stabilité qui sera
défini par l’utilisateur. Quand l’algorithme atteint ce seuil le nouveau
12
paramètre de ré-inisialisation sera opérationnel, ainsi des phases de ré-
inisialisation seront déclenchées.
Le tableau suivant présent le résultat de notre approche sur les quatre
jeux de test en appliquant le nouveau paramètre de ré-initialisation de la
population :
Exploitation en longueur Exploitation en largeur
Jeux de Test Non Guidé Guidé Non Guidé Guidé
Msa17 200x200 200x200 200x213 200x222
Msa35 215x200 215x200 200x223 200x221
Msa75 213x200 210x200 200x212 200x212
Msa150 219x200 213x200 200x222 200x211
10x Msa17 2149x200 2109x200 200x2200 200x2103
On remarque les améliorations apportées par ce nouveau paramètre.
XI) Comparaisons.
Nous avons utilisé un vaste nombre de jeu de tests et trouvés dans la
littérature, dont on connaît la solution optimale.
Référence Nom Taille Optimal
[Bur99a] Kendall 13 140 x 80
[Rat97b] D2 21 40 x 60
[Jak96] J1 25 40 x 15
[Jak96] J2 50 40 x 15
[Hop99] T1a, T1b, T1c, T1d, T1e 17 200 x 200
[Hop99] T2a, T2b, T2c, T2d, T2e 25 200 x 200
[Hop99] T3a, T3b, T3c, T3d, T3e 29 200 x 200
[Hop99] T4a, T4b, T4c, T4d, T4e 49 200 x 200
[Hop99] T5a, T5b, T5c, T5d, T5e 73 200 x 200
[Hop99] T6a, T6b, T6c, T6d, T6e 97 200 x 200
[Hop99] T7a, T7b, T7c, T7d, T7e 197 200 x 200
13
Notons bien que ces exemples de tests ne sont pas confectionnés pour
vérifier la contrainte de découpe de bout-en-bout. Donc l’optimal risque de ne
pas être atteint par notre méthode. Nous lançons notre méthode sur ces
exemples juste pour situer notre position, et voir la différence.
Exploitation en longueur Exploitation en largeur
Jeux de AG Notre AG Notre
test Classique Approche DH Classique Approche DW
Kendall 162x80 162x80 210x80 140x102 140x102 140x102
16,63% 16,63% 50% 28,51% 28,51% 27,5%
D2 40x60 40x60 47x60 40x60 40x60 40x72
0% 0% 17.5% 0% 0% 20%
J1 43x15 43x15 48x15 40x18 40x18 40x18
7,5% 7,5% 20% 20% 20% 20%
J2 43x15 42x15 43x15 40x17 40x16 40x16
5,12% 5% 7,5% 7,08% 6,67% 6,67%
T1a 237x200 237x200 300x200 200x246 200x231 200x260
18,5% 18,5% 50% 23% 15,5% 30%
T3a 234x200 229x200 256x200 200x239 200x232 200x265
17% 14,5% 28% 19,5% 16% 32,5%
T5a 238x200 217x200 218x200 200x239 200x215 200x223
19% 8,5% 9% 19,5% 7,5% 11,5%
T7a 226x200 212x200 214x200 200x227 200x210 200x217
13% 6% 7% 13,5% 5% 8,5%
Ces résultats montrent la puissance de notre méthode en matière
d’exploitation des résidus tout en vérifiant la contrainte de découpe de bout-en-
bout. Notre méthode a approché nettement de l’optimal pour les exemples de
Jakobs (J1 et J2) et elle atteint même l’optimal pour l’exemple de Dagli (D2),
qui sont des jeux de test de petite taille. En ce qui concerne les jeux de test de
Hopper on a choisi quatre exemples de petite moyenne et grand taille. Les
résultats obtenus sont très satisfaisants du fait qu’on a approché de l’optimal
malgré que ces jeux de test ne vérifient pas la contrainte de découpe de bout-
en-bout.
Pour mieux situer notre approche nous avons utilisé un exemple réel
[Msa95]. Il s’agit de produit D703 où les résultats obtenus sont 31 plaques de
dimension 2500x1250.
14
Notre méthode à donnée le résultat suivant (en nombre de plaque):
Exploitation en longueur Exploitation en largeur
Jeux de Non Guidé DH Non Guidé DW
Test Guidé Guidé
MsaPFE95 29 29 29 28 28 28
On voit bien qu’il n’y a pas une grande déférence entre les résultats. 29
plaques pour l’agencement en longueur et pour les trois nuances (non guidé,
guidé, et trié) et de même pour l’agencement en largeur (28 plaques partout).
L’apport de notre méthode n’est pas remarquable dans ce cas, seulement 3
plaques de gain par rapport au résultat obtenu par [Msa95], une telle chose est
expliquée par l’absence des petites pièces qui font la puissance de notre
méthode en matière d’exploitation des résidus.
XII) Conclusion.
Notre contribution, au problème de découpe rectangulaire, a montré son
efficacité. En premier lieu nous avons développé une routine puissante en
matière d’exploitation des résidus (BLF2G). Deuxièmement nous avons
hybridé cette routine avec un algorithme génétique amélioré, qui surmonte les
problèmes rencontrés par les algorithmes génétiques classiques. Pour les
problèmes de petite taille notre méthode a atteint l’optimal. Pour les problèmes
de moyenne taille notre méthode a approché nettement de l’optimal, et elle a
donné des résultats meilleurs que celui de l’heuristique basée sur le tri. Pour les
problèmes de grande taille notre méthode a divergé, (comme les autres
méthodes génétiques classiques), et l’heuristique basée sur le tri a donné des
résultats meilleurs. Mais avec l’option de guider l’algorithme génétique par
l’individu trié, notre méthode a réussi de reprendre la main et améliore même le
résultat trouvé par l’heuristique basée sur le tri.
La position de notre méthode par rapport aux autres méthodes est bonne.
Malgré que notre approche tient compte de la contrainte de découpe de bout-
en-bout, on a réussi à avoir des résultats comparables avec d’autres méthodes
15
qui ne vérifient pas cette contrainte. En plus notre deuxième amélioration
d’agencement en largeur a donné de la souplesse à notre méthode, et donne
souvent des résultats meilleurs que l’agencement classique (en longueur).
XIII) Travail futur.
L’utilisation des algorithmes génétiques qui sont des méthodes
puissantes en matière d’exploration de l’espace de recherche connaît ces limites
dans l’application au problème de découpe de moyenne et grande taille. En
perspective, et vu la nette amélioration apportée par l’introduction de l’individu
trié à la population initiale, le développement d’une méthode heuristique qui
sert à guider l’algorithme génétique tout le long de son processus génétique
depuis la population initiale jusqu’aux opérateurs génétiques, reste à exploiter.
De plus ce travail peut être étendu à d’autres formes géométriques, en vue
d’être appliqué pour la découpe de cuir, de tissus, etc…
En plus le parallélisme des algorithmes génétiques offre des avantages
en temps de résolution et en qualité des solutions reste aussi à explorer.
Références Bibliographique.
[Bur99a] E. Burke and G. Kendall, Comparison of Meta-Heuristic Algorithms
for Clustering Rectangles. Computers in Engineering 37, 383-386,
1999a.
[Fuj93] K. Fujita, S. Akagi, N. Hirokawa, Hybrid Approach for Optimal
Nesting Using a Genetic Algorithm and a Local Minimization
Algorithm, Department of Mechanical Engineering for Industrial
Machinery and Systems, Osaka University Suita, Osaka, JAPAN,
1993.
[Gol89] D. E. Goldberg, Genetic algorithms in search, optimization, and
machine learning. Reading, MA: Addison-Wesley, 1989.
16
[Hop97] E. Hopper, B. Turton, Application of Genetic Algorithms to Packing
Problems – A review, In : Proceedings of the 2nd On-line World
Conference on Soft Computing in Engineering Design and
Manufacturing, Springer Verlag, London, pp279-288, 1997.
[Hop99] E. Hopper, B. Turton, A Genetic Algorithm for a 2D Industrial
Packing Problem, Computers and Industrial Engineering, vol. 37/1-2,
pp. 375-378, 1999.
[Hop00] Eva Hopper, Two-dimensional Packing utilizing Evolutionary
Algorithms and other Meta-Heuristic Methods, A Thesis submitted to
the University of Wales for the Degree of Doctor of Philosophy, May
2000.
[Jak96] S. Jakobs, On genetic algorithms for the packing of polygons.
European Journal of Operations, Research 88, 165-181, 1996
[Mic96] Z. Michalewics, Genetic Algorithms + Data Structures = Evolution
Programs, Third, Revised and Extended Edition, Springer 1996.
[Msa95] S. Abou Msabah, M. Izzerouken, Conception et Réalisation d’un
logiciel d’optimisation des chutes de tôles, Mémoire du Projet de fin
d’études pour l’obtention du diplôme d’ingénieur d’état en
Informatique, Faculté du Génie Electrique, Département
d’Informatique, USTHB, 1995.
[Rai99] G. R. Raidl, G. Kodydek, Genetic Algorithms for the Multiple
Container Packing Problem, Department of computer graphics, Vienna
University of Technology, Karlsplatz 13/1861, 1040 Vienna, Austria,
1999.
[Rat97a] Ratanapan K. and Dagli C. H. An object-based evolutionary
algorithm for solving rectangular piece nesting problems. In: IEEE
(eds.), Proceedings of the IEEE Conference on Evolutionary
Computation, ICEC, IEEE, Piscataway, NJ, USA, pp. 989-994, 1997.
[Val01] C. L. Valensuela, P. Y. Wang, Heuristics for Large Strip Packing
Problems with Guillotine Patterns : an Empirical Study, MIC’2001, 4th
Meta-heuristics International Conference, 2001.
17
