第42卷第5期 Vol. 42No.5
假压技术
FORGING & STAMPING TECHNOLOGY
基于同质段矩形优化排样问题求解
姜永亮
（海南师范大学信息网络与数据中心，海南海口571158）
2017年5月 May 2017
摘要：为有效解决企业实际生产中的矩形优化排样问题，对矩形优化排样算法进行研究，给出基于同质段矩形优化排样向题的求解算法，该算法可同时有效解决企业实际生产中矩形优化排样的单一排样和套裁排样问题。算法首先基于隐式枚举法求出所有同质条带的最优排样及备选同质段，对备选同质段进行规范化处理求出所有的候选同质段，使用候选同质段将板材分成若干个子段，并将矩形优化排样问题转化为完全背包向题，最后基于动态规划算法进行求解。两组应用实例验证了本文算法的有效性
关键词：矩形优化排样；规范化处理；候选同质段；动态规划算法 DOI: 10. 13330/j. issn. 1000-3940. 2017. 05. 029
中图分类号：TP391.7
文献标识码：A
文章编号：1000-3940（2017）05-0159-05
Solutiononrectangularoptimallayoutbasedonthehomogeneoussegments
Jiang Yongliang
( Information Network and Data Center, Hainan Normal University, Haikou 571158, China)
Abstract : In order to solve the problems of rectangular optimal layout effectively in practical production, the rectangular optimal layout algo rithms were studied, and the solution algorithm was given based on the homogeneous segments. The above algorithm could effectively solve the single rectangular layout problem and suit cut layout in practical production. Firstly , based on the implicit enumeration method, the opti-
mal layout of all homogeneous strips and the alternative homogeneous
gments were calculated. Secondly , all the alternative homogeneous
segments were normalized for the candidate homogeneous segments. After the sheet was divided into several subsections with the candidate homogeneous segments, the rectangular optimal layout problem was converted to the complete knapsack problem. Finally, a solution was ob-tained based on the dynamic programming algorithm. Furthemore, two sets of application examples validated the effectiveness of the algorithm. Key words : rectangular optimal layout ; standardized treatment; candidate homogeneous segments; dynamic programming algorithm
矩形优化排样问题是机械制造、汽车制造等企业实际生产中经常遇到的向题，该向题在计算复杂性方面属于典型的NP问题[1-2]。根据企业实际生产中在同一张板材上加工出零件种类的多少，可将矩形优化排问题分为单一排样和套裁排样。对矩形套裁排样向题国内外学者研究较多[3-$]，这些算法在设计时主要考虑矩形套裁问题，进而导致在很多情况下这些算法在解决单一矩形排样问题方面板材利用率不高。对于单一矩形优化排样问题国内外学者也进行了相关研究(9-12)。在企业实际生产中经常会遇到单一排样与套裁排样并存的问题，尤其是遇到板材长度远远超过剪床刀刃长度时，实际生产中工人更倾向于在一个子段上加工一类零件。因此
收稿日期：20170225；修订日期：20170330
基金项目：国家自热科学基金资助项目（71361008）；海南省重点科技项目（ZDXM20130080）
作者简介：姜永亮（1980-），男，硕士，副教投 E-mail : yongliangjiang@ 126. com
万方数据
如何给出一个既能有效解决单一排样又能很好解决套裁排样，且切割工艺相对简单的排样系统是企业实际生产中急需解决的间题。鉴于此，本文对矩形优化排样算法进行研究，综合考虑切割工艺和原材料利用率两个因素的情况下，给出基于同质段矩形优化排样算法，有效解决了企业实际生产的矩形单一排样和套裁排样并存的问题。算法首先使用枚举法求出所有同质条带的最优排样，然后求出备选同质段，并对备选同质段进行规范化处理求出所有的候选同质段，并使用候选同质段在板材上进行排样，最后将矩形优化排样问题转化为完全背包问题，并
基于动态规划算法进行求解。 1
问题描述及相关概念 1.1
问题描述
假定企业实际生产排样任务为：在L×W的矩形板材上，最多排出m种矩形零件，第i种零件的