Backtracking Greedy Algorithm for Cutting Stock Problems


Article Preview

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.



Edited by:

Kai Cheng, Yingxue Yao and Liang Zhou




A. J. Crispin and K. Cheng, "Backtracking Greedy Algorithm for Cutting Stock Problems", Applied Mechanics and Materials, Vols. 10-12, pp. 203-207, 2008

Online since:

December 2007




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

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

[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.

[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.

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

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

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