Hybrid heuristic algorithms for the multi objective load balancing of 2D bin packing problems

Date

2015-09-23

Author

Muhammet, Beyaz
Dökeroğlu, Tansel
Coşar, Ahmet

Metadata

Show full item record

Item Usage Stats

125
views

0
downloads

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 the state-of-the-art metaheuristics and local search techniques for minimizing the number of bins while also maintaining the load balance. We analyze the optimization time and the resulting solution quality of the proposed algorithms on an offline 2DBPP benchmark problem set with 500 instances. Using these results of exhaustive experiments, we conclude that the proposed hybrid algorithms are robust with their ability to obtain a high percentage of the optimal solutions.

Subject Keywords

Genetic algorithm, Load balance, Memetic algorithm, Multiobjective genetic algorithm, Swap mutation

URI

http://link.springer.com/book/10.1007/978-3-319-22635-4
https://hdl.handle.net/11511/78237

Conference Name

30th International Symposium on Computer and Information Sciences, (23 - 25 Eylül 2015)

Collections

Graduate School of Natural and Applied Sciences, Conference / Seminar

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...
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,...
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...
Minimum-weight spanning tree algorithms - A survey and empirical study Bazlamaçcı, Cüneyt Fehmi (2001-07-01) The minimum-weight spanning tree problem is one of the most typical and well-known problems of combinatorial optimisation. Efficient solution techniques had been known for many years. However, in the last two decades asymptotically faster algorithms have been invented. Each new algorithm brought the time bound one step closer to linearity and finally Karger, Klein and Tarjan proposed the only known expected linear-time method. Modern algorithms make use of more advanced data structures and appear to be more...
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...

Citation Formats

B. Muhammet, T. Dökeroğlu, and A. Coşar, “Hybrid heuristic algorithms for the multi objective load balancing of 2D bin packing problems,” presented at the 30th International Symposium on Computer and Information Sciences, (23 - 25 Eylül 2015), London, UK, 2015, Accessed: 00, 2021. [Online]. Available: http://link.springer.com/book/10.1007/978-3-319-22635-4.