两阶段遗传算法和贪心策略相结合的多约束排样优化方法  

Layout Optimization Based on Two-Stage Genetic Algorithm and Greedy Strategy

作　　者：马英钧 钟俊江[1] MA Yingjun;ZHONG Junjiang(School of Mathematics&Statistics,Xiamen University of Technology,Xiamen 361024,China)

机构地区：[1]厦门理工学院数学与统计学院,福建厦门361024

出　　处：《厦门理工学院学报》2023年第3期79-87,共9页Journal of Xiamen University of Technology

基　　金：福建省自然科学基金项目(2021J05260,2023J011433);教育部人文社会科学研究青年基金项目(21YJC910011);福建省中青年教师教育科研项目(JAT200474)。

摘　　要：为了提升产品排样问题的板材利用率,降低生产成本,同时满足切割过程中的“齐头切”和“阶段数不超过3”的约束,分别建立产品和条带组合优化的数学模型;引入序号编码、部分交叉映射,设计局部最优解码方案,进而建立两阶段遗传算法模型。基于贪心策略分别建立产品和条带余料再利用算法来提升利用率,提出一种两阶段遗传算法和贪心策略的排样优化方法。5个基准数据集验证的结果表明:与其他排样优化模型相比,多阶段遗传算法和贪心策略的排样结果不仅满足“齐头切”和“阶段数”的约束,同时板材的利用率更高,在5个数据集上的板材利用率基本上都可保持在80%以上。To improve the plate utilization rate,reduce cost,and satisfy the constraints of“straight and edge cutting”and“no more than 3 stages”in the cutting process,a model of a two-stage genetic algorithm with the greedy strategy was proposed to optimize the layout.To accomplish this,mathematical models of product and strip combination were first introduced with serial number coding,partial cross mapping and local optimal decoding schemes to develop the two-stage genetic algorithm model,and the greedy strategy used to develop the algorithm for product and strip residual material reuse to improve the utilization rate.The results verified by five benchmark data sets show that compared with other layout optimization models,the layout results of the two-stage genetic algorithm with the greedy strategy meet the constraints of“straight and edge cutting”and“no more than 3 stages”,and have a higher plate utilization rate,marking basically 80%or more on all five data sets.

关 键 词：排样优化 遗传算法 贪心策略 板材利用率 

分 类 号：O221.2[理学—运筹学与控制论]