Paper Titles
Modeling and Simulation of a Externally Pressurized Spherical Gas Bearing
p.182
A Cohesion Metric for Design of Task Based on Activity Relationship Matrix in Product Process
p.187
Study on Free Oscillations of Systems with Even Nonlinearities by Means of the Method of Multiple Scales
p.193
Conceptual Design Method Based on Behavior Re-Creation
p.198
Backtracking Greedy Algorithm for Cutting Stock Problems
p.203
An SVG-Based Interactive Drawing Viewing Solution for Mobile Design or Manufacturing Collaboration
p.208
Web-Based Enterprise Knowledge Management for Product Life-Cycle
p.213
A Web-Based Collaborative Design Advisory System for Micro Product Design Assessment
p.220
Evaluation Model of the Product Design Team under Internet Environment
p.225

Backtracking Greedy Algorithm for Cutting Stock Problems

Article Preview

Abstract:

This paper presents a greedy search placement algorithm which incorporates backtracking for the leather stock cutting problem. In the leather manufacturing industry the efficient cutting of component parts (stencils) form a hide is of prime importance to maintain profitability. Consequently, the development of new approaches for generating cut-plans that minimise material waste and which can handle problem constraints have practical value. The unique feature of the greedy placement algorithm method presented in this paper is that it incorporates backtracking which allows previous placement steps to be retraced in situations where no placement solution can be found. The underlying encoding method is based on the use of the no-fit polygon (NFP) which describes the boundary around a stencil shape such that a second stencil shape can be placed while just touching the first but without overlapping. A material coverage of 64% can be achieved when taking placement constraints into account.

You might also be interested in these eBooks
e-Engineering & Digital Enterprise Technology View Preview

Info:

Periodical:

Applied Mechanics and Materials (Volumes 10-12)

Pages:

203-207

DOI:

https://doi.org/10.4028/www.scientific.net/AMM.10-12.203

Citation:

Cite this paper

Online since:

December 2007

Authors:

Alan J. Crispin, Kai Cheng

Keywords:

Backtracking, Cutting Stock Problem, Greedy Algorithm, No Fit Polygon

Export:

RIS, BibTeX

Price:

Permissions CCC:

Request Permissions

Permissions PLS:

Request Permissions

Сopyright:

© 2008 Trans Tech Publications Ltd. All Rights Reserved

Share:

Citation:

References

[1] J. Heistermann and T. Lengauer: Annals of Operations Research, Vol. 57 (1995), pp.147-173.

Google Scholar

[2] A. J. Crispin, P. Clay, G. E. Taylor and et al: International Journal of Applied Intelligence, Vol. 23 (2005), pp.9-20.

Google Scholar

[3] A. J. Crispin, P. Clay, G. E. Taylor and et al: Journal of Engineering Manufacture, I Mech E Part B, Short Communications in Manufacture and Design, Vol. 217 (2003), pp.1753-1756.

Google Scholar

[4] A. J. Crispin, P. Clay, G. E. Taylor and et al: International Journal for Manufacturing Science and Production, Vol. 5 (2003)No. 1-2, pp.17-21.

Google Scholar

[5] M. Adamowicz and A. Albano: Computer-Aided Design, Vol. 8 (1976)No. 1, pp.27-33.

Google Scholar

[6] E. Burke and G. Kendall: Proc. 26th International Conference on Computers and Industrial Engineering, Melbourne, Australia, (1999), pp.286-291.

Google Scholar

[7] J. A. Bennell, K. A. Dowsland and W. B. Downland: Computers and Operations Research, Vol. 28 (2000), pp.271-287.

Google Scholar