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

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...
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...
On generalized semi-infinite programming - Discussion
Weber, Gerhard Wilhelm; Tezel, A. (2006-06-01)
This paper surveys some basic properties of the class of generalized semi-infinite programming problems (GSIP) where the infinite index set of inequality constraints depends on the state variables and all emerging functions are assumed to be continuously differentiable. There exists a wide range of applications which can be modelled as a (GSIP). The paper discusses extensions of the Mangasarian-Fromovitz, Kuhn-Tucker and Abadie constraint qualification to (GSIP) and presents related first order optimality c...
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...
Robust hyper-heuristic algorithms for the offline oriented/non-oriented 2D bin packing problems
Beyaz, Muhammed; Dokeroglu, Tansel; Coşar, Ahmet (2015-11-01)
The offline 2D bin packing problem (2DBPP) is an NP-hard combinatorial optimization problem in which objects with various width and length sizes are packed into minimized number of 2D bins. Various versions of this well-known industrial engineering problem can be faced frequently. Several heuristics have been proposed for the solution of 2DBPP but it has not been possible to find the exact solutions for large problem instances. Next fit, first fit, best fit, unified tabu search, genetic and memetic algorith...
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.