查询结果:   张维存,秦荣,康凯.基于遗传算法求解带公差的“一刀切”问题[J].计算机应用与软件,2015,32(2):72 - 75,88.
中文标题
基于遗传算法求解带公差的“一刀切”问题
发表栏目
应用技术与研究
摘要点击数
881
英文标题
GENETIC ALGORITHM-BASED SOLUTION TO GUILLOTINE PROBLEM WITH TOLERANCE
作 者
张维存 秦荣 康凯 Zhang Weicun Qin Rong Kang Kai
作者单位
河北工业大学经济管理学院 天津 300401     
英文单位
School of Management, Hebei University of Technology, Tianjin 300401, China     
关键词
“一刀切”排样 矩形件排样 遗传算法 启发式规则 公差
Keywords
Guillotine packing Rectangular packing Genetic algorithms Heuristic rules Tolerance
基金项目
教育部博士点基金项目(20121317110012);河北省高等学校自然科学青年基金项目(2011125)
作者资料
张维存,副教授,主研领域:工业工程。秦荣,硕士生。康凯,教授。 。
文章摘要
矩形件排样是典型的组合优化问题,在很大程度上影响着企业生产效率。将遗传算法与启发式规则相结合,同时在排样过程中考虑待排样式的公差,求解“一刀切”矩形件排样问题。首先,采用实数基因编码方式,由实数基因值与启发式信息结合确定待排样式的优先权。其次,基于待排样式的最小极限尺寸,采用两步解码方法。第一步为初始填充,将待排样式组合成满足“一刀切”的可行条料,并求解板材利用率最高的条料填充方式; 第二步为对第一步剩余空白区的填充,求解不同启发式信息下,空白区利用率最高的待排样式填充方式。再者,基于待排样式的最大极限尺寸和板材尺寸,对最优排样方案进行调整。最后,以VB6.0为开发工具将算法实现,并通过实例对比分析证明了算法的有效性。
Abstract
Rectangular packing is a typical combinatorial optimisation problem which affects the enterprises productivity to a great extent. In this paper we combine the genetic algorithm with heuristic rules, and meanwhile consider the tolerance of the items in packing process to solve rectangular packing in guillotine problem. First, we use real gene coding mode, the priority of the items is determined based on the combination of real gene value and heuristic information. Secondly, we adopt two steps decoding method according to minimum admissible dimension of the item. The first step is initiative filling, it is to group the items in feasible strips satisfying the guillotine constraint, and to solve strips filling way with highest sheet utility; The second step is the filling of blank regions left in the first step, i.e. to solve the filling means for the items with highest blank region utility in different heuristic information. What’s more, the solution is to adjust the optimal packing scheme based on maximal admissible dimension and sheet size of the items. Finally, we implement the algorithm by using VB6.0 as the developing tool, and prove the effectiveness of the algorithm through examples comparison and analysis.
下载PDF全文