Robust hyper-heuristic algorithms for the offline oriented/non-oriented 2D bin packing problems

Date

2015-11-01

Author

Beyaz, Muhammed
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

160
views

0
downloads

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 algorithms are some of the state-of-the-art methods successfully applied to this important problem. In this study, we propose a set of novel hyper-heuristic algorithms that select/combine the state-of-the-art heuristics and local search techniques for minimizing the number of 2D bins. The proposed algorithms introduce new crossover and mutation operators for the selection of the heuristics. Through the results of exhaustive experiments on a set of offline 2DBPP benchmark problem instances, we conclude that the proposed algorithms are robust with their ability to obtain high percentage of the optimal solutions.

Subject Keywords

2D bin packing, Hyper-heuristic, Evolutionary, Genetic, Memetic

URI

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

Journal

APPLIED SOFT COMPUTING

DOI

https://doi.org/10.1016/j.asoc.2015.06.063

Collections

Graduate School of Natural and Applied Sciences, Article

Suggestions

OpenMETU
Core

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...
A Novel Grouping Genetic Algorithm for the One-Dimensional Bin Packing Problem on GPU Ozcan, Sukru Ozer; Dokeroglu, Tansel; Coşar, Ahmet; Yazıcı, Adnan (SPRINGER INT PUBLISHING AG, GEWERBESTRASSE 11, CHAM, CH-6330, SWITZERLAND; 2016-10-28) One-dimensional Bin Packing Problem (1D-BPP) is a challenging NP-Hard combinatorial problem which is used to pack finite number of items into minimum number of bins. Large problem instances of the 1D-BPP cannot be solved exactly due to the intractable nature of the problem. In this study, we propose an efficient Grouping Genetic Algorithm (GGA) by harnessing the power of the Graphics Processing Unit (GPU) using CUDA. The time consuming crossover and mutation processes of the GGA are executed on the GPU by i...
Optimization of one-dimensional Bin Packing Problem with island parallel grouping genetic algorithms Dokeroglu, Tansel; Coşar, Ahmet (2014-09-01) 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,...
An efficient algorithm for the capacitated single item dynamic lot size problem Kırca, Ö. (Elsevier BV, 1990-3) A dynamic programming based algorithm is developed for the single item lot size problem with concave costs and arbitrary capacities. By making use of the extreme point properties of the problem, first the set of all feasible cumulative production levels that may occur in an optimal solution is generated. In the second stage, a dynamic programming procedure is carried out over this set. The worst case computational effort is equal to that of the standard dynamic programming approach but extensive computation...

Citation Formats

M. Beyaz, T. Dokeroglu, and A. Coşar, “Robust hyper-heuristic algorithms for the offline oriented/non-oriented 2D bin packing problems,” APPLIED SOFT COMPUTING, pp. 236–245, 2015, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/31925.