基于改进BFD算法的多规格一维下料系统

0 引 言

    目前很多企业虽然采用了计算机辅助下料，但是大多数算法只能利用单一长度原材料下料，而不能实现多种长度原材料混合下料，而且功能单一，无法与其他部门实现数据共享，下料流程不合理，在企业实施ERP的过程中会成为自动化孤岛。本文设计了一种基于改进的最佳配合降序算法——BFD(Best Fit Decreasing)的优化下料系统，同时引入了流程丙造(BPR)的思想，在高压输电铁塔生产企业中得到了成功的应用。

1 一维下料问题的描述与算法设计

    1.1 一维下料问题的描述

    有m种长度的原材料Yi(i＝1，2，…，m)，每种原材有ai根，有n种长度的待加工工件：G(k＝1，2，…，n)，每种长度工件的需求数为bk根。设ckij(k＝1，2，…，n)为第i根原材料的第j种下料力一式中工件Gk的件数；设原材料Yi有hi种下料力一式，第i根原材料的第j(j＝1，2，…，hi)种下料力一式产生的余料为：

    

    实际生产过程中，往往希望一根原材料上截取的不同长度的工件种类不超过某个数值x(通常是3或4，本文的例子中取4)，即ckij中大于零的个数为c≤x，x在计算时可以调整。

    设整数xij为原材料Yi的第j种下料方式的数量，以产生的余料总长度最短为目标函数，则优化下料的数学模型为：
    
   

    1.2 求解方法

    从组合优化的角度，此模型可视为装箱问题，采用启发式近似算法或遗传算法来求解。两种算法各有优缺点，单纯从数学的角度看，遗传算法的解更接近最优，但实践证明，会给生产带来很大的难度，而采用改进的BFD(Best Fit Decreasing)进行求解，可以得到与遗传算法非常接近的解，同时工艺性能得到了大幅提升。

    BFD算法的下料描述：工件按照降序排列，取出长度为Gk的工件，检查所有原材料当前余料，对余料按升序排列，将Gk放在第一个能容纳它的余料上进行截取。算法流程如图1所示。

图1 算法流程

    求解步骤为：

    1)读取库存原材料和待加工工件数据，对工件按长度降序排列G[k](k＝1，2，…，n)，见表1，数量分别为b[k]，对原材料按长度升序排列为Y[i](i＝1，2，…，m)，数量分别为a[i]。

表1 工件明细表

    2)构建数组ycl[s]＝Y[i]，yclnum[s]＝a[i](s＝1，2，…，m)，gj[z]＝G[k]，gjnum[z]＝b[k](k＝1，2，…，n)，判断数量大于零的原材料和工件的规格数p、q是否减至零，如果都不为零，则转步骤3)，否则转步骤5)。

    3)用数童大于零的原材料ycl[s1](s1＝1，2，…，p)进行“试截取”，得到p个余料，选取其中最小余料对应的那种长度的原材料Y[i]。

    4)用一根Y[i]进行正式截取，a[i]＝a[i]－1，当这根原材料已经不能丙截取任何工件或其上的工件种类c＞x时，剩余长度成为余料，统计本次加工出的工件，转步骤2)。

    5)刘一以上结果进行调整，检查余料中是否有长度大于最后一根原材料工件的，如果有，则把此工件放在该余料上，重复操作直到没有余料可以利用，则计算结束，输出结果(见表2)。表2中，序号为5、7的两组数据之所以c＝4就是这种调整的结果。

表2 下料结果

    1.3 下料示例

    为了便于对比，用李培勇在“多规格-维型材优化下料”中工件数据进行下料，具体见表1(表中长度单位均为mm)；所用原材料为6m、8m、9m三种，数童没有限制，结果见表2。

    “多规格-维型材优化下料”中采用混合遗传算法，共消耗原材料215m，最后一根余料长2764mm，虽然利用率稍高，但单根原材料上截取的工件种类数c往往超过6种，加工难度很大，实际上大规模下料时几乎无法进行操作。本文的算法消耗原材料也是215m，最后一根余料长1074mm，同种原材料内基本上按照工件编号的顺序进行下料，而且c绝大多数为3，这大大方便了工人实际下料时的操作，简化了工序。表2中，下料1的数据格式为：零件编号－零件长度×单根下料数量，例如01－2144×2表T单根原材料上编号为01，长度为2144mm的零件，下料数童为2个，下料2、3、4同理；表2中除原材料长度用m来表示外，其余均为mm。

2 下料工作流程再造

    原材料的充分利用和下料工作效率的提高不仅和算法相关，而且和整个下料工作的流程也有直接关系，尤其是原材料的采购和可用余料的管理。以本系统应用的铁塔企业为例，原有的流程如图2所示。

