The Ordered Cutting Stock Problem

The one‐dimensional cutting stock problem (CSP) is a classic combinatorial optimization problem in which a number of parts of various lengths must be cut from an inventory of standard‐size material. The classic CSP ensures that the total demand for a given part size is met but ignores the fact that parts produced by a given cutting pattern may be destined for different jobs. As a result, applying the classic CSP in a dynamic production environment may result in many jobs being open (or partially complete) at any point in time—requiring significant material handling or sorting operations. This paper identifies and discusses a new type of one‐dimensional CSP, called the ordered CSP, which explicitly restricts to one the number of jobs in a production process that can be open, or in process, at any given point in time. Given the growing emphasis on mass customization in the manufacturing industry, this restriction can help lead to a reduction in both in‐process inventory levels and material handling activities. A formal mathematical formulation is provided for the new CSP model, and its applicability is discussed with respect to a production problem in the custom door and window manufacturing industry. A genetic algorithm (GA) solution approach is then presented, which incorporates a customized heuristic for reducing scrap levels. Several different production scenarios are considered, and computational results are provided that illustrate the ability of the GA‐based approach to significantly decrease the amount of scrap generated in the production process.