A Constrained Bin-Packing Problem

        We describe a constrained bin-packing problem (CBPP) and its solution. A CBPP is a constrained version of the bin-packing problem, in which items allocated to a bin are an ordered set satisfying constraints defined on them. The solution methodology is basically a greeedy heuristic search algorithm with beam search and constraint propagation. It can generate multiple near-optimal solutions is a reasonable time. This algorithm has been successfully applied to industrial-scale scheduling problems.

By: Mark Trumbo, Ho Soo Lee and Brian Knoth

Published in: RC20516 in 1996

This Research Report is not available electronically. Please request a copy from the contact listed below. IBM employees should contact ITIRC for a copy.

Questions about this service can be mailed to reports@us.ibm.com .