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

Dokeroglu, Tansel
Coşar, Ahmet
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.


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.