An investigation into two bin packing problems with ordering and orientation implications

Lewis, Rhyd ORCID: https://orcid.org/0000-0003-1046-811X, Song, Xiang ORCID: https://orcid.org/0000-0003-0235-3734, Dowsland, Kathryn Anne and Thompson, Jonathan Mark 2011. An investigation into two bin packing problems with ordering and orientation implications. European Journal of Operational Research 213 (1) , pp. 52-65. 10.1016/j.ejor.2011.03.016

Preview

PDF - Submitted Pre-Print Version Download (941kB) | Preview

Abstract

This paper considers variants of the one-dimensional bin packing (and stock cutting) problem in which both the ordering and orientation of items in a container influences the validity and quality of a solution. Two new real-world problems of this type are introduced, the first that involves the creation of wooden trapezoidal-shaped trusses for use in the roofing industry, the second that requires the cutting and scoring of rectangular pieces of cardboard in the construction of boxes. To tackle these problems, two variants of a local search-based approximation algorithm are proposed, the first that attempts to determine item ordering and orientation via simple heuristics, the second that employs more accurate but costly branch-and-bound procedures. We investigate the inevitable trade-off between speed and accuracy that occurs with these variants and highlight the circumstances under which each scheme is advantageous.

Item Type:	Article
Date Type:	Publication
Status:	Published
Schools:	Mathematics
Subjects:	Q Science > QA Mathematics Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Uncontrolled Keywords:	Packing; Cutting; Grouping problems; Local search; Heuristics
Publisher:	Elsevier
ISSN:	0377-2217
Last Modified:	08 Jan 2025 11:49
URI:	https://orca.cardiff.ac.uk/id/eprint/11082

Citation Data

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

Actions (repository staff only)

Edit Item