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

François Clautiaux 1, 2
1 DOLPHIN - Parallel Cooperative Multi-criteria Optimization
Inria Lille - Nord Europe, LIFL - Laboratoire d'Informatique Fondamentale de Lille
Abstract : Our problem consists in determining the number of large identical rectangles used to pack a list of rectangles with a fixed orientation. We propose methods to compute lower bounds, based on the concept of dual-feasible functions. We also propose two enumerative exact methods. One is devoted to the problem with one bin. It uses a new relaxation of the problem. The other solves the optimization problem by iteratively decomposing the set of rectangles.
Document type :
Theses
Recherche opérationnelle [cs.RO]. Université de Technologie de Compiègne, 2005. Français


https://tel.archives-ouvertes.fr/tel-00749411
Contributor : François Clautiaux <>
Submitted on : Wednesday, November 7, 2012 - 2:50:24 PM
Last modification on : Saturday, January 16, 2016 - 1:09:57 AM
Document(s) archivé(s) le : Friday, February 8, 2013 - 3:43:24 AM

Identifiers

  • HAL Id : tel-00749411, version 1

Citation

François Clautiaux. Bornes inférieures et méthodes exactes pour le problème de bin packing en deux dimensions avec orientation fixe. Recherche opérationnelle [cs.RO]. Université de Technologie de Compiègne, 2005. Français. <tel-00749411>

Export

Share

Metrics

Record views

284

Document downloads

171