A parallel multi-objective algorithm for two-dimensional bin packing with rotations and load balancing

Bin packing problems are NP-hard combinatorial optimization problems of fundamental importance in several fields, including computer science, engineering, economics, management, manufacturing, transportation, and logistics. In particular, the non-guillotine version of the single-objective two-dimensional bin packing problem with rotations is a highly complex scheduling problem that consists in packing a set of items into the minimum number of bins, where items can be rotated 900 and are characterized by having different heights and widths. Recently, some authors have proposed multi-objective formulations that also consider additional objectives, such as the balancing the bin load in order to increase its stability. The load imbalance minimization, which depends on the distribution of the items packed in them, is a critical point in many real applications. This paper analyzes how to solve two-dimensional bin packing problems with rotations and load balancing using parallel and multi-objective memetic algorithms that apply a set of search operators specifically designed to solve this problem. Results obtained using a set of test problems show the good performance of parallel and multi-objective memetic algorithms in comparison with other methods found in the literature. (c) 2013 Elsevier Ltd. All rights reserved.