融合动态规划与背包问题的多目标切割优化算法

打开文本图片集

中图分类号：S784 文献标识码：A 文章编号：2095-2953（2025）10-0044-08

Abstract：To address the problem where the output sequence of the original sawing algorithm in the fixed length stageof passive wooden window edge material processing mismatches stacking requirements，leading to difficulties in efciently and stably automating the stacking of the resulting segments due to incompatible size combinations -a bottleneck constraining overallproduction eficiency，this paper proposes a multi-objective optimizationalgorithm integrating Dynamic Programming （DP）rules with the Knapsack Problem. By formulating a one dimensional Knapsack Problem，the algorithm uses a Genetic Algorithm to search the solution space for candidate cutting paterns， which are treatedascombinations of "items"in the knapsack.It aims to maximize lumber utilization rate and stacking compliance rateas dual objectives.Adynamic state transition equation isdesigned，incorporating penalty functionsandweighting coefcients tobalance theprioritiesof thetwoojectives.Finalresults demonstratethatthisoptimized algorithmsignificantlyenhances stacking eficiencywhile maintaining theoriginal levelof lumberutilization.

Key words：knapsack problem; cutting stock optimization; dynamic programming;stacking model

木窗作为一种传统的建筑材料，在追求自然、环保和高品质生活的今天，其在现代建筑中仍占有一席之地[1]。（剩余6656字）