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

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. [1] Garey, M. R., and Johnson, D. S., Computers and intractability: A guide to the theory of NP-completeness. W.H. Freeman, (1979).
2. [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. [3] Stawowy, A., Evolutionary based heuristic for bin packing problem. Computers and Industrial Engineering, 55, 465–474, (2008).
4. [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. [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. [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. [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. [8] Cantu-Paz, E., Efficient and accurate parallel genetic algorithms. Kluwer Academic Publishers, (2000).

9. [9] Martello, S., and Toth, P., Knapsack Problems. Wiley, (1990).
10. [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. [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. [12] Falkenauer, E., A new representation and operators for GAs applied togrouping problems. Evolutionary Computation, 2, 2, 123–144, (1994).
13. [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. [14] Falkenauer, E., A hybrid grouping genetic algorithm for bin packing. Journal of Heuristics, 2, 1, 5–30, (1996).
15. [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. [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).