• English
    • français
  • Help
  •  | 
  • Contact
  •  | 
  • About
  •  | 
  • Login
  • HAL portal
  •  | 
  • Pages Pro
  • EN
  •  / 
  • FR
View Item 
  •   LillOA Home
  • Liste des unités
  • Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189
  • View Item
  •   LillOA Home
  • Liste des unités
  • Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Lower and Upper Bounds for the Bin Packing ...
  • BibTeX
  • CSV
  • Excel
  • RIS

Document type :
Article dans une revue scientifique
DOI :
10.1016/j.dam.2012.04.010
Title :
Lower and Upper Bounds for the Bin Packing Problem with Fragile Objects
Author(s) :
Clautiaux, François [Auteur]
Laboratoire d'Informatique Fondamentale de Lille [LIFL]
Parallel Cooperative Multi-criteria Optimization [DOLPHIN]
Dell Amico, Mauro [Auteur]
Università degli Studi di Modena e Reggio Emilia = University of Modena and Reggio Emilia [UNIMORE]
Iori, Manuel [Auteur]
Università degli Studi di Modena e Reggio Emilia = University of Modena and Reggio Emilia [UNIMORE]
Khanafer, Ali [Auteur]
Parallel Cooperative Multi-criteria Optimization [DOLPHIN]
Journal title :
Discrete Applied Mathematics
Pages :
73-86
Publisher :
Elsevier
Publication date :
2014
ISSN :
0166-218X
HAL domain(s) :
Informatique [cs]/Recherche opérationnelle [cs.RO]
English abstract : [en]
We are given a set of items, each characterized by a weight and a fragility, and a large number of uncapacitated bins. Our aim is to find the minimum number of bins needed to pack all items, in such a way that in each bin ...
Show more >
We are given a set of items, each characterized by a weight and a fragility, and a large number of uncapacitated bins. Our aim is to find the minimum number of bins needed to pack all items, in such a way that in each bin the sum of the item weights is less than or equal to the smallest fragility of an item in the bin. The problem is known in the literature as the Bin Packing Problem with Fragile Objects, and appears in the telecommunication field, when one has to assign cellular calls to available channels by ensuring that the total noise in a channel does not exceed the noise acceptance limit of a call.We propose several techniques to compute lower and upper bounds for this problem. For what concerns lower bounds, we present combinatorial techniques with guaranteed worst case and a more complex bound based on a column generation algorithm. We also present a technique to compute, in a fast heuristic way, dual information that is used to strengthen the convergence of the column generation. For what concerns upper bounds, we present a large set of constructive heuristics followed by a Variable Neighborhood Search algorithm. Our heuristic techniques are aimed at both computing upper bounds and strengthening the behavior of the lower bounds in a matheuristic fashion. Extensive computational tests show the effectiveness of the proposed algorithms.Show less >
Language :
Anglais
Peer reviewed article :
Oui
Audience :
Internationale
Popular science :
Non
Collections :
  • Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189
Source :
Harvested from HAL
Files
Thumbnail
  • https://doi.org/10.1016/j.dam.2012.04.010
  • Open access
  • Access the document
Thumbnail
  • https://doi.org/10.1016/j.dam.2012.04.010
  • Open access
  • Access the document
Thumbnail
  • https://doi.org/10.1016/j.dam.2012.04.010
  • Open access
  • Access the document
Thumbnail
  • https://doi.org/10.1016/j.dam.2012.04.010
  • Open access
  • Access the document
Université de Lille

Mentions légales
Université de Lille © 2017