基于产品交货期约束的合作关系优化模型

基于产品交货期约束的合作关系优化模型

1ve构建中的合作伙伴选择与优化问题有助于快速制造的实施，可以通过不同地理位置的公司之间的合作来实施。为了获得市场机遇，实现产品快速发展，一些制造公司之间成立了一个动态联盟，即虚拟公司（威斯）。在威斯克，每个核心公司之间有着加强合作的合作知识、信息和技术交流的能力，充分发挥各自的优势和创造能力，在最短的时间内以最低的投资完成产品的设计和制造过程，并快速市场引导产品。在VE构建中,合作伙伴的选择是一个关键的问题,它直接关系到VE的成败.在VE合作伙伴选择与优化中,必须权衡各方面因素,如成本、质量、交货期和风险等,对潜在的候选企业进行全面考察,从中选出最优化的伙伴组合.因此,在近几年的VE研究中,许多学者都在探索合作伙伴的选择与优化问题.由于合作伙伴选择需要考虑多方面因素,文献采用分层次比较法选优,考虑实际问题中的不确定因素,提出了一种新的模糊规划方法用于VE构建中的合作伙伴选择.文献考虑了制造和运输费用,通过网络优化模型,提出了一种有效算法,但由于问题的复杂性,没有考虑时间的约束.合作伙伴的选择对VE的运行风险也是考察候选伙伴的一个因素.文献提出了基于风险的VE合作伙伴选择问题,并采用遗传算法进行求解.文献采用分支定界法求解VE合作伙伴选择问题,考虑了项目的拖期惩罚,其优化目标是总成本最低.文献指出,高质量的产品是进入市场的先决条件,对许多企业来说,除高质量外,成本和时间是竞争的关键.文献提出了VE构建中基于成本和时间的合作伙伴选择优化问题,给出了一个两阶段求解算法.第一阶段通过一个多项式的精确算法求得最早完成时间的解,保证了解的可行性;第二阶段以最早完成时间作为可行初始解,利用一个启发式算法对解进行改进,最终使得在完成时间的约束下制造成本最小.本文在文献研究的基础上,采用遗传算法对问题进行求解.2企业核心能力对ve构建的意义每种产品的生产都需要经过产品设计、物料采购和生产制造的过程,而在生产制造过程中,每一道工序都需要相应的生产资源(机器设备和工作人员等),这些构成了企业的核心能力.核心能力是企业一组先进技术和资源的和谐组合,是响应机遇、参与竞争所依赖的能力.对于大而全的企业,依靠自身的核心能力足以完成产品的设计、物料采购、生产制造以及产品销售全过程.面对市场的快速变化以及对产品的需求由少品种、大批量向多品种、少批量甚至个性化的转变,这种大而全的企业显然无法应对这种市场需求的转型,因此,VE应运而生.在VE构建中,盟主首先将生产任务分成若干子任务,然后与潜在的合作伙伴协商,以获得必要的伙伴选择信息.2.1任务之间的相关关系制造任务的分解需要考虑资源的利用、生产计划和质量控制等因素,根据产品生产所需的核心能力类型进行任务分解.各任务之间的先后顺序关系由产品生产工艺决定.2.2心能力类型和生产时间VE构建过程中,盟主通过计算机网络发布招标信息,招标信息中给出所需核心能力类型、生产时间等信息.每个任务可能包含若干个子任务.投标者对其中某一任务进行投标时,须根据能力需求计划确定完成任务的时间段,在投标时申明任务的最早开始时间、所需要的制造时间以及完成该项任务所需费用.2.3模型设计原则根据招标和投标过程中所获得的信息,以及各任务的先后顺序,可建立描述伙伴选择的数学模型.由于各潜在合作伙伴的地理位置不同,在建模中,除了要考虑各潜在伙伴在投标中提供的制造费用、最早开始时间、制造时间外,还要估算出物料或半成品的运输时间和运输费用.现给出符号如下:I={1,2,…,m}——任务(节点)编号;Ti——任务i,i=1,2,…,m;Tij——任务i中的子任务j;Fi={fi1,fi2,\:,fiki}——任务Ti的投标者的集合,其中:ki表示任务Ti的投标者数量;fir∈{0,1}:1,投标者fir被选中完成任务Ti;0,投标者fir未被选中,r=1,2,…,ki;i=1,2,…,m.cir——投标者fir对任务Ti所投的制造费用;wirjh——将候选者fir所完成的任务Ti的物料(或半成品)送到fjh的费用,其中i≠j,j是i的紧后节点;Eijr——投标者fir对子任务Tij所投的最早开时间;pijr——投标者fir对子任务Tij所投的制造时间;Dijr——在虚拟企业构建过程中确定的由投标者fir完成子任务Tij的计划开始时间;sirjh——将候选者fir所完成的任务Ti的物料(或半成品)送到fjh所需的时间,其中i≠j,j是i的紧后节点;Dc——产品交货期.按照JIT(JustInTime)理念,提前生产和滞后生产都是不可取的,提前生产会导致库存增加,而滞后生产不能满足客户需求,失去信誉或商机.因此,本文考虑虚拟企业构建中合作伙伴的选择原则是在满足产品交货期的前提下,使制造费用和运输费用的总和最小.这一问题可以用下面的0-1型整数规划模型描述:minJ=m∑i=1m∑j=1ki∑r=1kj∑h=1wirjhδ(fir,fjh)+m∑i=1ki∑r=1cirfir,j是i的紧后节点.(1)s.t.ki∑r=1fir=1,fir∈Fi,i=1,2,\:,m;(2)fir∈{0,1},fir∈Fi,i=1,2,\:,m,r=1,2,\:,ki;(3)Dijr≥Dnhd+pnhd+sndir,∀j,h,i是n的紧后节点‚子任务Τnh先于子任务Τij,fir=1,fnd=1,fir∈Fi,fnd∈Fn;(4)Dijr≥Eijr,∀j,fir=1,fir∈Fi,i=1,2,\:,m;(5)(Dmjr+pmjr)≤Dc,∀j,fmr=1,fmr∈Fm.(6)minJ=∑i=1m∑j=1m∑r=1ki∑h=1kjwirjhδ(fir,fjh)+∑i=1m∑r=1kicirfir,j是i的紧后节点.(1)s.t.∑r=1kifir=1,fir∈Fi,i=1,2,\:,m;(2)fir∈{0,1},fir∈Fi,i=1,2,\:,m,r=1,2,\:,ki;(3)Dijr≥Dnhd+pnhd+sndir,∀j,h,i是n的紧后节点‚子任务Tnh先于子任务Tij,fir=1,fnd=1,fir∈Fi,fnd∈Fn;(4)Dijr≥Eijr,∀j,fir=1,fir∈Fi,i=1,2,\:,m;(5)(Dmjr+pmjr)≤Dc,∀j,fmr=1,fmr∈Fm.(6)式中,δ(fir,fjh)∈{0,1}:1,当fir=1,fjh=1时;0,其他.目标函数(1)为制造费用和运输费用的总和,约束(2)表示对每一任务必须从候选伙伴中选出其中一个,且只能选择一个加入虚拟企业中,约束(4)和(5)保证任务的先后顺序约束,约束(6)是交货期约束.3遗传计算方法的设计由于计算的复杂性,对上述数学模型直接求解有相当的难度,为此,采用遗传算法进行求解.3.1任务5生成fmxm由上述问题描述可知,对于任务Ti共有ki个候选伙伴,需要从中选出一个,且只能选择一个,因此采用自然数据串编码方式最为简单,即x=[x1x2\:xm]‚(7)x=[x1x2\:xm]‚(7)其中,1≤xi≤ki,i=1,2,…,m.编码(7)可解码为:f1x1=1,f2x2=1,\:,fmxm=1,即,xi表示对于任务Ti选择第xi个候选伙伴.例如染色体编码为[23516435]表示对任务T1,选择f12=1,对任务T2,选择f23=1,…,对T8,选择f85=1.3.2cost、完成时间节点为搜索满足交货期约束下,制造费用和运输费用的总和(即总费用)最低的VE合作伙伴组合,对应每一染色体编码需要计算出总费用cost和完成时间CT,cost计算公式如下:cost=m∑i=1m∑j=1wixi,jxjδ(fixi,fjxj)+m∑i=1cixifixi,(8)cost=∑i=1m∑j=1mwixi,jxjδ(fixi,fjxj)+∑i=1mcixifixi,(8)式中:δ(fixi,fjxj)∈{0,1}:1,j是i的紧后节点;0,其他.CT根据解码结果和约束条件(4)、(5)计算.3.3适应度函数设计由于目标函数为最小值问题,故定义适应度函数为:fit(cost)=1-cost-costmincostmax-costmin‚(9)fit(cost)=1−cost−costmincostmax−costmin‚(9)其中,cost为由公式(8)计算出的对应某一染色体编码制造费用和运输费用的总和(总费用),costmin为总费用的最小估算值,costmax为总费用的最大估算值,costmin和costmax适当取值,使0<fit(cost)<1.总费用cost越小,适应度fit越大,该染色体被选中可能性就越大.3.4数目和分子步骤设种群大小为popsize,种群中所有个体都是随机产生的,其算法如下:步骤1初始化,设数组k=[k1k2…km],其中ki表示对任务Ti的候选伙伴数目(i=1,2,…,m),令j=0,进入步骤2.步骤2j=j+1,若j>popsize,转入步骤5,否则,进入步骤3.步骤3令i=0,子步骤3.1:i=i+1,若i>m,转入步骤4,否则,进入子步骤3.2;子步骤3.2:产生(0,1)之间的随机数p,进入子步骤3.3;子步骤3.3:xi=「p*ki?,转向子步骤3.1.步骤4种群中第j个染色体popj=x,转向步骤2.步骤5种群ΡΟΡ=[pop1pop2⋮poppopsize]‚结束.3.5个体被入选的可能性初始种群生成以后,按照基本遗传算法就是对种群进行遗传操作,即选择、交叉、变异,经过设定的最大进化代数后停止.其中选择采用轮盘赌法,适应度高个体的被选中的可能性大;交叉采用单点交叉法.基本遗传算法通常得不到十分满意的搜索性能.对于本文提出的问题采用基本遗传算法存在两方面的不足:第一,本文提出合作伙伴的选择原则是在满足产品交货期的前提下,使总费用(cost)最小,按照公式(9)给出的适应度函数搜索的结果不能保证满足产品交货期的约束;第二,采用基本遗传算法搜索无论是最大适应度还是平均适应度都不甚理想,这一点在案例分析中得到了验证.为此,本文采用改进遗传算法.3.6改进的遗传算法改进遗传算法的基本思想是对种群中染色体进行过滤(染色体过滤法).首先计算出种群中每一个体所对应的产品生产完成时间(CT),剔出CT大于交货期的所有个体(即不可行染色体),再从剩余的个体中选出一些适应度高的个体,其数量等于不可行染色体的数量.使这些个体在种群中复制一次,以保持种群大小不变.其优点是,第一,种群中不再包含不可行染色体,从而保证搜索的结果满足产品交货期的约束;第二,用高适应度的染色体取代不可行染色体,使得高适应度染色体在种群中所占比例增大,从而使选择操作中有更多的优良个体被选中,提高了搜索性能.改进的遗传算法操作如下:步骤1按照上述方法产生初始种群,种群大小为popsize,进入步骤2;步骤2令进化代数gen=0,设定交叉概率pc,变异概率pm,最大进化代数maxgen,进入步骤3;步骤3gen=gen+1,如果gen>maxgen转入步骤11,否则进入步骤4;步骤4计算种群中每一个体所对应的cost和CT,进入步骤5;步骤5将种群中每一个体所对应的CT与交货期Dc比较,若某个体对应的CT>Dc则从种群中剔出该个体,剔出的个体数量为dnum,进入步骤6;步骤6按照公式(9)计算出种群中每个个体的适应度,并从中选择dnum个高适应度的个体进行个体复制,以保证种群大小仍为popsize,进入步骤7;步骤7采用轮盘赌选择法进行选择操作,进入步骤8;步骤8随机配对,按照概率pc单点交叉,交叉点随机设置,进入步骤9;步骤9对个体的每一基因座,依变异概率pm指定其变异点,对每一指定的变异点的基因值由除该基因值以外的随机产生的[1,ki]之间的数值代替,进入步骤10;步骤10寻找种群中最大适应值maxfit和与之对应的最小费用mincost,计算种群的平均适应度avefit和平均费用avecost,转向步骤3;步骤11计算结束.种群中适应度最大的个体就是对应成本最低的个体,对其解码得到VE合作伙伴选择的最优组合.4任务3.2模架加工和原材料采购现以模具制造的例子来说明本文给出的遗传算法的应用.一个模具制造企业接了一个大型注塑模的订单,它需要大型铣床和磨床加工模架,以及在模架上进行相关加工;需要精密数控机床加工型腔和型芯;需要大型注塑机进行试模.型腔和型芯由镶块组成,一些镶块先要用数控机床加工出初步外形,再用电火花加工成精确外形.该企业不具备所有这些资源,需要组织VE来完成.这项生产任务根据所需核心能力可以分解成下列制造任务:任务1产品的三维造型、模具设计,包括型腔、型芯和电极的设计,需要有经验的模具设计人员和相关的CAD软件包.任务2模架的设计、模架制造工艺设计、模架加工制造以及在模架上进行相关加工,需要大型铣床和磨床.任务3型腔和型芯的工艺设计,NC编程及镶块的粗加工,需要数控机床.任务4电极的工艺设计,NC编程和加工,需要精密NC机床.任务5镶块的电火花加工.任务6其他零部件的设计和制造、模具装配,需要有经验的模具工人.任务7试模,需要大型注塑机.任务8根据试模结果进行修模,需要有经验的模具工人.如果某一任务需要原材料,那么原材料的采购包括在该任务中.任务之间的先后顺序关系如图1所示.公司决定任务1要由公司自己完成,其他的任务由合作伙