Abstract
We consider an industrial cutting problem in textile manufacturing and report on heuristics for computing cutting images and lower bounds on waste for this problem. For the upper bounds we use greedy strategies based on hodographs and global optimization based on simulated annealing. For the lower bounds we use branch-and-bound methods for computing optimal solutions of placement subproblems that determine the performance of the overall subproblem. The upper bounds are computed in less than an hour on a common-day workstation and are competitive in quality with results obtained by human nesters. The lower bounds take a few hours to compute and are within 0.4% of the upper bound for certain types of clothing (e.g., for pants).
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
C. Amaral, J. Bernardo, and J. Jorge. “Marker-making using automatic placement of irregular shapes for the garment industry”. Computer & Graphics, Vol 14 No. 1:41–46, 1990.
C. Bounsaythip, S. Maouche, and G. Roussel. “Algorithms for a marker making system: ε-admissible resolution”. 12th International Conference on Systems Science, Wroclaw (Poland), 1995.
J. Chung, D. J. Hillman, and D. Scott. “An intelligent nesting system on 2-D highly irregular resources”. In Applications of Artificial Intelligence VIII — Proceedings of the 8th International Conference of the International Society for Optical Engineering (SPIE), pages 472–483, 1990. Vol. 1293.
R. Cuninghame-Green. ”Geometry, shoemaking and the milk tray problem”. New Scientist, No. 12:50–53, 1989.
R. Cuninghame-Green. ”Cut out waste!”. OR Insight, Vol. 5, No. 3:4–7, 1992.
K. Daniels, Z. Li, and V. Milenkovic. “Automatic marker making”. In T. Shermer, editor, Proceedings of the Third Canadian Conference on Computational Geometry, August 1991.
K. Daniels, Z. Li, and V. Milenkovic. “Placement and compaction of non-convex polygons for clothing manufacture”. In C. Wang, editor, Proceedings of the Fourth Canadian Conference on Computational Geometry, August 1992.
K. Daniels and V. Milenkovic. “Multiple translational containment: Approximate and exact algorithms”. Proceedings of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 205–214, 1995.
K. Daniels and V. Milenkovic. “Translational polygon containment and minimal enclosure using geometric algorithms and mathematical programming”. 36th Annual IEEE Conference on Foundations of Computer Science, 1995.
K. A. Dowsland and W. B. Dowsland. “Packing problems”. European Journal of Operational Research (EJOR), Vol. 56, No. 1:2–14, 1992.
K. A. Dowsland and W. B. Dowsland. “Solution approaches to irregular nesting problems”. Working paper EBMS/1994/18, European Business Management School, University of Wales, Swansea, Singleton Park, Swansea SA2 8PP, UK, 1994.
H. Dyckhoff and U. Finke. “Cutting and Packing in Production and Distribution”. Physica-Verlag, Heidelberg, Germany, 1992.
R. J. Fowler, M. S. Paterson, and S. L. Tanimoto. “Optimal packing and covering in the plane are NP-complete”. Information Processing Letters (IPL), Vol. 12, No. 3:133–137, 1981.
R. Heckmann and T. Lengauer. “A simulated annealing approach to the nesting problem in the textile manufacturing industry”. In R. E. Burkard, P. L. Hammer, T. Ibaraki, and M. Queyranne, editors, Annals of Operations Research, volume No. 57, pages 103–133. J.C. Baltzer AG Science Publishers, Amsterdam, 1995.
J. Heistermann and T. Lengauer. “Efficient automatic part nesting on irregular and inhomogeneous surfaces”. In Proceedings of the Fourth ACM-SIAM Symposium on Discrete Algorithms (SODA '93), pages 251–259, Austin, Texas, USA, January 1993.
J. Heistermann and T. Lengauer. “The nesting problem in the leather manufacturing industry”. In R. E. Burkard, P. L. Hammer, T. Ibaraki, and M. Queyranne, editors, Annals of Operations Research, volume No. 57, pages 147–173. J.C. Baltzer AG Science Publishers, Amsterdam, 1995.
Z. Li and V. Milenkovic. “A compaction algorithm for non-convex polygons and its application”. In Proceedings of the Ninth Annual ACM Symposium on Computational Geometry, May 1993.
S. Maouche and G. Roussel. “Intelligent lay-planning system for irregular shapes and sheet with patterns and flaws. resolution by ε-admissible tree search”. 24th International Symposium on Industrial Robots (ISIR), Tokyo, 1993.
V. Milenkovic. “Multiple translational containment, Part II: Exact algorithms”. Extended abstract, Aiken Computation Laboratory, Harvard University, Cambridge, MA 02138, 1994.
C. E. Pfefferkorn. “A heuristic problem solving design system for equipment or furniture layouts”. Communications of the ACM, Vol. 18, No. 5:286–297, 1975.
E. Ridenour Paternoster and P. E. Sweeney. “Cutting and packing problems: A categorized application-orientated research bibliography”. Journal of the Operational Research Society, Vol. 43, No. 7:691–706, 1992.
S. Roberts. “Application of heuristic techniques to the cutting-stock problem for worktops”. Journal of the Operational Research Society, Vol. 35, No. 5:369–377, 1984.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1996 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Heckmann, R., Lengauer, T. (1996). Computing upper and lower bounds on textile nesting problems. In: Diaz, J., Serna, M. (eds) Algorithms — ESA '96. ESA 1996. Lecture Notes in Computer Science, vol 1136. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-61680-2_70
Download citation
DOI: https://doi.org/10.1007/3-540-61680-2_70
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-61680-1
Online ISBN: 978-3-540-70667-0
eBook Packages: Springer Book Archive