Heuristics for the score-constrained strip-packing problem

Hawa, Asyl L., Lewis, Rhyd ORCID: https://orcid.org/0000-0003-1046-811X and Thompson, Jonathan M. 2018. Heuristics for the score-constrained strip-packing problem. Presented at: COCOA 2018: International Conference on Combinatorial Optimization and Applications, Atlanta, GA, USA, 15-17 December 2018. Published in: Kim, Donghyun, Uma, R. N. and Zelikovsky, Alexander eds. Combinatorial Optimization and Applications: 12th International Conference, COCOA 2018, Atlanta, GA, USA, December 15-17, 2018, Proceedings. Lecture Notes in Computer Science , vol.11346 Springer Verlag, p. 449. 10.1007/978-3-030-04651-4_30

Preview

PDF - Accepted Post-Print Version Download (309kB) | Preview

Abstract

This paper investigates the Score-Constrained Strip-Packing Problem (SCSPP), a combinatorial optimisation problem that generalises the one-dimensional bin-packing problem. In the construction of cardboard boxes, rectangular items are packed onto strips to be scored by knives prior to being folded. The order and orientation of the items on the strips determine whether the knives are able to score the items correctly. Initially, we detail an exact polynomial-time algorithm for finding a feasible alignment of items on a single strip. We then integrate this algorithm with a packing heuristic to address the multi-strip problem and compare with two other greedy heuristics, discussing the circumstances in which each method is superior.

Item Type:	Conference or Workshop Item (Paper)
Date Type:	Publication
Status:	Published
Schools:	Mathematics
Publisher:	Springer Verlag
ISBN:	9783030046507
Date of First Compliant Deposit:	13 December 2018
Date of Acceptance:	20 September 2018
Last Modified:	24 Oct 2022 08:23
URI:	https://orca.cardiff.ac.uk/id/eprint/117626

Citation Data

Cited 3 times in Scopus. View in Scopus. Powered By Scopus® Data

Actions (repository staff only)

Edit Item