Aggregated state dynamic programming for a multiobjective two-dimensional bin packing problem

Ya Liu, Chengbin Chu, Y Yu

Research output: Contribution to journalArticleAcademicpeer-review

4 Citations (Scopus)

Abstract

This paper studies a real-life multi-objective two-dimensional single-bin-size bin-packing problem arising in industry. A packing pattern is defined by one bin, a set of items packed into the bin and the packing positions of these items. A number of bins can be placed with the same packing pattern. The objective is not only to minimise the number of bins used, as in traditional bin-packing problems, but also to minimise the number of packing patterns. Based on our previous study of a heuristic stemming from dynamic programming by aggregating states to avoid the exponential increase in the number of states, we further develop this heuristic by decomposing a pattern with a number of bins at each step. Computational results show that this heuristic provides satisfactory results with a gap generally less than 20% with respect to the optimum
Original languageEnglish
Pages (from-to)4316-4325
Number of pages10
JournalInternational Journal of Production Research
Volume50
Issue number15
DOIs
Publication statusPublished - 17 Oct 2011

Fingerprint

Dive into the research topics of 'Aggregated state dynamic programming for a multiobjective two-dimensional bin packing problem'. Together they form a unique fingerprint.

Cite this