[1]陈烨烨,李捍东.基于贪心混合定位算法三阶段排样问题研究[J].机械与电子,2024,42(03):12-16.
　CHEN Yeye,LI Handong.Research on Three-stage Nesting Problem Based on Greedy Hybrid Positioning Algorithm[J].Machinery & Electronics,2024,42(03):12-16.
点击复制

基于贪心混合定位算法三阶段排样问题研究()
分享到：

《机械与电子》[ISSN:1001-2257/CN:52-1052/TH]

卷:
42
期数:
2024年03期
页码:
12-16
栏目:
设计与研究
出版日期:
2024-03-25

文章信息/Info

Title:
Research on Three-stage Nesting Problem Based on Greedy Hybrid Positioning Algorithm
文章编号:
1001-2257 ( 2024 ) 03-0012-05
作者:
陈烨烨; 李捍东
贵州大学电气工程学院,贵州 贵阳 550025
Author(s):
CHEN Yeye ;  LI Handong
( College of Electrical Engineering , Guizhou University , Guiyang 550025 , China )
关键词:
三阶段排样; 混合整数规划模型; 贪心混合定位算法
Keywords:
three stages nesting ;  mixed integer programming model ;  greedy hybrid positioning algorithm
分类号:
TP18 ; TH16
文献标志码:
A
摘要:
针对三阶段排样板材利用率问题,提出了基于贪心混合定位算法的三阶段排样优化方法。以板材利用率为优化目标,首先建立带约束的混合整数规划模型,对三阶段排样问题进行分割;其次将板材分成 3 个分区并使用贪心算法对输入序列进行排序优化;最后使用混合定位算法对候选矩形件找最优板材放置分区。研究采用数据规模为 3 000 块矩形件的 4 组板材数据集进行验证,结果表明,所提模型较其他算法板材利用率得到提高,且运行时长大幅缩短。
Abstract:
A three-stage layout optimization method based on greedy hybrid positioning algorithm was proposed to solve the utilization problem of three-stage layout.Taking the utilization rate of sheet metal as the optimization objective , firstly , a constrained mixed integer programming model is established to segment the three-stage layout problem ; secondly , the plate is divided into three partitions and the input sequence is sorted and optimized by greedy algorithm ; finally , a hybrid positioning algorithm is used to find the optimal plate placement partition for the candidate rectangular parts.Four sets of plate data with a data scale of 3 000 rectangular pieces are used to verify the results.The results show that the proposed model has higher plate utilization and shorter running time than other algorithms.

参考文献/References:

[ 1 ] 曾晓亮,吴琼,袁旭华 . 二维矩形件排样问题的自适应多岛遗传算法优化[ J ] . 锻压技术, 2020 , 45 ( 12 ): 53-58.

[ 2 ] 赵晓东,米小珍 . 遗传算法模型在矩形件排样优化中的应用[ J ] . 锻压技术, 2007 ( 6 ): 153-156.
[ 3 ] 季君,邢斐斐,黄敦华,等 . 一种分阶段式匀质块最优矩形件排样方法[ J ] . 锻压技术, 2021 , 46 ( 2 ): 46-51.
[ 4 ] 王莉 . 矩形件排样问题的遗传模拟退火混合求解算法[ J ] . 锻压技术, 2021 , 46 ( 8 ): 70-76.
[ 5 ] CUI M , YANG K , DENG X G , et al.Double genes improved genetic algorithm for solving two-dimensional rectangular layout problem [ J ] .Journal of physics : conference series , 2021 , 213 ( 1 ): 012007.
[ 6 ] SILVA E , ALVELOS F , CARVALHO J M V D.An integer programming model for two-and three-stage two-dimensional cutting stock problems [ J ] .European journal of operational research , 2010 , 205 ( 3 ): 699-708.
[ 7 ] BRENDA S , COFFMAN E G , RIVEST R L.Orthogonal packing in two dimensions [ J ] .SIAM Journal on computing , 1980 , 9 ( 4 ): 846-855.
[ 8 ] 贾志欣,殷国富,罗阳 . 二维不规则零件排样问题的遗传算法求解[ J ] . 计算机辅助设计与图形学学报, 2002( 5 ): 467-470.
[ 9 ] 张德富,韩水华,叶卫国 . 求解矩形 Packing 问题的砌墙式启发式算法[ J ] . 计算机学报, 2008 ( 3 ): 509-515.
[ 10 ] LONG J Y , ZHENG Z , GAO X Q , et al.An effective heuristic based on column generation for the two-dimensional three-stage steel plate cutting problem [ J ] .Annals of operations research , 2020 , 289 ( 2 ): 291-311.
[ 11 ] 王静静,瞿少成,李科林 . 一种基于并行交叉遗传算法的二维不规则排样问题求解[ J ] . 计算机应用与软件,2020 , 37 ( 7 ): 188-193.
[ 12 ] 刘诚,孙远升,花军,等 . 基于遗传贪心混合搜索的人造板下料算法[ J ] . 林业工程学报, 2021 , 6 ( 4 ): 127-133.
[ 13 ] 宋连超,朱建良,张彤 . 矩形件排样优化贪婪算法及系统开发[ J ] . 哈尔滨理工大学学报, 2007 , 12 ( 1 ); 29-31.
[ 14 ] 刘诚,孙远升,花军,等 . 基于贪心算法及局部枚举策略的人造板排样方案研究 [ J ] . 木材科学与技术,2021 , 35 ( 6 ): 55-61.
[ 15 ] 胡文蓓 . 二维矩形件排样问题高效求解算法研究[ D ] .南昌:江西财经大学,2018.

备注/Memo

备注/Memo:
收稿日期: 2023-08-08
基金项目:国家自然科学基金资助项目( 52167007 )
作者简介:陈烨烨 ( 2000- ),女,贵州遵义人,硕士研究生,研究方向为电子信息;李捍东 ( 1966- ),男,贵州贵阳人,教授,硕士研究生导师,研究方向为计算机控制、嵌入式系统。
更新日期/Last Update: 2024-03-25