Optimization of Passive Wooden Window Material Cutting Based on Genetic Algorithm

REN Changqing, WU Ziqi, YAN Jie, DING Xingchen, YANG Chunmei

PDF(1697 KB)
PDF(1697 KB)
Forest Engineering ›› 2025, Vol. 41 ›› Issue (03) : 595-602. DOI: 10.7525/j.issn.1006-8023.2025.03.016
Forest Industry Technology and Equipment

Optimization of Passive Wooden Window Material Cutting Based on Genetic Algorithm

Author information +
History +

Abstract

In the customization process of passive wooden window manufacturing, reducing material waste during frame cutting is key to cost reduction. This problem is modeled as a one-dimensional cutting stock problem. To address the issue of traditional genetic algorithms where the individual encoding method tends to lead to the destruction of cutting patterns and low exploration efficiency during iterations, a new individual encoding method is proposed to maintain the integrity of cutting patterns throughout the evolutionary process. Additionally, a heuristic strategy and a correction strategy are introduced for individual correction and population evolution. Simulation results show that for different test cases, the average material utilization rate, excluding the last remnants, exceeds 99%, with some improvements in the length of the last remnants compared to other algorithms. For two sets of real production data from enterprises, the proposed algorithm achieves the theoretical lower bound, with average utilization rates (excluding the last remnants) of 99.49% and 99.66%, respectively, outperforming the results of the company's existing software. This demonstrates the algorithm's potential to effectively reduce costs and provide practical solutions in engineering applications.

Key words

One-dimensional cutting stock problem / genetic algorithm / heuristic algorithm / population encoding / usable leftovers

Cite this article

Download Citations
REN Changqing , WU Ziqi , YAN Jie , et al . Optimization of Passive Wooden Window Material Cutting Based on Genetic Algorithm. Forest Engineering. 2025, 41(03): 595-602 https://doi.org/10.7525/j.issn.1006-8023.2025.03.016

References

1
ZHENG L MUELLER M LUO C,et al.Variations in whole-life carbon emissions of similar buildings in proximity:An analysis of 145 residential properties in Cornwall,UK[J].Energy and Buildings2023296:113387.
2
RAVELO S V MENESES C N SANTOS M O.Meta-heuristics for the one-dimensional cutting stock problem with usable leftover[J].Journal of Heuristics202026(4):585-618.
3
GILMORE P C GOMORY R E.A linear programming approach to the cutting-stock problem[J].Operations Research19619(6):849-859.
4
GILMORE P C GOMORY R E.A linear programming approach to the cutting stock problem—Part Ⅱ[J].Operations Research196311(6):863-1025.
5
BELOV G SCHEITHAUER G.A branch-and-cut-and-price algorithm for one-dimensional stock cutting and two-dimensional two-stage cutting[J].European Journal of Operational Research2006171(1):85-106.
6
CHEN Y H HUANG H C CAI H Y,et al.A genetic algorithm approach for the multiple length cutting stock problem[C]//2019 IEEE 1st Global Conference on Life Sciences and Technologies (LifeTech).IEEE,2019:162-165.
7
JOHNSON D S DEMERS A ULLMAN J D,et al.Worst-case performance bounds for simple one-dimensional packing algorithms[J].SIAM Journal on Computing19743(4):299-325.
8
BAKER B S COFFMAN E G.A tight asymptotic bound for next-fit-decreasing bin-packing[J].SIAM Journal on Algebraic Discrete Methods19812(2):147-152.
9
CAMPELLO B S C GHIDINI C T L S AYRES A O C,et al.A residual recombination heuristic for one-dimensional cutting stock problems[J].Top202230(1):194-220.
10
沈显君,杨进才,应伟勤,等.一维下料问题的自适应广义粒子群优化求解[J].华南理工大学学报(自然科学版)200735(9):113-117.
SHEN X J YANG J C YING W Q,et al.Adaptive general particle swarm optimization for one-dimension cutting stock problem[J].Journal of South China University of Technology (Natural Science Edition)200735(9):113-117.
11
魏凉良,叶家玮.一维下料问题的改进自适应遗传算法[J].华南理工大学学报(自然科学版)200331(6):26-30.
WEI L L YE J W.Modified adaptive genetic algorithm for one-dimensional cutting problem[J].Journal of South China University of Technology (Natural Science Edition)200331(6):26-30.
12
侯改,何朗,黄樟灿,等.基于差分进化的金字塔演化策略求解一维下料问题[J].计算机科学202047(7):166-170.
HOU G HE L HUANG Z C,et al.Pyramid evolution strategy based on differential evolution for solving one-dimensional cutting stock problem[J].Computer Science202047(7):166-170.
13
丁为.线材下料优化问题建模与混合求解算法研究[D].武汉:华中科技大学,2022.
DING W.Research on modeling and hybrid solving algorithms for wire cutting stock optimization problem[D].Wuhan:Huazhong University of Science and Technology,2022.
14
ALAM T QAMAR S DIXIT A,et al.Genetic algorithm:Reviews,implementations,and applications[J].arXiv preprint arXiv:2007.12673,2020.
15
李培勇,王全华,裘泳铭.型材优化下料的混合遗传算法[J].上海交通大学学报200135(10):1557-1560.
LI P Y WANG Q H QIU Y M.Optimization for one-dimensional cutting using hybrid genetic algorithm[J].Journal of Shanghai Jiao Tong University200135(10):1557-1560.
16
李斌,贺飞.求解一维下料问题的改进混合遗传算法[J].内蒙古大学学报(自然科学版)201445(3):245-250.
LI B HE F.Improved hybrid genetic algorithm for one-dimensional cutting stock problem[J].Journal of Inner Mongolia University (Natural Science Edition)201445(3):245-250.
17
LU Y VASKO F J.A Comprehensive empirical demonstration of the impact of choice constraints on solving generalizations of the 0-1 knapsack problem using the integer programming option of CPLEX® [J].Engineering Optimization202052(9):1632-1644.

Comments

PDF(1697 KB)

Accesses

Citation

Detail

Sections
Recommended

/