We introduce an evolutionary stochastic-local-search (SLS) algorithm for addressing a generalized version of the so-called 1 V D R cutting-stock problem. Cutting-stock problems are encountered often in industrial environments and the ability to address them efficiently usually results in large economic benefits. Traditionally linear-programming-based techniques have been utilized to address such problems, however their flexibility might be limited when nonlinear constraints and objective functions are introduced. To this end, this paper proposes an evolutionary SLS algorithm for addressing one-dimensional cutting-stock problems. The contribution lies in the introduction of a flexible structural framework of the optimization that may accommodate a large family of diversification strategies including a novel parallel pattern appropriate for SLS algorithms (not necessarily restricted to cutting-stock problems). We finally demonstrate through experiments in a real-world manufacturing problem the benefit in cost reduction of the considered diversification strategies.
Due to the fact that many different types of cutting stock problems can be found in the literature, e.g. with respect to dimensionality, characteristics of large and small objects, shape of figures and so forth, it is highly desirable that the scientific community is using the same language and terminology when describing problems and the corresponding solution approaches. In @cite_36 a typology that covered the most important four characteristics at the time to classify optimization problems like the cutting stock problems was introduced. This typology was improved by @cite_25 . An overview of characteristics how to classify the problems in the literature can be found in @cite_24 . The problem can further be distinguished whether it is off-line (full knowledge of the input) or on-line (no knowledge of the next items) @cite_0 .
@cite_36 @cite_0 @cite_25 @cite_24
1979415050 2105175235 2049815971
Abstract Cutting and packing problems appear under various names in literature, e.g. cutting stock or trim loss problem, bin or strip packing problem, vehicle, pallet or container loading problem, nesting problem, knapsack problem etc. The paper develops a consistent and systematic approach for a comprehensive typology integrating the various kinds of problems. The typology is founded on the basic logical structure of cutting and packing problems. The purpose is to unify the different use of notions in the literature and to concentrate further research on special types of problems. The number of publications in the area of Cutting and Packing (C&P) has increased considerably over the last two decades. The typology of C&P problems introduced by Dyckhoff [Dyckhoff, H., 1990. A typology of cutting and packing problems. European Journal of Operational Research 44, 145–159] initially provided an excellent instrument for the organisation and categorisation of existing and new literature. However, over the years also some deficiencies of this typology became evident, which created problems in dealing with recent developments and prevented it from being accepted more generally. In this paper, the authors present an improved typology, which is partially based on Dyckhoff’s original ideas, but introduces new categorisation criteria, which define problem categories different from those of Dyckhoff. Furthermore, a new, consistent system of names is suggested for these problem categories. Finally, the practicability of the new scheme is demonstrated by using it as a basis for a categorisation of the C&P literature from the years between 1995 and 2004. � 2006 Elsevier B.V. All rights reserved. The assortment or catalog problem involves determining which of the possible set of sizes or qualities of some product should be stocked when it is not possible or desirable to stock all of them and substitution in one direction (larger for smaller or higher-quality for lower-quality) is possible at some cost. We review the work published on this topic over the last 50 years.