Advanced Search

Query:

Fill in the form and click »Search«...

Format:

Display: entries per page entries

Zbl 1167.90623
Burke, Edmund; Hellier, Robert; Kendall, Graham; Whitwell, Glenn
A new bottom-left-fill heuristic algorithm for the two-dimensional irregular packing problem. (English)
[J] Oper. Res. 54, No. 3, 587-601 (2006). ISSN 0030-364X

Summary: This paper presents a new heuristic algorithm for the two-dimensional irregular stock-cutting problem, which generates significantly better results than the previous state of the art on a wide range of established benchmark problems. The developed algorithm is able to pack shapes with a traditional line representation, and it can also pack shapes that incorporate circular arcs and holes. This in itself represents a significant improvement upon the state of the art. By utilising hill climbing and tabu local search methods, the proposed technique produces 25 new best solutions for 26 previously reported benchmark problems drawn from over 20 years of cutting and packing research. These solutions are obtained using reasonable time frames, the majority of problems being solved within five minutes. In addition to this, we also present 10 new benchmark problems, which involve both circular arcs and holes. These are provided because of a shortage of realistic industrial style benchmark problems within the literature and to encourage further research and greater comparison between this and future methods.

MSC 2000:: *90C27 Combinatorial programming
68W99 None of the above, but in this section
90B35 Scheduling theory
90B80 Discrete location and assignment

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering Article Journal Journal

	Scientific prize winners of the ICM 2010
	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.

Advanced Search

Zentralblatt MATH Berlin [Germany]