水平型制造协作组织多目标订单分配优化模型研究.doc

水平型制造协作组织多目标订单分配优化模型研究程方启1 叶飞帆2 杨建国1（1.上海交通大学机械与动力学院 上海 2002402.宁波大学工学院 宁波 浙江 315211 ）摘要：水平型制造协作组织是由多个生产同类产品的企业组成的一种分散化的协作生产企业联合体。正确合理地在水平型制造协作组织企业成员之间进行订单分配，是提高制造企业敏捷性和竞争力的重要手段。针对订单分配问题，建立了综合成本最小化与生产负荷均衡的多目标函数模型。应用非支配排序遗传算法(NSGA-II)对多目标优化模型进行求解，获得了Pareto最优解集。仿真计算结果表明提出的模型和算法能获得满意的解。关键词：水平型制造协作组织 订单分配 生产负荷 NSGA-II 中图分类号：TH166 A multi-objective order allocation optimization model of horizontal manufacturing collaborative organizationFangqi Cheng1, Feifan Ye2, Jianguo Yang11. School of Mechanical Engineering, Shanghai JiaoTong University, Shanghai,P.R. China2. Faculty of Engineering, Ningbo University, NingBo, Zhejiang Province, P.R. ChinaAbstract: Horizontal manufacturing collaborative organization is a dispersed enterprise community consisting of several enterprises which produce the same kind of products. To correctly assign order among member companies of horizontal manufacturing collaborative organization is one of the most important ways to improve the agility and competitiveness of manufacturing enterprises. For the order allocation problem, a multi-objective optimization model is developed to minimize the comprehensive cost and balancing the production loads among the selected manufacturing enterprises. Non-dominated sorting genetic algorithm (NSGA-II) is applied to solve the optimization functions. The optimal solution set of Pareto is obtained. The simulation results indicate that the proposed model and algorithm is able to obtain satisfactory solutions. Keywords: horizontal manufacturing collaborative organization, order allocation, production load, NSGA-II71 引言 基金项目：浙江省自然科学基金(Z604342)作者简介：程方启(1970)，男，山东东营人，博士生，研究方向为敏捷制造及制造系统工程，E-mail: . 制造协作组织(Manufacturing Collaborative Organization, MCO)根据一定的制造任务，将地理上和组织上分散的制造企业伙伴组织起来，通过企业间的有效协作实现“共赢”的目标 1。 从资源共享的角度看，企业之间资源共享的类型可以分成“水平共享”和“垂直共享”两类2。“水平共享”的企业在产品的价值增值链中以一种“水平”关系存在，如对于需求量较大的同一类零部件需要寻找多个制造企业，则这多个制造企业之间形成“水平共享”的关系。也就是说水平共享的企业之间共同完成同一样产品或同一份订单。当某企业获得一定数量的产品订单，而受交货期及其资源的限制，需要将订单的一部分交给其他企业来完成。这就是水平型制造协作组织(Horizontal MCO, HMCO)的订单分配问题。向晋乾等3研究了横向型企业集团内部企业之间的订单分配问题，建立了利润最大化的单目标0-1规划模型。姬小利4从供应链出发，应用混合遗传算法研究了多产品、多订单、多时段的订单任务分配问题。Ruengsak 与 Nguyen 5 考虑了准时交货率，成本两个因素，优化订单分配以降低购买成本。Xiangtong 6 应用启发式算法与动态规划方法研究了在多个生产能力不同的供应商中如何分配数量一定的订单任务。Ezgi Aktar与 den stn 7把订单分配问题建模为多目标混合整数规划问题进行了研究。以上研究没有考虑制造企业的生产负荷因素的影响，且没有考虑需要在企业之间均衡分配订单数量。而候选企业的生产负荷对于伙伴选择及订单分配来说也是一项需要考虑的重要因素，并且生产负荷均衡在许多生产计划与调度问题中被认为是优化的准则之一8 9。因此本文引入了企业生产负荷影响因素，建立了负荷均衡的订单分配多目标优化模型。以便快速地进行订单分配，保证产品质量与交货期，使企业的制造资源最大程度的均衡，提高企业的资源利用率。2 订单分配问题建模面向多企业的订单分配问题要求盟主企业(获得订单的企业)在保证产品质量的情况下，需要按期交货。这就需要盟主考察其他潜在企业的生产能力和当前的生产负荷，来确定可以进行订单分解的产品数量。2.1 问题描述在生产同类产品的多个企业中，盟主获得一个大订单，依靠自身的能力不能完成。为了在预定交货期内完成订单，盟主会在本区域企业集群中选择合适的企业，组成HMCO，共同完成生产任务。除了考虑成本、交货期等影响因素外，企业生产负荷也是一个需要考虑的重要因素。如果仅仅按照企业具备的生产资源来分配订单，会造成资源冲突。即使该企业接受订单，也会受生产负荷的限制，不能很好地满足保证产品质量、按期交货的要求。考虑到各制造企业具有不同的生产能力以及当前的生产任务量，这里我们用生产负荷率(生产任务与最大生产能力的比率)来衡量各制造企业的生产状况。由于制造企业的生产活动过程是高度并行的，生产负荷率最大的制造企业将决定整个产品的交货期，要使产品的交货期尽可能短，生产负荷率最大的制造企业的生产负荷率应尽可能小。理论上，如果所有制造企业的生产负荷率都相等，则产品的交货期最短。所以各制造企业的生产负荷率应尽可能地接近生产负荷率，即制造企业的生产负荷尽可能均衡。在HMCO成员企业中均衡地分配制造任务订单，可以使各成员企业的生产负荷尽可能均衡，便于顺利地组织生产，更易于完成生产任务。由于各企业生产同类产品，安排的生产计划是并行的，所以，最迟完成生产任务的企业的生产时间就是实际交货期时间。2.2 多目标订单分配模型为了便于订单分配问题建模，考虑如下假设与参数：假设：(1) 订单需要的产品只限一种；(2) 不考虑数量打折情况。 参数及符号：i候选企业序号xi候选企业i的订单数量yi对候选企业i，获得一部分订单：yi=1; 不分配订单： yi=0.Ci对候选企业i，单位订单产品的成本Oi 候选企业i的定购成本PLi 候选企业i可接受的最低订单数量PUi候选企业i可接受的最高订单数量Li候选企业i的生产负荷率Pi候选企业i的当前实际的生产能力Qi候选企业i的产品合格率D订单产品的数量DLT交货期 多目标订单分配问题可以建模如下：目标函数1：综合成本最低 (1)目标函数2：选中的制造企业生产负荷差别最小(制造企业生产负荷率尽可能均衡) (2)约束条件： (3) (4) (5)公式(1)为优化目标函数1：综合成本最低。函数第一项：，优化产品生产成本最低；函数第二项：优化定购成本最低。公式(2)为优化目标函数2：选中的制造企业之间生产负荷率尽可能均衡。约束条件(3)确保分配给k个制造企业的订单产品数量之和满足顾客的需要。约束条件(4)表示分配给制造企业的订单数量在其可接受的范围之内。约束条件(5)表示有一个或多个制造企业得不到订单生产任务。3 多目标优化算法多目标优化问题中的目标函数往往是相互关联甚至相互矛盾的。通常并不存在唯一解，使其相对于所有的目标函数是全局最优的。而存在一系列解，其特点为至少存在一个目标优于其他所有的解，这样的解称之为非劣解，或Pareto解，这些解的集合即为Pareto最优解集，求解多目标优化问题的主要任务是求得该优化问题的Pareto最优解集。3.1 NSGA-II算法在众多多目标优化算法中，多目标遗传算法的应用研究最为广泛，遗传算法通过对一个种群进行运算操作，在一个进化代中可以得到多个Pareto最优解，因此，是求解Pareto最优解集的一种有效算法。NSGA是一种基于Pareto最优概念的多目标进化算法，由Srinivas和Deb10在1995年提出。他们将非支配排序思想引入遗传算法，把多个目标函数的计算转化为虚拟适应度的计算，用于求解多目标优化问题。NSGA的基本原理是基于对个体的多层分级实现种群的非支配排序，在选择操作执行前，群体根据支配与非支配关系排序，所有非支配个体被排成一类，这些个体共享虚拟适应度值，依此逐步对剩余的个体进行分级并赋予相应的虚拟适应度。NSGA-II算法是对NSGA算法的改进，由Kalyanmoy Deb等11提出。NSGA-II算法采用快速非支配排序算法、拥挤度比较算子和精英保留策略，克服了NSGA算法的计算复杂度高、非精英保存策略和需特别指定共享半径的缺点。NSGA-II算法流程如下：1:first_pop(pop,ns) 2:non_dominated_sort( )3:get_margins( )4:repeat5:add_children( )6:non_dominated_sort( )7:get_margins( )8:newpop and i 19while | newpop | + | front(i) | ns do10:newpop= newpop front(i)11:i i+112:end while13:missing ns- | newpop | 14:if missing 0 then15:margin_sort(front,i,margin)16:for j 1 to missing do17:newpop= newpop the jth solution of front(i)18:end for19:end if20:pop newpop 21:until stopping_criterion3.2 NSGA-II算法应用由于NSGA-II算法有以下优点：(1)模块化及柔性的结构, (2)一次运行可获得多个解，并且已成功应用于许多优化问题。所以本文选用改进的NSGA-II对订单分配多目标优化模型进行求解。w 染色体编码机制采用基于自然数编码方式，每一自然数代码串表示一条染色体。wi表示第i个企业获得的产品订单数量，i = 1, 2, k。则w = w1, w2, , wi, , wk表示一条染色体。则每条染色体就是多目标订单分配优化问题的一个解。w 操作因子在选择操作过程中采用了排序的方法。计算适值后同时更新个体的索引，使得较优的个体拥有较小的索引值。然后采用竞赛法确定参加繁衍的个体，并在排序的同时引入了删除算子。将种群中相同的个体删除，避免了高适值个体迅速占领整个种群而引起早熟。交叉算子采用循环交叉策略，确定参加繁殖的个体依次选索引为第i和第i+1(i =1, 2，N-1)的个体进行交叉，并将第N个体和第1个体交叉，这样共产生N个后代。 变异操作在交叉操作之后进行，对某个染色体进行变异操作同时确保变异后的个体在允许的取值范围内。w 终止迭代条件目前，多目标优化计算还没有标准的可靠的终止迭代条件。本文采用迭代到一定次数(N)后终止。4 算例分析为了验证所建立的多目标订单均衡分配优化模型及NSGA-II算法，本文研究了一个注塑机零部件生产任务订单分配问题。订单产品的数量D4500，预定交货期DLT30 (天)。应用供应商选择评价算法如AHP或TOPSIS等方法，首先确定候选企业的得分及排序。这里根据直接给出的候选制造企业排序表(表1)，结合候选制造企业参数表(表2)，计算订单分配问题。 表1. 候选制造企业排序候选制造企业序号得分排序ME 1ME 2ME 3ME 4ME 5ME 6ME 7ME 80.76780.61410.81450.30270.23650.59890.28130.698924168573表2. 候选制造企业参数 制造企业Pi(/D)Ci ($)Qi (%)Oi ($)Li (%)ME 1 (rank2)ME 2 (rank4)ME 3 (rank1)ME 4 (rank6)ME 5 (rank8)ME 6 (rank5)ME 7 (rank7)ME 8 (rank3)46675349555868702343342931284130959793949096949667925748867562584523689285517235根据表1、表2、订单产品的数量D以及预定交货期DLT，可以按照候选制造企业的排序、生产能力确定订单分配的制造企业。根据计算分析（表 3），可以确定在5个制造企业（ME 3，ME 1，ME 8，ME 2，ME 6）中进行订单分配。表 3. 最大生产能力排序制造企业最大生产能力最大累积生产能力12345 ME 3 ME 1 ME 8 ME 2 ME 6P3(1-L3)DLT = 508P1(1-L1)DLT = 759P8(1-L8)DLT = 1365P2(1-L2)DLT = 1547P6(1-L6)DLT = 853508：508759：1267+1365：2632+1547：4179853：508(5084500) 1267(12674500) 2632(26324500) 4179 (41794500)目标函数 1： . (6)目标函数 2： (7) 约束： 计算结果如图1所示。图中区域D中的5个解在表4中列出。可见，通过多目标计算，可以获得Pareto解集。决策者可以根据企业自身情况与市场调研结果确定最优的订单分配方案。由于在订单分配模型中考虑了企业生产负荷的影响，基于负荷平衡的订单分配准则可以是订单任务均衡地分配到制造企业中。图2表示按照订单分配方案10进行分配后各制造企业的生产负荷状况。可以看出，各制造企业的生产负荷都在0.88至0.98之间。图 2. Pareto解集表 4 区域D(图1)内订单分配结果解订单分配数量目标函数1 （1105）目标函数 2x1x2x3x6x8 8712130647278512251.47600.018809705130647278512321.47640.0171010662130046283212441.47730.0141311661130046282912481.47740.0137812656130846082512511.47880.01203图 2. 生产负荷状况(对应表4中解10)5 结论针对水平型制造协作组织存在的成员企业之间的订单分配问题，建立了一个考虑综合成本与成员企业之间的生产负荷均衡的多目标优化模型。应用NSGA-II算法进行求解，获得了问题的Pareto解集。决策者可以根据自身情况和市场状况选择决策方案。企业的生产负荷状况反应了当前企业的生产任务，影响企业生产任务的执行。因此，本文在订单优化分配模型中引入了生产负荷均衡的优化准则，算例的结果分析表明，企业之间任务的分配可使各制造企业的生产负荷相对均衡，以便快速地进行订单分配，保证产品质量与交货期，使企业的制造资源最大程度的均衡，提高企业的资源利用率。参考文献：1 Jagdev H, Browne J. The extended enterprisea context for manufacturing J. Production Planning and Control. 1998, 9: 21629.2 WangRunxiao, Luo Qi, ZhuMingqua. Study on partners selection modeling in virtual enterprise J. Chinese Journal of Mechanical Engineering. 2002, 38(10):28-30. (in Chinese)王润孝, 罗琦, 朱名栓. 虚拟企业伙伴选择的建模研究J. 机械工程学报. 2002, 38(10):28-30.3 XIANG Jinqian, HUANG Peiqing, WANG Ziping. Order Allocation Model Based on Profit Maximization Of Horizontal Conglomerate J. Journal of Southwest Jiao Tong Uninversity. 2006, 41(2):241-244. (in Chinese)向晋乾, 黄培清, 王子萍. 横向型企业集团利润最大化的订单分配模型J. 西南交通大学学报. 2006, 41(2):241-244.4 Ji Xiaoli. Order Allocation Model in Supply Chain and Hybrid Genetic Algorithm J. Journal of Southwest Jiao Tong Uninversity. 2005, 40(6):811-815. (in Chinese).姬小利. 供应链订单任务分配模型及其混合遗传算法J. 西南交通大学学报. 2005, 40(6):811-815. 5 Ruengsak Kawtummachai, Nguyen Van Hop. Order allocation in a multiple-supplier environment J. Int. J. Production Economics. 2005, 9394: 231238.6 Xiangtong Qi. Order splitting with multiple capacitated suppliers J. European Journal of Operational Research. 2007, 178: 421432.7 Ezgi Aktar Demirtas, den stn. An integrated multi-objective