生成最优同质条带两阶段布局方式的精确算法

doi:10.16731/j.cnki.1671-3133.2018.07.004

现代制造工程 ›› 2018, Vol. 454 ›› Issue (7): 17-22.doi: 10.16731/j.cnki.1671-3133.2018.07.004

生成最优同质条带两阶段布局方式的精确算法

季君¹, 张文增², 邢斐斐¹, 谢维³, 崔耀东⁴

1 北京电子科技职业学院机电工程学院,北京 100176;
2 清华大学机械工程系,北京 100084;
3 北京工业大学城市交通学院,北京 100124;
4 广西大学计算机与电子信息学院,南宁 530004

收稿日期:2017-09-22 出版日期:2018-07-20 发布日期:2018-07-20
作者简介:季君,博士,讲师,主要研究方向为优化计算技术、CAD,已发表文章30余篇,其中第一作者26篇,SCI检索1篇,EI检索10篇,中文核心6篇。张文增,博士,副教授,主要研究方向为机器人技术及自动化。邢斐斐,博士,讲师,主要研究方向为智能工程,先进制造技术。谢维,博士,教授,主要研究方向为智能控制,信息处理。崔耀东,博士,教授,主要研究方向为优化计算技术、CAD。E-mail:wenzeng@tsinghua.edu.cn
基金资助:
国家自然科学基金项目(51575302);北京市自然科学基金项目(G170005);北京电子科技职业学院科技重点课题项目(YZKB2015008,YZK2016031)

An exact algorithm for generating optimal two stage homogeneous strip layouts

Ji Jun¹, Zhang Wenzeng², Xing Feifei¹, Xie Wei³, Cui Yaodong⁴

1 School of Mechanical,Electronic Engineering,Beijing Polytechnic,Beijing 100176,China;
2 Dept.of Mechanical Engineering,Tsinghua University,Beijing 100084,China;
3 College of Metropolitan and Transportation,Beijing University of Technology,Beijing 100124,China;
4 School of Computer and Electronics Information,Guangxi University,Nanning 530004,China

Received:2017-09-22 Online:2018-07-20 Published:2018-07-20

摘要/Abstract

摘要： 传统最优解算法在解决大规模二维件布局问题时,计算时间较长。提出一种基于同质条带两阶段布局算法,此算法生成的同质两阶段布局方式,满足生产中的剪冲下料工艺,且计算时间合理。首先,竖直剪切线将板材分割成同质段;然后,水平剪切线将同质段分割成同质条带。通过求解动态规划算法生成最优同质条带布局方式,求解背包问题得到同质条带在同质段上和同质段在板材上的最优布局方式。利用经典文献中的基准测题,将此算法与普通两阶段算法、TABU500算法和最优解精确算法进行比较,结果表明此算法在布局价值优于普通两阶段和TABU500型算法,计算时间远远短于最优解精确算法,优化结果等于或极接近于最优解精确算法。

关键词: 布局, 同质条带, 背包问题

Abstract: The time required by an optimal exact algorithm to solve the large-scale rectangle two-dimensional cutting problems may become unbearable.So an algorithm for two-stage homogeneous strip patterns for pieces is presented.The algorithm not only is appropriate for the shearing and punching process,but also reasonable in time.Firstly,vertical cuts divide the stock sheet into composite strips,and then horizontal cuts divide the composite strips into homogeneous strips.The algorithm uses a dynamic programming recursion to determine the optimal homogeneous strip layout,solves knapsack problems to obtain the homogeneous strip layout on the composite and the composite strip layout on the sheet.The algorithm is tested through benchmark problems,and compares with three famous algorithms,the classic two-stage algorithm,the TABU500 algorithm and optimal algorithm.The pattern value of this algorithm is better than that of the classic two-stage and TABU500 algorithm.What’s more,this algorithm can give solutions very close to optimal algorithm,and the computation time is shorter than optimal algorithm.

Key words: layout, homogeneous strip, knapsack problem

中图分类号:

TP391

季君, 张文增, 邢斐斐, 谢维, 崔耀东. 生成最优同质条带两阶段布局方式的精确算法[J]. 现代制造工程, 2018, 454(7): 17-22.

Ji Jun, Zhang Wenzeng, Xing Feifei, Xie Wei, Cui Yaodong. An exact algorithm for generating optimal two stage homogeneous strip layouts[J]. Modern Manufacturing Engineering, 2018, 454(7): 17-22.

[1]	马成昊, 闫丰亭, 李媛媛, 李志博. 车间多排设备布局问题的优化研究^*[J]. 现代制造工程, 2024, 521(2): 8-15.
[2]	刘智飞;马建民;刘振东. 考虑不确定因素的可重构车间布局与调度联合优化[J]. 现代制造工程, 2023, 515(8): 15-21.
[3]	张家骅. 不确定需求下的单向环形设备动态布局方法[J]. 现代制造工程, 2023, 518(11): 12-18.
[4]	张思奇，于登辉，郑一明，李冠洋. 基于多目标候鸟算法的车间布局研究[J]. 现代制造工程, 2022, 497(2): 16-23.
[5]	葛晓梅，李世豪. 基于改进遗传算法的多目标车间布局优化问题研究[J]. 现代制造工程, 2021, 486(3): 10-14.
[6]	霍震,杨子昭,王岩峰,刘卫东,周恢,高谦. 基于SLP法和AHP法的离散物料智能生产线设计与仿真[J]. 现代制造工程, 2021, 493(10): 50-59.
[7]	周尔民，邓洪，费卫卫，周伟. 人因视角下的设备布局时间成本优化研究[J]. 现代制造工程, 2020, 473(2): 110-115.
[8]	晁智强，薛大兵，刘相波，宁初明，王飞. 不同扭力轴布局下悬挂系统振动分析[J]. 现代制造工程, 2020, 472(1): 65-71.
[9]	马俊燕, 刘祥沙, 廖小平, 郑羽嘉, 鲁娟, 苏贵长. 紧凑布局设计的物理学研究及实验方法设计[J]. 现代制造工程, 2017, 438(3): 7-17.
[10]	琚晶晶, 林锦国. 基于改进的GA-SLP生产车间布局规划研究[J]. 现代制造工程, 2017, 446(11): 120-124.
[11]	郭翠平, 魏修亭, 魏振先, 张卫国. 汽车轮胎自动装车堆垛算法设计[J]. 现代制造工程, 2017, 445(10): 14-18.

生成最优同质条带两阶段布局方式的精确算法

An exact algorithm for generating optimal two stage homogeneous strip layouts

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 11

编辑推荐

Metrics