×

The irregular cutting-stock problem – a new procedure for deriving the no-fit polygon. (English) Zbl 1048.90510

Comput. Oper. Res. 28, No. 3, 271-287 (2001); erratum ibid. 32, No. 5, 1353 (2005).
Summary: The nofit polygon is a powerful and effective tool for handling the geometry required for a range of solution approaches to two-dimensional irregular cutting-stock problems. However, unless all the pieces are convex, it is widely perceived as being difficult to implement, and its use has therefore been somewhat limited. The primary purpose of this paper is to correct this misconception by introducing a new method of calculating the nofit polygon. Although it is based on previous approaches which use the mathematical concept of Minkowski sums, this new method can be stated as a set of simple rules that can be implemented without an indepth understanding of the underlying mathematics. The result is an approach that is both very general and easy to use.

MSC:

90B80 Discrete location and assignment
90C08 Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.)

Software:

TOPOS
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Adamowicz, M.; Albano, A., Nesting two dimensional shapes in rectangular modules, Computer Aided Design, 8, 1, 27-33 (1976)
[2] Art RC. An approach to the two dimensional irregular cutting stock problem. IBM Cambridge Scientific Centre, Report 36-Y08, 1966.; Art RC. An approach to the two dimensional irregular cutting stock problem. IBM Cambridge Scientific Centre, Report 36-Y08, 1966.
[3] Bennell JA. Incorporating problem specific knowledge into a local search framework for the irregular shape packing problem. Ph.D. thesis, University of Wales, Swansea, 1998.; Bennell JA. Incorporating problem specific knowledge into a local search framework for the irregular shape packing problem. Ph.D. thesis, University of Wales, Swansea, 1998.
[4] Bennell, J. A.; Dowsland, K. A., A tabu thresholding implementation for the irregular stock cutting problem, International Journal of Production Research, 37, 18, 4259-4275 (1999) · Zbl 0949.90606
[5] Cuninghame-Green R. Geometry, shoemaking and the milk tray problem. New Scientist 12 August 1989; 1677 :50-3.; Cuninghame-Green R. Geometry, shoemaking and the milk tray problem. New Scientist 12 August 1989; 1677 :50-3.
[6] Dowsland, K. A.; Dowsland, W. B.; Bennell, J. A., Jostling for position: local improvement for irregular cutting patterns, Journal of the Operational Research Society, 49, 6, 647-658 (1998) · Zbl 1131.90440
[7] Dowsland, K. A.; Dowsland, W. B., Solution approaches to irregular nesting problems, European Journal of Operational Research, 84, 506-521 (1995) · Zbl 0918.90116
[8] Ghosh, P. K., A unified computational framework for minkowski operations, Computers and Graphics, 17, 4, 357-378 (1993)
[9] Ghosh, P. K., An algebra of polygons through the notion of negative shapes, CVGIP: Image Understanding, 54, 1, 119-144 (1991) · Zbl 0774.68118
[10] Grünbaum, B., Convex polytopes (1967), Interscience: Interscience London · Zbl 0163.16603
[11] Heckmann, R.; Lengauer, T., A simulated annealing approach to the nesting problem in the textile manufacturing industry, Annals of Operational Research, 57, 103-133 (1995) · Zbl 0831.90062
[12] Konopasek M. Mathematical treatment of some apparel marking and cutting problems. US Department of Commerce Report, 99-26-90857-10, 1981.; Konopasek M. Mathematical treatment of some apparel marking and cutting problems. US Department of Commerce Report, 99-26-90857-10, 1981.
[13] Li, Z.; Milenkovic, V., Compaction and separation algorithms for non-convex polygons and their application, European Journal of Operations Research, 84, 539-561 (1995) · Zbl 1127.90403
[14] Mahadevan A. Optimisation in computer aided pattern packing. Ph.D. thesis, North Carolina State University, 1984.; Mahadevan A. Optimisation in computer aided pattern packing. Ph.D. thesis, North Carolina State University, 1984.
[15] Milenkovic V, Daniels K, Li Z. Placement and compaction of non convex polygons for clothing manufacture. Fourth Canadian Conference on Computational Geometry, St John’s, Newfoundland, 1992.; Milenkovic V, Daniels K, Li Z. Placement and compaction of non convex polygons for clothing manufacture. Fourth Canadian Conference on Computational Geometry, St John’s, Newfoundland, 1992.
[16] Oliveira JF, Gomes AM, Ferreira JS. A new constructive algorithm for nesting problems. Conference Paper, IFORS, Vancouver, BC, Canada, 1996.; Oliveira JF, Gomes AM, Ferreira JS. A new constructive algorithm for nesting problems. Conference Paper, IFORS, Vancouver, BC, Canada, 1996.
[17] Ramkumar GD. An algorithm to compute the minkowski sum outer-face of two simple polygons. Proceedings of the 12th Annual Symposium on Computational Geometry FCRC 96, 1996.; Ramkumar GD. An algorithm to compute the minkowski sum outer-face of two simple polygons. Proceedings of the 12th Annual Symposium on Computational Geometry FCRC 96, 1996.
[18] Special interest group on cutting and packing (SICUP), http://prodlog.wiwi.uni-halle.de/sicup/.; Special interest group on cutting and packing (SICUP), http://prodlog.wiwi.uni-halle.de/sicup/.
[19] Stoyan YG, Ponomarenko LD. Minkowski sum and hodograph of the dense placement vector function. Reports of the SSR Academy of Science, SER.A 10, 1977.; Stoyan YG, Ponomarenko LD. Minkowski sum and hodograph of the dense placement vector function. Reports of the SSR Academy of Science, SER.A 10, 1977.
[20] Theodoracatos, V. E.; Grimsley, J. L., The optimal packing of arbitrarily-shaped polygons using simulated annealing and polynomial-time cooling schedules, Computer Methods in Applied Mechanics and Engineering, 125, 53-70 (1995) · Zbl 0945.90012
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.