图2 原有工作流程

    技术部门先对铁塔图样进行放样，对生成的工件明细表进行统计，给出大致的原材料需求表，见表3。

表3 原有原材料需求表

    表3作为物料采购部门的采购依据，购回物料入库后用来下料生产。可以看出，表3中数据并不能提供原材料的长度，而实际下料时原材料的利用率和长度的关系下分密切，例如，某次对40×3的角钢下料时，经过计算用6m和8m料混合最节省原材料，而由于[NextPage]此前依据表3采购的100t，40×3角钢是7m、8m、9m三种，缺少6m料，这就造成材料利用率降低，且由于7m和9m料得不到有效利用而造成库存积压。

    改进后的下料工作流程如图3所示，第一步，将待加工的工件明细表输入下料系统，将系统工作模式设置为原材料无限多，经过优化计算，得出最合理的原材料需求表如表4所示，作为物料部门购入原材料的依据；第二步，将工作模式设置为以库房现有原材料为依据，重新计算，打印输出下料单给生产车间；第三步车间根据下料单进行领料和生产，产生的可用余料重新入库，以备二次利用，把废料存入废料库。

图3 改进后的工作流程

表4 改进后的原材料需求表

    对比新、旧流程可以看出，最大的差别在于本下料系统可以给物料采购部门提供更合理的采购依据，据此进行下料可以得到更高的材料利用率，并改善了库存，同时增加了历史数据库以备查询，并对余料进行细化管理。

3 结 语

    本文研究并开发了基于改进BFD算法的多规格一维下料系统，计算结果接近最优解，且兼顾了实际生产的工艺性要求，同时引入流程再造的思想，改善了优化下料的工作流程，在成都某铁塔生产企业的实际应用表明，本系统的成功实施可以显著提高角钢利用率和下料的工作效率，并改善了库存状况。

    1.2 求解方法

    从组合优化的角度，此模型可视为装箱问题，采用启发式近似算法或遗传算法来求解。两种算法各有优缺点，单纯从数学的角度看，遗传算法的解更接近最优，但实践证明，会给生产带来很大的难度，而采用改进的BFD(Best Fit Decreasing)进行求解，可以得到与遗传算法非常接近的解，同时工艺性能得到了大幅提升。

    BFD算法的下料描述：工件按照降序排列，取出长度为Gk的工件，检查所有原材料当前余料，对余料按升序排列，将Gk放在第一个能容纳它的余料上进行截取。算法流程如图1所示。

图1 算法流程

    求解步骤为：

    1)读取库存原材料和待加工工件数据，对工件按长度降序排列G[k](k＝1，2，…，n)，见表1，数量分别为b[k]，对原材料按长度升序排列为Y[i](i＝1，2，…，m)，数量分别为a[i]。

表1 工件明细表

    2)构建数组ycl[s]＝Y[i]，yclnum[s]＝a[i](s＝1，2，…，m)，gj[z]＝G[k]，gjnum[z]＝b[k](k＝1，2，…，n)，判断数量大于零的原材料和工件的规格数p、q是否减至零，如果都不为零，则转步骤3)，否则转步骤5)。

    3)用数童大于零的原材料ycl[s1](s1＝1，2，…，p)进行“试截取”，得到p个余料，选取其中最小余料对应的那种长度的原材料Y[i]。

    4)用一根Y[i]进行正式截取，a[i]＝a[i]－1，当这根原材料已经不能丙截取任何工件或其上的工件种类c＞x时，剩余长度成为余料，统计本次加工出的工件，转步骤2)。

    5)刘一以上结果进行调整，检查余料中是否有长度大于最后一根原材料工件的，如果有，则把此工件放在该余料上，重复操作直到没有余料可以利用，则计算结束，输出结果(见表2)。表2中，序号为5、7的两组数据之所以c＝4就是这种调整的结果。

表2 下料结果

    1.3 下料示例

    为了便于对比，用李培勇在“多规格-维型材优化下料”中工件数据进行下料，具体见表1(表中长度单位均为mm)；所用原材料为6m、8m、9m三种，数童没有限制，结果见表2。

    “多规格-维型材优化下料”中采用混合遗传算法，共消耗原材料215m，最后一根余料长2764mm，虽然利用率稍高，但单根原材料上截取的工件种类数c往往超过6种，加工难度很大，实际上大规模下料时几乎无法进行操作。本文的算法消耗原材料也是215m，最后一根余料长1074mm，同种原材料内基本上按照工件编号的顺序进行下料，而且c绝大多数为3，这大大方便了工人实际下料时的操作，简化了工序。表2中，下料1的数据格式为：零件编号－零件长度×单根下料数量，例如01－2144×2表T单根原材料上编号为01，长度为2144mm的零件，下料数童为2个，下料2、3、4同理；表2中除原材料长度用m来表示外，其余均为mm。