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

2014-09-01
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.
COMPUTERS & INDUSTRIAL ENGINEERING

Suggestions

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 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...
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...
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...
Effective optimization with weighted automata on decomposable trees
Ravve, E. V.; Volkovich, Z.; Weber, Gerhard Wilhelm (Informa UK Limited, 2014-01-02)
In this paper, we consider quantitative optimization problems on decomposable discrete systems. We restrict ourselves to labeled trees as the description of the systems and we use weighted automata on them as our computational model. We introduce a new kind of labeled decomposable trees, sum-like weighted labeled trees, and propose a method, which allows us to reduce the solution of an optimization problem, defined in a fragment of Weighted Monadic Second Order Logic, on such a tree to the solution of effec...
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.