中图分类号：S777 文献标识码：A DOI：10.7525/j.issn.1006-8023.2025.03.016

Abstract：In thecustomization process of pasive wooden window manufacturing，reducing material wasteduring frame cutting is keytocostreduction.This problem is modeledasaone-dimensional cutting stock problem.Toadress the issue of traditional geneticalgorithms wheretheindividual encoding method tends toleadtothedestructionofcuing patternsandlow exploration eficiency during iterations，anew individual encoding methodis proposed to maintainthe integrityofcutting patterns throughout the evolutionary process.Additionally，aheuristic strategy andacorrection strategy are introduced for individual correctionandpopulationevolution.Simulationresultsshowthat fordiferent testcases， the average material utilization rate，excluding the last remnants，exceeds 99 % ，with some improvements in the length of thelastremnants compared toother algorithms.Fortwosets ofreal production data fromenterprises，the proposed algorithmachieves the theoreticallower bound，withaverageutilizationrates （excluding the lastremnants）of 99.49%and 99.66%，respectively，outperforming the resultsofthe company's existing software.This demonstrates the algorithm's potential to efectively reduce costs and provide practical solutions in engineering applications.

Keywords：One-dimensionalcutting stock problem；genetic algorithm；heuristic algorithm；population encoding；usable leftovers

0 引言

场正在不断扩大。其中，被动式木窗因其美观、保温、隔音以及低碳等优势，逐渐受到市场的关注和喜爱[1]。然而，高昂的原料成本制约了定制化被动式木窗市场随着人们对家具定制需求的增加，定制化家具市的进一步扩展。在生产过程中，被动式木窗的边框材通常通过截断标准长度的集成材获得，这一过程中会产生各种废料。因此，为了降低成本，可以通过减少截断过程中原材料的浪费来实现优化，这就涉及一维下料问题。

一维下料问题（one-dimensional cutting stock prob-lem，1D-CSP）旨在通过切割给定规格的原料生成满足生产需求的零件或产品，并尽可能减少材料浪费或使用量。这一问题在制造业中备受关注[2]，由于1D-CSP具有非确定性多项式困难（non-deterministicpolyno-mial-timehard，NP-hard）属性，随着问题规模的增大，求解愈发困难。为解决1D-CSP，大量文献进行了相关研究。目前主要的解决方式有2种。一是精确算法，包括列生成[3-4]、分支-切割-定价[5]等方法，常用于求解最优解，但需要消耗大量的计算资源。二是启发式算法，可分为传统启发式和元启发式，用于获得可接受时间内的可行解6。传统启发式算法，如降序首次适应算法（first fit decreasing，FFD）[7]、降序最佳适应算法（best fitdecreasing，BFD）[8]、残差重组启发式算法（residual recombination heuristic，RRH）等[9]，通过设计的策略快速获取下料方案，但对于较大规模的问题，此类方法仅能得到局部解，为此许多文献中使用元启发算法进行求解，比如沈显君等[1]结合粒子群算法、遗传算法以及模拟退火算法提出的自适应广义粒子群优化算……