Show/Hide Menu
Hide/Show Apps
Logout
Türkçe
Türkçe
Search
Search
Login
Login
OpenMETU
OpenMETU
About
About
Open Science Policy
Open Science Policy
Open Access Guideline
Open Access Guideline
Postgraduate Thesis Guideline
Postgraduate Thesis Guideline
Communities & Collections
Communities & Collections
Help
Help
Frequently Asked Questions
Frequently Asked Questions
Guides
Guides
Thesis submission
Thesis submission
MS without thesis term project submission
MS without thesis term project submission
Publication submission with DOI
Publication submission with DOI
Publication submission
Publication submission
Supporting Information
Supporting Information
General Information
General Information
Copyright, Embargo and License
Copyright, Embargo and License
Contact us
Contact us
Hybrid metaheuristic algorithms for single and multi-objective 2d bin packing problem
Download
index.pdf
Date
2015
Author
Beyaz, Muhammed
Metadata
Show full item record
Item Usage Stats
215
views
112
downloads
Cite This
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 instances. Next fit, First Fit, Best Fit, Unified Tabu Search and Genetic Algorithms are some of these algorithms. Recently, Memetic Algorithms have put themselves forward as a new area of research in evolutionary computation with their ability to combine di erent heuristics and local search mechanisms together for higher quality solutions. In this thesis, we propose a set of single and multiobjective memetic and genetic algorithms that make use of the state-of-the-art metaheuristics and local search techniques for the solution of 2DBPP. We analyze the optimization time and the resulting solution quality of the algorithms on a 2DBPP benchmark offline problem set with 500 instances. Through results of exhaustive experiments and with the aid of a novel visual analyzer developed in this study, we conclude that the proposed memetic and hybrid genetic algorithms are robust with their ability to obtain very high percentage of the optimal solutions for the given benchmark problem instances.
Subject Keywords
Genetic algorithms.
,
Heuristic algorithms.
,
Computer algorithms.
,
Combinatorial optimization.
,
Combinatorial packing and covering.
URI
http://etd.lib.metu.edu.tr/upload/12618455/index.pdf
https://hdl.handle.net/11511/24446
Collections
Graduate School of Natural and Applied Sciences, Thesis
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...
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...
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,...
Converging preferred regions in multi-objective combinatorial optimization problems
Lokman, Banu; Köksalan, Murat; Department of Industrial Engineering (2011)
Finding the true nondominated points is typically hard for Multi-objective Combinatorial Optimization (MOCO) problems. Furthermore, it is not practical to generate all of them since the number of nondominated points may grow exponentially as the problem size increases. In this thesis, we develop an exact algorithm to find all nondominated points in a specified region. We combine this exact algorithm with a heuristic algorithm that approximates the possible locations of the nondominated points. Interacting w...
Parallel Approximation, and Integer Programming Reformulation
Patakı, Gabor; Tural, Mustafa Kemal (null; 2008-03-14)
We show that in a knapsack feasibility problem an integral vectorp, which is short, and nearparallel to the constraint vector gives a branching direction with small integer width.We use this result to analyze two computationally efficient reformulation techniques on lowdensity knapsack problems. Both reformulations have a constraint matrix with columns reducedin the sense of Lenstra, Lenstra, and Lov ́asz. We prove an upper bound on the integer widthalong the last variable, which becomes 1,when the density ...
Citation Formats
IEEE
ACM
APA
CHICAGO
MLA
BibTeX
M. Beyaz, “Hybrid metaheuristic algorithms for single and multi-objective 2d bin packing problem,” M.S. - Master of Science, Middle East Technical University, 2015.