Aggregated state dynamic programming for a multiobjective two-dimensional bin packing problem
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.
|Keywords||OR, cutting stock problems, dynamic programming|
|Persistent URL||dx.doi.org/10.1080/00207543.2011.622309, hdl.handle.net/1765/37819|
Liu, Y., Chu, C., & Yu, Y.. (2012). Aggregated state dynamic programming for a multiobjective two-dimensional bin packing problem. International Journal of Production Research, 50(15), 4316–4325. doi:10.1080/00207543.2011.622309