Journal
COMPUTERS & OPERATIONS RESEARCH
Volume 39, Issue 7, Pages 1487-1505Publisher
PERGAMON-ELSEVIER SCIENCE LTD
DOI: 10.1016/j.cor.2011.08.021
Keywords
Leather nesting problem; Constructive heuristics; Computational study
Categories
Funding
- Algoritmi Research Center of the University of Minho
- Portuguese Science and Technology Foundation [SFRH/BDE/15650/2007, UMINHO/BII/183/2009]
- Fundação para a Ciência e a Tecnologia [SFRH/BDE/15650/2007] Funding Source: FCT
Ask authors/readers for more resources
In this paper, we address one of the hardest two-dimensional cutting stock problems that can be found in industry. The problem is called the Leather Nesting Problem, and it consists in finding the best layouts for a set of irregular shapes within large natural leather hides with highly irregular contours, and which may have holes and quality zones. Here, we focus on a real case from the automotive industry, and in particular on the production of car seats. In this case, the irregular shapes that have to be cut from the hides are pieces of the car seats. The practical relevance of this problem, and the potential value of the savings that good solutions may generate, contrasts with the very small number of contributions that have been reported in the literature. In this paper, we aim to contribute to the efficient resolution of this problem by exploring in depth many new different constructive procedures. Our approaches rely on the computation of no-fit polygons, and try to use the information provided by these polygons as much as possible. Different strategies for sorting, selecting and placing the pieces, and for evaluating the placement of these pieces are proposed and discussed. We also report on an extensive set of computational experiments using real instances. To evaluate our approaches, we applied the real criteria used by companies operating in this sector. These experiments show that our approaches can generate very high quality layouts within the same time limits as those needed by human operators. (C) 2011 Elsevier Ltd. All rights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available