Variable sized bin packing with color constraints

Abstract

In this paper, we introduce the variable sized bin packing problem with novel packing constraints, called the color constraints. In an instance of this problem, we have n items to be packed into bins of m distinct sizes. Items come with two attributes: color and size. In addition to the usual capacity constraints, we require that each bin contain items with at most p distinct colors, where p is a pre-specified positive integer. Our objective is to minimize the total capacity of the bins used in the packing. This problem arises as a model for the slab design problem in the production planning process of a steel plant. An APTAS and two 3-approximations are presented.