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, trans-portation, 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 90° and are characterized by hav-ing 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 stabil-ity. 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 compar-ison with other methods found in the literature.