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 [4] 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.

1

M.R. Garey, D.S. Johnson, "Computers and intractability: a guide to the theory of NP-completeness", W.H. Freeman & Company, San Francisco CA, 1979.

2

M. Sathe, O. Schenk, H. Burkhart, "Tackling Many-Constraint One-Dimensional Bin Packing with Clustering Genetic Algorithms", Sixth ESICUP Meeting, Valencia, Spain, 25-27, 2009.

3

A. Lodi, S. Martello, D. Vigo, "Recent advances on two-dimensional bin-packing problems", Discrete Applied Mathematics, 123, 379-96, 2002. doi:10.1016/S0166-218X(01)00347-X

4

D. Liu, K. Tan, C. Huang, W. Ho, "On solving multiobjective bin packing problems using evolutionary particle swarm optimization", European Journal of Operational Research, 190(2), 357-382, 2008. doi:10.1016/j.ejor.2007.06.032

purchase the full-text of this paper (price £20)

go to the previous paper
go to the next paper
return to the table of contents
return to the book description
purchase this book (price £85 +P&P)