About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
IJCAI 1997
Conference paper
An approximate 0-1 edge-labeling algorithm for constrained bin-packing problem
Abstract
This paper describes a constrained bin-packing •problem (CBPP) and an approximate, anytime algorithm for solutions. A CBPP is a constrained version of the bin-packing problem, in which a set of items allocated to a bin are ordered in a way to satisfy constraints defined on them and achieve near-optimality. The algorithm for CBPP uses a heuristic search for labeling edges with a binary value, together with a beam search and constraint propagation. Some experimental results are provided. This algorithm has been successfully applied to industrial-scale scheduling problems.