A heuristic for variable size multiobjective two-dimensional bin packing

Abstract

This paper focuses on a real life variable size multiobjective two-dimensional bin packing problem arising in a manufacturing company. It consists of placing a given set of items into bins of different sizes (called variable size bins) to minimise not only the wasted space of bins but also the number of packing patterns generated. Although an existing heuristic (called HIB), initially developed for problems with identical bins, is able to solve this problem after slight adaptations (we call this slightly adapted version as MAHIB), it requires prohibitive amounts of computation time for large-sized instances. We thus develop a heuristic called HVSB. HVSB explores different lists of items. For each list, an approach based on dynamic programming (called ASDP) is used to obtain a feasible packing. Computational results show that HVSB is efficient. The results obtained with HVSB are very close to the so-called ‘quasi-optimal packing plan’ for large-sized instances with variable size bins. For some instances, the total cost is even less than the ‘quasi-optimal packing plan’. Compared with the above-mentioned HIB and MAHIB, HVSB provides solutions of similar quality both for instances with identical bins and small-sized instances with variable size bins, but with much shorter computation times.

Keywords:

• dynamic programming
• two-dimensional bin packing
• heuristic