1 引言
九十年代以来，市场竞争的不断加剧、产品的多样化和更高顾客化需求给企业带来了很大的压力，企业越来越意识到在生产过程中引进操作柔性的重要性。一台SMC插置机器可以通过增加插头或者在插头上增加可以插接不同元件的取件器而提高自身的操作柔性。而一条装配线通常通过安装不同的插置机器使其能够生产不同种类的产品类。
从1990年代以来，关于FMS生产能力调整问题已经有了相当的研究。文献[2]提出了一个在多产品背景下，多种技术可供选择时的生产能力扩充模型，正如他在文中所述，这个模型的一个主要的局限在于需求不减的假设和柔性生产能力只生产特定的产品类的假设。文献[3]研究了在多计划期多种机器生产单产品类，并且设备规模离散时，生产能力的扩充、缩减以及替换的策略。文献[4]和文献[5]研究了生产能力扩充的最优策略，尽管在模型中考虑了刚性设备和柔性设备之间的选择，但是，他们的模型和求解方法不能直接应用到PWB装配线问题上，文献[6]研究了不同计划期上需求变化且多产品类背景下，刚性设备和完全柔性设备之间的权衡问题。文献[7]随后在随机多种需求情形以及产品生命周期不确定的背景下将其结果进行了扩展．文献[8]用一类模型来比较在不同的生产环境和控制策略下，产品的多样性和生产的过程柔性对于生产的影响．这和本文的模型有一定的类似之处，但是要指出的是他们并没有考虑产品的结构，也就是产品的BOM约束．文献[9]研究了需求随时间变化的情形下生产能力的扩充问题，他们以最小化新设备投资成本、设备运作成本和库存成本为目标，提出了一个多阶段的混合整数规划模型，并且通过Lasransian松弛的方法来寻找有效的新设备投资计划。文献[10]考虑了在一系列离散的需求情形下，并在广定的投资约束下购买新设备，以未满足需求最小化为目标建立了一个随机整数规划模型。他们找到了一个不随需求变化的购买设备的集合，在该集合中选择购买设备，可以以最小的投资成本满足最大的需求．在多计划期，多产品类，需求确定但会随不同计划期发生变化的情况下，文献[11]提出了一个PWB装配线能力扩充的模型，该模型考虑了机器的柔性以及产品的BOM约束．文献[12]在该基础上扩展到随机的多种需求情形下的生产能力扩充问题，提出了一种通过求解多个背包问题来分解原问题的方法。但是，文献[12]只研究了能力扩充问题，而没有考虑能力缩减以及能力转移问题，当考虑能力缩减以及能力转移时，无法用背包问题来描述能力调整，需要开发其他的算法来求解这一问题．本文将研究随机多种需求情形下的生产能力调整问题，在这种不确定的情形下进行生产能力的调整，将会带来风险，因此在模型中将加入对于风险的描述，本文提出的求解方法不仅仅解决能力扩充问题，而且还能够得到完整的能力调整决策(包括设备拆卸以及设备转移)。
文章的结构如下：第2节提出了PWB装配线的一个能力规划模型；第3节提出了减少搜索空间的一个启发式算法，得到模型的调整略集；第4节运用遗传算法对调整略集进行搜索；第5节通过实例验证了本文方法的正确性和可行性；第6节为文章的结论部分。
2 BOM约束下的能力规划问题
本文将要考虑随机需求下的能力规划问题，在多个时间段上需求有多种可能情形，在这种不确定的情形下进行生产能力的调整，将会带来风险，因此在做出能力调整决策时，需要考虑两个目标，即最大的期望收益和最小的风险．在文献[13]的FMS能力规划模型中，运用期权定价的方法描述了风险，本文也将采用这种方法表述风险。
具体模型眠如下，其中的符号和参数见表1。
表1 模型中的符号和参数
上述模型加入了对于风险的描述，其中r是带有风险的收益率(投资报酬率)，a为年期望风险收益率(风险贴水)，α = r－rf，rf为无风险利率。模型中(1)式为目标函数，前三项是装配线的调整成本，分别对应于调整新机器、拆卸已有机器、转移机器的成本，第四项和第五项为期望的外包成本和期望的生产成本之和。(2)式和(3)式为能力约束，分别要求每台机器的总插置数不超过其总能力和第i种元件的生产计划不超过每台机器的能力。(4)式为BOM约束，要求每个产品类必须在同一条装配线上完成，也即要求每条装配线上产品类的元件生产计划必须满足BOM约束。(5)式为需求约束，要求每种元件的生产计划不能超过需求。(6)式为投资预算约束，要求调整新设备的总投资不能超过预算。(7)式为非负和整数约束。
模型M0是一个大规模混合整数规划问题，一个实际的问题如18条装配线用5类元件制造3个产品类，每条装配线计划期初平均有6台插置机器，可选用的机器种类为40，计划期(两年)被等分为8个时间段(季度)，则模型有159，840个对应于生产计划的连续决策变量，106，560个对应于装配线调整的整数决策变量和297，224个约束．该模型无法直接进行求解。
3 减小搜索空间的略集求解方法
如上节所述，一个实际的问题中含有106，560个能力调整整数决策变量，但是事实上可能只是某几种机器加到某几条装配线上，也就意味着很多整数决策变量的值为零．一个直观的解释是，对于每一条装配线，由于生产要满足需求和成本约束以及产品类的BOM约束，同时考虑装配线上已有的机器，某些种类的机器加到该条装配线上是不可取的。因此可以通过一些启发式算法把这些不可取的决策变量从搜索空间中去掉，本文先求解模型M0，得到一个对应于每个时间段每条装配线需要加某些机器的集合(称为增装略集，略集中的每一个元素表示在某个时间段上某种机器加到某条装配线是合适的)，然后应用一些规则对其进行修正，得到设备调整略集(包括增装、拆卸以及转移)，最后应用遗传算法(GA)搜索调整略集以得到问题的一个近似最优解。
用{A(t，m，Z)}表示时间段t上对应所有需求情形时第m种机器应该加到第z条装配线上的集合，{B(t，n，m，L)}表示时间段t上对应每种需求情形rt时第m种机器应该加到第Z条装配线上的集合，则集合{B(t，n，m，L)}可以通过类似于确定需求下增装略集的求解方法得到(具体算法见文献[11])．
在得到{B(t，n，m，L)}之后，如何得到{A(t，m，L)}，一个直观的方法如下：
(8)式实际上是一种求所有市场需求情形下的最大的增装略集的方法。
在确定调整略集时，虽然求得的{A(t，m，L)}是一个增加机器的集合，但是在多计划期时在该略集下求解，仍然会出现拆卸机器的情况，一个直观的原因是由于开始的计划期增加了较多的某种机器而导致后期的时间段上需要拆卸．基于这个原因，需要对集合{A(t，m，L)}作如下的修正：在确定每个时间段的调整略集时，都使它包含以前各期略集中相应的元素．同时由于求得的{B(t，n，m，L)}是每个时间段t上每种需求情形n下应该增加的机器集合，无法得到该时间段上该需求情形下应该拆卸的机器集合．解决这个问题的一个方法是，由于在计划期初存在一个初始的装配线布局，而考虑到机器的拆卸只能是对应于某时间段上某条装配线存在这种机器的情形，因此可以进一步的修正集合{A(t，m，L)：再在每个时间段集合的元素中，加入初始布局上存在的机器种类．做了上述两次修正后，可以得到最终的集合{A(t，m，L)}必然也包含了需要拆卸机器的集合．由于初始的装配线布局对于机器种类也是稀疏的，作如上的处理虽然会使问题的规模仍然较大，但是相比较原始问题而言，它仍然在很大程度上缩小了搜索空间。
当模型M0。的调整略集确定后，可以通过求解新的模型M1。来得到近似最优解．模型。只需把肘。中的(7)式替换成：
4 遗传算法搜索调整略集
应用遗传算法搜索调整略集，以下将主要介绍算法的编码方法和个体适应度评价方法，编码方法：
算法中染色体直接用0—20的十进制整数进行编码，在每一位整数前加一个符号位，“－”表示拆卸机器，“+”则表示增加机器。生成初始群体时，考虑到不增加任何机器(对应染色体的所有基因位为零)是问题的一个可行解，而且考虑到最优解对应的染色体的很多基因位将会为零，算法中将不增加任何机器总是作为一个初始解。其他的初始解将由系统随机生成，为了能够确保随机生成的初始解是问题的可行解，需要记录每一期的装配线结构，某一期的装配线调整决策变量必须以上一期的装配线结构为依据，只有当上一期装配线包含某种机器，对应于该条装配线的该种机器的基因才可能取负数，并且负数的绝对值不能超过原有机器的台数；其他的基因只能随机的取正数，这条原则在变异操作和交叉操作同样需要遵循。
个体适应度评价方法：
记MIN和MAX分别为某一代染色体中所有染色体对应的模型肘．的目标函数值的最小值和最大值，本文定义如下地适应度函数：
在(10)式中，Zˊ(y)是模型M1的目标函数值上增加超过投资预算的适应性惩罚因子P(g，y)后的总成本，g为遗传算法进化的代数，即
在(12)式中，参数α≥0，β＞0，y，g1>1与P均是可调参数，用以调整惩罚因子的大小．其中，g，>l的作用在于算法开始的若干代不考虑投资预算约束．y的值可正可负，若取正，则相对而言有缩小超预算后果的作用，反之则有放大超预算后果的作用．参数α>0的作用在于对投资预算的约束随进化代数的增加而要求越来越严厉。β>0是调整惩罚因子整体水平的参数，P为惩罚因子的上限。
在上述的染色体中没有基因位表示机器的转移，但是实际上由于编码时在整数变量前加了符号位，使得染色体中已经隐含了机器转移的情况．考虑到模型的形式和求解顺序，通过遗传算法搜索解空间，得到一个表示机器增减的解串，此时生产能力调整已经确定，然后再在此能力调整方案下求解一个生产计划问题(模型肘，的(2)式和(3)式)。
若一个解串只是考虑增加或者减少机器两种情况而不考虑机器转移的情况，则通过(10)式确定的适应度函数值偏高，而对于模型肘。中生产能力的约束没有影响．如对于某个时间段t某种机器m得到调整略集{A(t，m，1)，A(t，m，2)，A(t，m，4)}，即在第1、2、4条装配线上需要调整机器m，在遗传算法中用三个基因位表示。由于每个解串的每个基因位表示的是相应时间段相应装配线上相应机器的增减情况，则在求解生产计划问题时，只需要把这三个基因代入到能力约束((2)式和(3)式)中，即可得到时间段t上装配线的实际布局，也即对于模型M1．中的生产能力约束没有影响。
若某个染色体中这三个基因分别为a，-b和C(其中a，b，C均为大于零的整数，并假定a>b)，则暗示着在一个实际的调整方案是将第m种机器从第2条装配线转移b台到第1条装配线上，实际调整成本：
如果残值按照购买单价的30％计算，则C—Cˊ<70％Cp(t，m)<0，即通过遗传算法得到的适应度函数值偏高。同时可以看出，遗传算法得到的投资成本也偏高．解决这个问题的一个方法是，在评价一个染色体的适应度时，首先识别略集中t和m相同的元素，并同时识别是否存在机器转移的情况，如果存在，则需要根据(13)式计算生产能力调整成本以修正该染色体的总成本，并同时修正适应度函数值。
5 实例研究
5.1 小规模仿真实例
应用上述算法对随机需求下的装配线能力调整问题进行仿真计算．假设企业有2条生产线，共有3种机器可供选择，生产的产品类为2种，且共有3种元件组成各种产品类，计划期为2个(具体数据见文献[11])。
在上述的规模下，可以通过数学软件LP_solver直接求解，用Y(t，m，L)表示第t时间段上第Z条装配线第m种机器的调整台数，y(t，m，L)为正表示增加，为负表示拆卸，则可以得到最优解如下：
y(1，1，1)=1，y(1，1，2)=1，y(1，3，1)=3，y(1，3，2)=3，r(2，2，2)=-l，r(2，3，2)=-1，对应的总成本净现值为$1600767。
应用第三部分提出的方法求解得到的调整略集为(其中取δ=0.5)：A(1，1，1)，A(1，1，2)，A(I，2，2)，A(1，3，1)，A(1，3，2)，A(2，1，1)，A(2，1，2)，A(2，2，2)，A(2，3，1)，A(2，3，2)，其中一共有10个元素．再应用第四部分提出的遗传算法搜索略集，得到的最优解为：y(1，1，1)=1，y(1，I，2)=1，y(1，3，1)=3，y(1，3，2)=3，r(2，2，2)=-1，g(2，3，2)=一1，对应的总成本净现值为$1600767。
从上述小规模仿真计算的结果可以看到，通过求取模型M。的调整略集，使得遗传算法的搜索空间减少了(小规模问题减少了两个元素，效果不是很明显，但是对于大规模问题，搜索空间将会有较大幅度的减少)。同时可以看到通过计算得到的调整略集在减少搜索空间的同时能够较好的保持搜索空间的完整性，从而提高了算法收敛到最优解的可能性。
表2 生产线初始布局
5.2 大规模的仿真实例
某企业有12条生产线生产3个产品类．初始生产线布局如表2所示，共有20种机器可供选择，其特征如表3所示，产品类结构如表4所示，市场需求如表5所示，各种市场需求情形出现的概率如表6所示．根据论文[11]的略集求解方法得到机器增装略集如表7所示。
表3 可用机器特征
表4 产品类结构
表5 多时间段上市场需求情形
表6 各市场需求情形出现的概率
表7 时间段上的增装略集
应用本文提出的修正方法对增装略集进行修正得到设备调整略集，然后在相同的条件下进行十次计算，得到的十个收敛解中最差的个体对应的生产线调整决策如下(对应的总成本净现值为$31772412．oo)：
Y(1，2，4)=2，y(1，3，7)=10，Y(2，14，2)=1，Y(6，3，5)=7，y(6，3，7)=1，l，(7，3，2)=3，y(7，3，4)=5，Y(8，3，12)=1。
最优的个体对应的生产线调整决策如下(对应的总成本净现值$31720234.00)：
y(1，2，7)=3，l，(1，3，4)=4，l，(3，3，7)=5，y(4，3，7)=2，y(5，3，4)=6，y(5，3，5)=4，l，(6，3，8)=1．在上述实例中，十组解中目标函数值之间的最大误差为0．16％，可以认为已经收敛到了近似解，于是我们把这个最优个体作为企业最后的生产线调整策略。
5.3 算法的优越性
由于本文建立的生产能力调整模型是一个大规模的混合整数规划模型，目前还没有较好的方法进行求解，在已有文献中，标准遗传算法是一种较为常用的求解这一问题的方法．因此，我们将从计算时间和计算误差两个方面，把本文算法(记为HGA)的结果与标准遗传算法(记为SGA)的结果进行比较，以说明本文算法的适用性以及优越性．比较结果见表8，其中计算误差的计算方法为：当整数变量个数小于20时，原问题可以通过数学软件LP 80lvelr直接求解，此时最优解对应的最优值记为OPT，计算结果记为z(x)，则计算误差为：(z(x)一oFr)／OPT×100．当整数变量个数大于20时，由于此时无法得到原问题的最优解，因此通过LP solver求解忽略整数约束时的线性规划问题，得到最优解对应的最优值记为LB，则计算误差为：(z(x)—LB)，OPT×100．由于LB是原始问题最优值的下界，因此，算法的实际误差要低于该计算误差。
表8的计算结果显示：虽然本文的算法处理规模较小的问题时，计算时间与标准遗传算法相比不具有明显的优势(这主要是因为本文的算法在求解调整略集时需要花费一定的时间)，但是在计算精度上仍然要高于标准遗传算法。而当问题规模较大时(整数变量个数大于50)，本文的算法无论在计算精度上还是计算时间上都远远优于标准遗传算法，这说明了本文算法处理大规模混合整数规划问题的有效性以及优越性。
表8 不同规模的计算结果比较
6 结论
本文针对印刷装配板的制造过程，建立了一个基于多种需求状态的多计划期多种产品类的能力规划模型，该模型考虑了机器的柔性、产品类的BOM约束以及进行生产能力调整的风险。由于模型是一个大规模的混和整数规划问题，无法用一般的数学软件直接进行求解，本文提出了一种求解近似最优解的方法。首先减少装配线能力调整决策变量的搜索空间，然后应用遗传算法进行搜索．最后通过实例分析验证了该方法的可行性，并将计算结果与标准遗传算法的计算结果进行了比较。比较结果表明，相对于标准遗传算法而言，尽管该方法在处理小规模问题时不具有显著的优势，但是在处理大规模问题时，该方法在计算精度上以及计算时间上都远远优于标准遗传算法．因此，本文给出了一种处理大规模的多需求状态下多计划期多种产品类的能力规划问题的有效方法，为企业制定相应的能力规划决策提供了有力的支持。
核心关注：拓步ERP系统平台是覆盖了众多的业务领域、行业应用，蕴涵了丰富的ERP管理思想，集成了ERP软件业务管理理念，功能涉及供应链、成本、制造、CRM、HR等众多业务领域的管理，全面涵盖了企业关注ERP管理系统的核心领域，是众多中小企业信息化建设首选的ERP管理软件信赖品牌。
转载请注明出处：拓步ERP资讯网http://www.toberp.com/
本文标题：印刷装配板行业ERP系统考虑BOM的FMS生产线能力规划问题
本文网址：http://www.toberp.com/html/consultation/1082003716.html
相关文章
