Displaying similar documents to “Online LIB problems : heuristics for bin covering and lower bounds for bin packing”

Online LIB problems: Heuristics for Bin Covering and lower bounds for Bin Packing

Luke Finlay, Prabhu Manyem (2006)

RAIRO - Operations Research

Similarity:

We consider the NP Hard problems of online Bin Covering and Packing while requiring that larger (or longer, in the one dimensional case) items be placed at the bottom of the bins, below smaller (or shorter) items — we call such a version, the version of problems. Bin sizes can be uniform or variable. We look at computational studies for both the Best Fit and Harmonic Fit algorithms for uniform sized bin covering. The Best Fit heuristic for this version of the problem is introduced...

Metaheuristics based on Bin Packing for the line balancing problem

Michel Gourgand, Nathalie Grangeon, Sylvie Norre (2007)

RAIRO - Operations Research

Similarity:

The line balancing problem consits in assigning tasks to stations in order to respect precedence constraints and cycle time constraints. In this paper, the cycle time is fixed and the objective is to minimize the number of stations. We propose to use metaheuristics based on simulated annealing by exploiting the link between the line balancing problem and the bin packing problem. The principle of the method lies in the combination between a metaheuristic and a bin packing heuristic....

Primal-dual approximation algorithms for a packing-covering pair of problems

Sofia Kovaleva, Frits C.R. Spieksma (2010)

RAIRO - Operations Research

Similarity:

We consider a special packing-covering pair of problems. The packing problem is a natural generalization of finding a (weighted) maximum independent set in an interval graph, the covering problem generalizes the problem of finding a (weighted) minimum clique cover in an interval graph. The problem pair involves weights and capacities; we consider the case of unit weights and the case of unit capacities. In each case we describe a simple algorithm that outputs a solution to the packing...

Algorithms for the two dimensional bin packing problem with partial conflicts

Khaoula Hamdi-Dhaoui, Nacima Labadie, Alice Yalaoui (2012)

RAIRO - Operations Research

Similarity:

The two-dimensional bin packing problem is a well-known problem for which several exact and approximation methods were proposed. In real life applications, such as in Hazardous Material transportation, transported items may be partially incompatible, and have to be separated by a safety distance. This complication has not yet been considered in the literature. This paper introduces this extension called the two-dimensional bin packing problem with partial conflicts (2BPPC) which is a...

Algorithms for the two dimensional bin packing problem with partial conflicts

Khaoula Hamdi-Dhaoui, Nacima Labadie, Alice Yalaoui (2012)

RAIRO - Operations Research

Similarity:

The two-dimensional bin packing problem is a well-known problem for which several exact and approximation methods were proposed. In real life applications, such as in Hazardous Material transportation, transported items may be partially incompatible, and have to be separated by a safety distance. This complication has not yet been considered in the literature. This paper introduces this extension called the two-dimensional bin packing problem with partial conflicts (2BPPC) which is a...

A note on dual approximation algorithms for class constrained bin packing problems

Eduardo C. Xavier, Flàvio Keidi Miyazawa (2009)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Similarity:

In this paper we present a dual approximation scheme for the class constrained shelf bin packing problem. In this problem, we are given bins of capacity 1 , and n items of Q different classes, each item e with class c e and size s e . The problem is to pack the items into bins, such that two items of different classes packed in a same bin must be in different shelves. Items in a same shelf are packed consecutively. Moreover, items in consecutive shelves must be separated by shelf divisors...