s'authentifier
version française rss feed

tel-00749411, version 1

Bornes inférieures et méthodes exactes pour le problème de bin packing en deux dimensions avec orientation fixe

François Clautiaux () a12

Université de Technologie de Compiègne (10/04/2005), Jacques Carlier, Aziz Moukrim (Dir.)

Résumé : Notre problème consiste à déterminer le nombre de grands rectangles identiques nécessaires pour ranger une liste de rectangles sans modifier leur orientation. Nous proposons des méthodes pour calculer des bornes inférieures pour ce problème, essentiellement basée sur le concept de fonctions dual-réalisables. Nous proposons aussi deux méthodes exactes de type énumératives. L'une permet de déterminer si un ensemble de rectangles peut être contenu dans un rectangle unique. Elle repose sur une nouvelle relaxation du problème. La deuxième méthode permet de résoudre le problème général de bin packing en deux dimensions. Elle calcule pour cela une décomposition itérative de l'ensemble des rectangles à placer.

  • Domaine : Informatique/Recherche opérationnelle
  • Mots-clés : problème de conditionnement (bin-packing) en deux dimensions – bornes inférieures – méthodes exactes
 
  • tel-00749411, version 1
  • oai:tel.archives-ouvertes.fr:tel-00749411
  • Contributeur : 
  • Soumis le : Mercredi 7 Novembre 2012, 14:50:24
  • Dernière modification le : Jeudi 8 Novembre 2012, 09:08:08
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...