Optimization of one-dimensional Bin Packing Problem with island parallel grouping genetic algorithms
Computers and Industrial Engineering, cilt.75, sa.1, ss.176-186, 2014 (SCI-Expanded, Scopus)
- Yayın Türü: Makale / Tam Makale
- Cilt numarası: 75 Sayı: 1
- Basım Tarihi: 2014
- Doi Numarası: 10.1016/j.cie.2014.06.002
- Dergi Adı: Computers and Industrial Engineering
- Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus
- Sayfa Sayıları: ss.176-186
- Anahtar Kelimeler: Grouping genetic algorithms, Hybrid-heuristics, One-dimensional bin packing, Parallel computation
- TED Üniversitesi Adresli: Hayır
Özet
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, and bin-oriented heuristics to obtain solutions for large scale one-dimensional BPP instances. A total number of 1318 benchmark problems are examined with the proposed algorithms and it is shown that optimal solutions for 88.5% of these instances can be obtained with practical optimization times while solving the rest of the problems with no more than one extra bin. When the results are compared with the existing state-of-the-art heuristics, the developed parallel hybrid grouping genetic algorithms can be considered as one of the best one-dimensional BPP algorithms in terms of computation time and solution quality. © 2014 Elsevier Ltd. All rights reserved.