Optimization of one-dimensional Bin Packing Problem with island parallel grouping genetic algorithms

Date

2014-09-01

Author

Dokeroglu, Tansel
Coşar, Ahmet

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

172
views

0
downloads

The well-known one-dimensional Bin Packing Problem (BPP) of whose variants arise in many real life situations is a challenging NP-Hard combinatorial optimization problem. Metaheuristics are widely used optimization tools to find (near-) optimal solutions for solving large problem instances of BPP in reasonable running times. With this study, we propose a set of robust and scalable hybrid parallel algorithms that take advantage of parallel computation techniques, evolutionary grouping genetic metaheuristics, and bin-oriented heuristics to obtain solutions for large scale one-dimensional BPP instances. A total number of 1318 benchmark problems are examined with the proposed algorithms and it is shown that optimal solutions for 88.5% of these instances can be obtained with practical optimization times while solving the rest of the problems with no more than one extra bin. When the results are compared with the existing state-of-the-art heuristics, the developed parallel hybrid grouping genetic algorithms can be considered as one of the best one-dimensional BPP algorithms in terms of computation time and solution quality.

Subject Keywords

One-dimensional bin packing, Grouping genetic algorithms, Parallel computation, Hybrid-heuristics

URI

https://hdl.handle.net/11511/32327

Journal

COMPUTERS & INDUSTRIAL ENGINEERING

DOI

https://doi.org/10.1016/j.cie.2014.06.002

Collections

Graduate School of Natural and Applied Sciences, Article

Suggestions

OpenMETU
Core

Hybrid heuristic algorithms for the multi objective load balancing of 2D bin packing problems Muhammet, Beyaz; Dökeroğlu, Tansel; Coşar, Ahmet (null; 2015-09-23) 2D Bin packing problem (2DBPP) is an NP-hard combinatorial optimization problem. Multiobjective versions of this well-known industrial engineering problem can occur frequently in real world application. Recently, Hybrid Evolutionary Algorithms have appear as a new area of research with their ability to combine alternative heuristics and local search mechanisms together for higher quality solutions. In this study, we propose a set of novel multiobjective hybrid genetic and memetic algorithms that make use of...
Optimization of the array geometry for direction finding Özaydın, Seval; Koç, Seyit Sencer; Tanık, Yalçın; Department of Electrical and Electronics Engineering (2003) In this thesis, optimization of the geometry of non-uniform arrays for direction finding yielding unambiguous results is studied. A measure of similarity between the array response vectors is defined. In this measure, the effects of antenna array geometry, source placements and antenna gains are included as variable parameters. Then, assuming that the antenna gains are known and constant, constraints on the similarity function are developed and described to result in unambiguous configurations and maximum r...
Forward Kinematics of the 6-6 general Parallel Manipulator Using Real Coded Genetic Algorithms Rolland, Luc; Chandra, Rohitash (2009-07-17) This article examines an optimization method to solve the forward kinematics problem (FKP) applied to parallel manipulators. Based on Genetic Algorithms (GA), a non-linear equation system solving problem is converted into an optimization one. The majority of truly parallel manipulators can be modeled by the 6-6 which is an hexapod constituted by a fixed base and a mobile platform attached to six kinematics chains with linear (prismatic) actuators located between two ball joints. Parallel manipulator kinemat...
Hybrid metaheuristic algorithms for single and multi-objective 2d bin packing problem Beyaz, Muhammed; Coşar, Ahmet; Dökeroğlu, Tansel; Department of Computer Engineering (2015) 2D Bin packing problem (2DBPP) is an NP-hard combinatorial optimization problem. Objects with di erent width and length sizes are packed in order to minimize the number of unit-capacity bins according to an objective function. Single or multiobjective versions of this well-known industrial engineering problem can be faced frequently in real life situations. There have been several heuristics proposed for the solution of 2DBPP until now where it is not possible to find the exact solutions for large problem i...
Efficient parallelization of multilevel fast multipole algorithm Ergül, Özgür Salih (null; 2006-11-10) We report our efforts for the solution of large electromagnetics problems accurately and efficiently with the parallel multilevel fast multipole algorithm. We carefully investigate different stages of the parallelization and identify the bottlenecks to develop new strategies. The required modifications are implemented in order to increase the efficiency of the solutions of scattering problems involving various geometries.

Citation Formats

T. Dokeroglu and A. Coşar, “Optimization of one-dimensional Bin Packing Problem with island parallel grouping genetic algorithms,” COMPUTERS & INDUSTRIAL ENGINEERING, pp. 176–186, 2014, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/32327.