Content area
In this work, the Bin Packing combinatorial optimization problem is studied from the practical side. The focus is on the Falkenauer T benchmark class, which is a collection of 80 problem instances that are considered hard to handle algorithmically. Contrary to this widely accepted view, we show that the instances of this benchmark class can be solved relatively easily, without applying any sophisticated methods like metaheuristics. A new algorithm is proposed, which can operate in two modes: either using backtrack or local search to find optimal packing. In theory, both operating modes are guaranteed to find a solution. Computational results show that all instances of the Falkenauer T benchmark class can be solved in a total of 1.18 s and 2.39 s with the two operating modes alone, or 0.2 s when running in parallel.
Details
; Éles, András 2
; Goswami, Angshuman Robin 1
; Szalkai, István 1 ; Tuza, Zsolt 3
1 Mathematical Department, Faculty of Information Technology, University of Pannonia, 8200 Veszprém, Hungary;
2 Department of Computer Science and Systems Technology, Faculty of Information Technology, University of Pannonia, 8200 Veszprém, Hungary;
3 Department of Computer Science and Systems Technology, Faculty of Information Technology, University of Pannonia, 8200 Veszprém, Hungary;