A parallel multi-objective algorithm for two-dimensional bin packing with rotations and load balancing |
| |
Authors: | Antonio Fernández Consolación Gil Raúl Baños María G. Montoya |
| |
Affiliation: | 1. Dpt. of Informatics, The Agrifood Campus of International Excellence (ceiA3), University of Almería, Carretera de Sacramento s/n, E-04120 Almería, Spain;2. Dpt. of Computer Architecture and Technology, CITIC-UGR (Research Centre on Information and Communications Technology), University of Granada, C/Periodista Daniel Saucedo s/n, E-18071 Granada, Spain |
| |
Abstract: | 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 90° 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. |
| |
Keywords: | Two-dimensional bin packing problem with rotations Load balancing Memetic algorithms Pareto-based multi-objective optimization Parallel processing |
本文献已被 ScienceDirect 等数据库收录! |
|