Un mouvement incrémental pour le problème du strip-packing

Résumé : Alors qu'il est facile de maintenir la propriété BL lors de l'ajout d'un rectangle, ce maintien est plus coûteux après le retrait d'un rectangle. Cela rend difficile de concevoir des mouvements incrémentaux dans des métaheuristiques ou des algorithmes complets d'optimisation. Cet article explore la possibilité de violer la propriété BL. A la place, nous proposons de maintenir simplement un ensemble de "trous maximaux", ce qui permet l'ajout mais aussi le retrait incrémental de rectangles. Pour valider notre approche alternative, nous avons conçu un mouvement incrémental, qui maintient les trous maximaux, pour le problème du strip-packing, une variante du problème de placement de rectangles. Nous avons également utilisé des heuristiques initiales gloutonnes standard. et la métaheuristique {\tt ID~Walk} pour réaliser une recherche locale basée sur ce mouvement. Les résultats expérimentaux montrent que l'approche est compétitive avec les meilleurs algorithmes incomplets, plus spécialement avec les autres métaheuristiques (dotées de mécanismes pour sortir des mimima locaux).
Type de document :
Communication dans un congrès
Troisièmes Journées Francophones de Programmationpar Contraintes (JFPC07), Jun 2007, Rocquencourt / France, 2007, JFPC07
Liste complète des métadonnées

Littérature citée [14 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00151236
Contributeur : Sylvain Soliman <>
Soumis le : vendredi 1 juin 2007 - 19:00:49
Dernière modification le : lundi 16 juillet 2018 - 15:42:06
Document(s) archivé(s) le : vendredi 21 septembre 2012 - 16:06:10

Fichier

58.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00151236, version 1

Collections

Citation

Bertrand Neveu, Gilles Trombettoni, Ignacio Araya. Un mouvement incrémental pour le problème du strip-packing. Troisièmes Journées Francophones de Programmationpar Contraintes (JFPC07), Jun 2007, Rocquencourt / France, 2007, JFPC07. 〈inria-00151236〉

Partager

Métriques

Consultations de la notice

203

Téléchargements de fichiers

180