Computational & Technology Resources
an online resource for computational,
engineering & technology publications
PROCEEDINGS OF THE SECOND INTERNATIONAL CONFERENCE ON PARALLEL, DISTRIBUTED, GRID AND CLOUD COMPUTING FOR ENGINEERING
Edited by: P. Iványi and B.H.V. Topping
Parallel Memetic Algorithms for Multi-Objective Bin-Packing Problems
A. Fernández, C. Gil, A.L. Márquez, R. Baños, M.G. Montoya and M. Parra
Department of Computer Architecture and Electronics, University of Almería, Spain
A. Fernández, C. Gil, A.L. Márquez, R. Baños, M.G. Montoya, M. Parra, "Parallel Memetic Algorithms for Multi-Objective Bin-Packing Problems", in P. Iványi, B.H.V. Topping, (Editors), "Proceedings of the Second International Conference on Parallel, Distributed, Grid and Cloud Computing for Engineering", Civil-Comp Press, Stirlingshire, UK, Paper 47, 2011. doi:10.4203/ccp.95.47
Keywords: parallel computing, island-based model, two-dimensional bin-packing problem, memetic algorithms.
Most papers dealing with the 2D-BPP try to solve single-objective formulations, where the aim is to minimize the number of bins needed to pack all the pieces. The high complexity of all the multi-dimensional bin-packing problems involves that large instances need to be solved by robust computational optimization techniques, including meta-heuristic approaches such as memetic algorithms.
Recently, other authors have proposed to include other objectives to optimize. For instance, Liu and Tan  solved a multi-objective two-dimensional bin-packing problem (MO-2DBPP) which considers a second objective based on minimizing the imbalance of the bins according to a centre of gravity. Load balancing has many applications, including container loading, tractor trailer trucks, pallet loading and cargo airplanes.
The use of parallel computing is an interesting way of improving the performance of the sequential methods in computationally expensive problems. This paper presents a parallel memetic algorithm, named PMOMA-2DBPP, to solve the MO-2DBPP with rotations. The sequential version of the algorithm applies several different mutation, crossover and local search operators, which are based on adding or removing pieces to or from a bin with the aim of reducing the number of used bins. The selection of agents is done by applying tournaments among agents using Pareto-dominance relations. The task related to verifying that the pieces do not overlap each other is computationally expensive. The parallel implementation, uses the well-known island model, which consists of dividing the population into several sub-populations (islands) which evolves separately on different processors, while occasionally islands exchange some agents.
purchase the full-text of this paper (price £20)