Cardiff University | Prifysgol Caerdydd ORCA
Online Research @ Cardiff 
WelshClear Cookie - decide language by browser settings

Heuristics for large strip packing problems with guillotine patterns: An empirical study

Mumford, Christine Lesley ORCID: https://orcid.org/0000-0002-4514-0272, Vick, J. and Wang, Pearl Y. 2004. Heuristics for large strip packing problems with guillotine patterns: An empirical study. Metaheuristics: Computer Decision-making 86 , pp. 501-522.

[thumbnail of binpaper4.pdf]
Preview
Text
Download (149kB) | Preview

Abstract

In this paper we undertake an empirical study which examines the effectiveness of eight simple strip packing heuristics on data sets of different sizes with various characteristics and known optima. We restrict this initial study to techniques that produce guillotine patterns (also known as slicing floorplans). Guillotine patterns are important industrially. Our chosen heuristics are simple to code, have very fast execution times, and provide a good starting point for our research. In particular, we examine the performance of the eight heuristics as the problems become larger, and demonstrate the effectiveness of a preprocessing routine that rotates some of the rectangles by 90 degrees before the heuristics are applied. We compare the heuristic results to those obtained using a good genetic algorithm (GA) that also produces guillotine patterns. Our findings suggest that the GA is better on problems of up to about 200 rectangles, but thereafter certain of the heuristics become increasingly effective as the problem size becomes larger, producing better results much more quickly than the GA.

Item Type: Article
Date Type: Publication
Status: Published
Schools: Computer Science & Informatics
Subjects: Q Science > QA Mathematics
Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Q Science > QA Mathematics > QA76 Computer software
Last Modified: 04 May 2023 13:01
URI: https://orca.cardiff.ac.uk/id/eprint/31905

Citation Data

Actions (repository staff only)

Edit Item Edit Item

Downloads

Downloads per month over past year

View more statistics