Bir boyutlu kutulama probleminin eniyilenmesi için hiper-sezgisel paralel bir algoritma

Year 2017, Volume: 19 Issue: 1, 1 - 11, 08.06.2017

Tansel Dökeroğlu

https://doi.org/10.25092/baunfbed.319992

Abstract

Bir boyutlu kutulama problemi (1BKP), endüstri mühendisliğinin üzerinde
en çok çalışılan NP-Zor kombinatoriyal problemlerinden bir tanesidir. Büyük
sayıda (elliden fazla) parça içeren problem kümeleri için en iyi çözümün
bulunması klasik kaba kuvvet algoritmaları ile yüz yıllarca sürebilmektedir. Bu
yüzden (yaklaşık)-optimal çözümleri ile eniyilemeyi tam olarak ya da düşük
performans kayıpları ile kısa sürelerde bulabilen sezgisel algoritmalar
sıklıkla kullanılmaktadır. Bu çalışma ile birlikte, Gruplama Genetik
Algoritmalarında (GGA) kullanılan sezgisel kutulama tekniklerinden sadece bir
tanesini kullanan klasik yaklaşımlar yerine, aynı anda birçok sezgisel kutulama
tekniğini kullanan hiper-sezgisel paralel bir algoritma (HPGG-1BKP)
geliştirildi. En Uygun Boşluğu Doldur (EUBD), İlk Bulduğun Boşluğu Doldur
(İBBD) ve En Küçük Boşluğu Bırakarak Doldur (EKBBD) sezgisel kutu doldurma
algoritmaları bu algoritmada aynı anda paralel olarak kullanıldı. 1228 bençmark
problemi üzerinde yapılan deneyler sonucunda %88.1 başarı ile 1070 optimal
sonuç elde edildi. Geri kalan problemler için de sadece bir kutu daha fazla
kullanan çözümler üretilerek sonuçlar eniyilendi. Önerilen algoritma Falkenauer
GGA ile karşılaştırıldığında %9’a varan iyileşmeler elde edildi.

Keywords

Genetik, bir boyutlu kutulama, paralel, hiper-sezgisel

A parallel hyper-heuristic algorithm for the optimization of one-dimensional bin packing problem

Abstract

One-Dimensional Bin
Packing Problem (1DBPP) is one of the most well-known NP-Hard problems of
industrial engineering. The execution time of a brute force approach algorithm
for finding the optimal solution for its problem instances with several items
(more than 50) can spend more than hundreds of years. Therefore, heuristic
algorithms that can find (near)-optimal solutions are preferred with their
reasonable optimization times. With this study, we propose a novel parallel
hyper-heuristic Grouping Genetic Algorithm (HHPGGA-1DBPP) that uses several
heuristics concurrently, whereas classical Grouping Genetic Algorithms (GGA)
use only a single one during the optimization. The solutions of the proposed
algorithm outperform the classical ones’. Best Fit Decreasing (BFD), First Fit
Decreasing (FFD), and Minimum Bin Slack (MBS) are the bin-oriented heuristics
used in the proposed algorithm. With the experiments carried out on 1,228
problem instances, 1,070 of the problems (88.1%) are solved optimally. The remaining
problems are optimized by producing only a single extra bin. These experimental
results show that the proposed algorithm can outperform Falkenauer GGA. The
obtained results are improved up to 9%.

Keywords

Genetic, one-dimensional bin packing, parallel, hyper-heuristic

References

• [1] Garey, M. R., and Johnson, D. S., Computers and intractability: A guide to the theory of NP-completeness. W.H. Freeman, (1979).
• [2] Dokeroglu, T., and Cosar, A., Optimization of one-dimensional bin packing problem with island parallel grouping genetic algorithms. Computers and Industrial Engineering, 75, 176-186, (2014).
• [3] Stawowy, A., Evolutionary based heuristic for bin packing problem. Computers and Industrial Engineering, 55, 465–474, (2008).
• [4] Burke , E.K., McCollum, B., Meisels, A., Petrovic, S., and Qu, R., A graph-based hyper-heuristic for educational timetabling problems, European Journal of Opertions Research 176, 1, 177–192, (2007).
• [5] Burke, E.K., Hyde, M., Kendall, G., Ochoa, G., Ozcan, E., and Woodward, J.R., A classification of hyper-heuristic approaches, in: Handbook of Metaheuristics, Springer US, 449–468, (2010).
• [6] Beyaz, M., Dokeroglu, T., and Cosar, A. Robust hyper-heuristic algorithms for the offline oriented/non-oriented 2D bin packing problems. Applied Soft Computing, 36, 236-245, (2015).
• [7] Wolpert, D.H., and Macready, W.G., No free lunch theorems for optimization. Evolutionary Computation, IEEE Transactions on, 1, 1, 67-82, (1997).
• [8] Cantu-Paz, E., Efficient and accurate parallel genetic algorithms. Kluwer Academic Publishers, (2000).
• [9] Martello, S., and Toth, P., Knapsack Problems. Wiley, (1990).
• [10] Gupta, J.N.D., and Ho, J.C., A new heuristic algorithm for the one-dimensional bin packing problem. Production Planning and Control 10, 6, 598-603, (1999).
• [11] Fleszar, K., and Charalambous, C., Average-weight-controlled bin-oriented heuristics for the one-dimensional bin-packing problem. European Journal of Operations Research, 210, 176–184, (2011).
• [12] Falkenauer, E., A new representation and operators for GAs applied togrouping problems. Evolutionary Computation, 2, 2, 123–144, (1994).
• [13] Bozejko, W., Uchronski, M., and Wodecki, M., Parallel hybrid metaheuristics for the flexible job shop problem. Computers & Industrial Engineering, 59, 2, 323–333, (2010).
• [14] Falkenauer, E., A hybrid grouping genetic algorithm for bin packing. Journal of Heuristics, 2, 1, 5–30, (1996).
• [15] Scholl, A., Klein, R., and Jurgens, C., BISON: A fast hybrid procedure for exactly solving the one-dimensional bin packing problem. Computers and Operations Research, 24, 7, 627–645, (1997).
• [16] Belov, G., Scheithauer, G., and Mukhacheva, E. A., One-dimensional heuristics adapted for two-dimensional rectangular strip packing. Journal of the Operational Research Society, 59, 6, 823–832, (2007).