Robust hyper-heuristic algorithms for the offline oriented/non-oriented 2D bin packing problems


Beyaz M., Dokeroglu T., COŞAR A.

APPLIED SOFT COMPUTING, cilt.36, ss.236-245, 2015 (SCI-Expanded) identifier identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 36
  • Basım Tarihi: 2015
  • Doi Numarası: 10.1016/j.asoc.2015.06.063
  • Dergi Adı: APPLIED SOFT COMPUTING
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Sayfa Sayıları: ss.236-245
  • Anahtar Kelimeler: 2D bin packing, Hyper-heuristic, Evolutionary, Genetic, Memetic, GENETIC ALGORITHM, OPTIMIZATION, DESIGN, FRAMEWORK
  • Orta Doğu Teknik Üniversitesi Adresli: Evet

Özet

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 algorithms are some of the state-of-the-art methods successfully applied to this important problem. In this study, we propose a set of novel hyper-heuristic algorithms that select/combine the state-of-the-art heuristics and local search techniques for minimizing the number of 2D bins. The proposed algorithms introduce new crossover and mutation operators for the selection of the heuristics. Through the results of exhaustive experiments on a set of offline 2DBPP benchmark problem instances, we conclude that the proposed algorithms are robust with their ability to obtain high percentage of the optimal solutions. (C) 2015 Elsevier B.V. All rights reserved.