Optimisation hybride par colonies de fourmis pour le problème de découpe à deux dimensions

Alice Yalaoui; Chengbin Chu

RAIRO - Operations Research (2009)

  • Volume: 43, Issue: 1, page 87-101
  • ISSN: 0399-0559

Abstract

top
In this paper, we are interested in the guillotine bin packing problem (2BP/O/G). The aim of this problem is to cut a set of rectangular pieces (items) from a set of identical large rectangular pieces (stock sheets). We try to minimize the number of stock sheets used in order to satisfy the demand. This is done applying edge to edge cut, which is called the guillotine constraint. We propose in this paper a resolution approach using Ant Colony Optimization (ACO) and the SHF-FF heuristic of Ben Messaoud et al. [2] in order to solve this NP-hard problem. We improve the best known results.

How to cite

top

Yalaoui, Alice, and Chu, Chengbin. "Optimisation hybride par colonies de fourmis pour le problème de découpe à deux dimensions." RAIRO - Operations Research 43.1 (2009): 87-101. <http://eudml.org/doc/250547>.

@article{Yalaoui2009,
abstract = { Nous nous intéressons dans cet article au problème de découpe guillotine en deux dimensions noté 2BP/O/G. Il s'agit de découper un certain nombre de pièces rectangulaires dans un ensemble de plaques de matière première, elles même rectangulaires et identiques. Celles-ci sont disponibles en quantité illimitée. L'objectif est de minimiser le nombre de plaques utilisées pour satisfaire la demande, en appliquant une succession de coupes, dites guillotines, allant de bout en bout. Nous proposons une approche de résolution combinant l'optimisation par colonies de fourmis (ACO) et l'heuristique SHF-FF de Ben Messaoud et al. [2] pour résoudre ce problème NP-difficile. },
author = {Yalaoui, Alice, Chu, Chengbin},
journal = {RAIRO - Operations Research},
keywords = {Colonies de fourmis; découpe; guillotine; optimisation; Bin packing.; colonies de fourmis; bin packing},
language = {fre},
month = {1},
number = {1},
pages = {87-101},
publisher = {EDP Sciences},
title = {Optimisation hybride par colonies de fourmis pour le problème de découpe à deux dimensions},
url = {http://eudml.org/doc/250547},
volume = {43},
year = {2009},
}

TY - JOUR
AU - Yalaoui, Alice
AU - Chu, Chengbin
TI - Optimisation hybride par colonies de fourmis pour le problème de découpe à deux dimensions
JO - RAIRO - Operations Research
DA - 2009/1//
PB - EDP Sciences
VL - 43
IS - 1
SP - 87
EP - 101
AB - Nous nous intéressons dans cet article au problème de découpe guillotine en deux dimensions noté 2BP/O/G. Il s'agit de découper un certain nombre de pièces rectangulaires dans un ensemble de plaques de matière première, elles même rectangulaires et identiques. Celles-ci sont disponibles en quantité illimitée. L'objectif est de minimiser le nombre de plaques utilisées pour satisfaire la demande, en appliquant une succession de coupes, dites guillotines, allant de bout en bout. Nous proposons une approche de résolution combinant l'optimisation par colonies de fourmis (ACO) et l'heuristique SHF-FF de Ben Messaoud et al. [2] pour résoudre ce problème NP-difficile.
LA - fre
KW - Colonies de fourmis; découpe; guillotine; optimisation; Bin packing.; colonies de fourmis; bin packing
UR - http://eudml.org/doc/250547
ER -

References

top
  1. S. Ben messaoud, C. Chu and M.L. Espinouse, Une nouvelle heuristique pour le problème de découpe guillotine en 2D, in Proc.MOSIM'03, Toulouse, France (2003) 116–121.  
  2. S. Ben messaoud, C. Chu and M.L. Espinouse, New concept of the classic shelf algorithm. Proc. IEPM'03, Porto, Portugal (2003) 465–471.  
  3. J.O. Berkey and P.Y. Wang, Two dimensional finite bin-packing algorithms. J. Oper. Res. Soc.38 (1987) 423–429.  
  4. F. Chung, M. Garey and D. Johnson, On packing two-dimensional bins. SIAM J. Algebr. Discrete Methods3 (1982) 66–76.  
  5. M. Dorigo, V. Maniezzo and A. Colorni, The ant system: Optimization by a colony of cooperating agents. IEEE Trans. Syst. Man Cybern. B26 (1996) 29–71.  
  6. H. Dyckhoff, A typology of cutting and packing problems. Eur. J. Oper. Res.44 (1990) 145–159.  
  7. J. Levine and F. Ducatelle, Ant Colony optimization and local search for bin packing and cutting stock problems. J. Oper. Res. Soc.55 (2004) 705–716.  
  8. A. Lodi, S. Martello and D. Vigo, Neighborhood search algorithm for the guillotine non-oriented two-dimensional bin packing problem, in Meta-heuristics: Advances and Trends in Local Search Paradigms for Optimization, S. Voss, S. Martello, I.H. Osman, C. Roucairol, Kluwer academic Publishers, Boston (1998) 125–139.  
  9. A. Lodi, S. Martello and D. Vigo, Recent advances on two-dimensional bin packing problems. Discrete Appl. Math.123 (2002) 379–396.  
  10. A. Lodi, S. Martello and D. Vigo, Two-dimensional packing problems: A survey. Eur. J. Oper. Res.141 (2002) 241–252.  

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.