基于遗传算法求解带公差的“一刀切”问题  

GENETIC ALGORITHM-BASED SOLUTION TO GUILLOTINE PROBLEM WITH TOLERANCE

作　　者：张维存[1] 秦荣[1] 康凯[1] 

机构地区：[1]河北工业大学经济管理学院,天津300401

出　　处：《计算机应用与软件》2015年第2期72-75,88,共5页Computer Applications and Software

基　　金：教育部博士点基金项目(20121317110012);河北省高等学校自然科学青年基金项目(2011125)

摘　　要：矩形件排样是典型的组合优化问题,在很大程度上影响着企业生产效率。将遗传算法与启发式规则相结合,同时在排样过程中考虑待排样式的公差,求解"一刀切"矩形件排样问题。首先,采用实数基因编码方式,由实数基因值与启发式信息结合确定待排样式的优先权。其次,基于待排样式的最小极限尺寸,采用两步解码方法。第一步为初始填充,将待排样式组合成满足"一刀切"的可行条料,并求解板材利用率最高的条料填充方式;第二步为对第一步剩余空白区的填充,求解不同启发式信息下,空白区利用率最高的待排样式填充方式。再者,基于待排样式的最大极限尺寸和板材尺寸,对最优排样方案进行调整。最后,以VB6.0为开发工具将算法实现,并通过实例对比分析证明了算法的有效性。Rectangular packing is a typical combinatorial opfimisation 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 dimensionof 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.

关 键 词：“一刀切”排样 矩形件排样 遗传算法 启发式规则 公差 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]