基于综合作业顺序图的混合装配线平衡问题求解

基于综合作业顺序图的混合装配线平衡问题求解

0混合装配线平衡算法的研究在同一线上，可以在相同的钻孔线上连续混合不同类型的产品，结构相似且靠近工艺的产品。如果没有大量的仓库，它可以快速响应市场的变化。为合理、有效地使用混合型装配线,必须解决生产线平衡和生产排序两个主要问题。生产线平衡问题是将产品装配线上所有作业任务适当地分配到各个工作站中,使各工作站的作业时间接近生产节拍;生产排序问题是确定不同品种产品投入生产线的顺序。本文主要研究混合装配线平衡问题(Mixed-modelAssemblyLineBalancingProblem,MALB-P)。由于MALB-P需要考虑不同品种之间的相互影响,它比单品种装配线平衡问题(Single-modelAssemblyLineBalancingProblem,SALB-P)更复杂。随着混合装配线在现代工业生产中的广泛应用,MALB-P越来越受到国内外学者的重视。目前,对MALB-P的研究主要集中在两个方面:①对于给定生产节拍,最小化工作站数;②对于给定的工作站数,最小化生产节拍。前者适用于计划期产品需求量确定,通过适当的作业分配,最小化生产资源;后者适用于生产资源确定,通过适当的作业分配,最小化生产时间。无论哪一种情况,要达到生产线平衡都要解决作业任务的分配问题,使分配到各个工作站中的作业量均衡。但混合装配线上不同品种产品在所包含的作业任务和作业时间的差异,给均衡分配作业任务带来了困难。在目前的研究中,解决这个问题的方法主要通过如下步骤:首先由每种产品的作业顺序图得到多品种产品的综合作业顺序图,然后按照各品种需求比例,计算每个作业任务的平均作业时间,最后根据多品种产品的综合作业顺序图及每个作业任务的平均作业时间,将作业任务分配到各工作站。其实质是首先将多品种装配线等效为单品种装配线,然后按照求解SALB-P的方法求解MALB-P。对于多品种混合装配线,由于不同品种产品所包含的作业任务不尽相同,对同一种作业任务不同品种产品的作业时间也可能不同,MALB-P的上述解决方案只能实现生产线上各工作站的平均负荷平衡,而不能实现各工作站间瞬时负荷的平衡,从而生产线上会出现等待和阻塞现象,降低了工作站的工作效率。为此,求解MALB-P,不仅需要解决平均负荷的平衡问题,而且需要考虑瞬时负荷的平衡问题。目前,兼顾平均负荷平衡与瞬时负荷平衡问题的研究很少,文献求解MALB-P,设计了工作站数最少、各工作站间负荷均衡和工作站内不同品种产品的负荷均衡三个目标函数,从而兼顾了平均负荷平衡与瞬时负荷平衡,但目标函数中的空闲时间计算是以平均节拍为基础的,难以准确计算每种产品在一个工作站内作业的空闲时间。文献对给定序列的混合品种装配生产线平衡算法进行了研究,其优化目标是各工作站剩余工作总量最小,解决的是瞬时负荷平衡问题,但其数学模型的建立是基于假设:每个工作站内的工人只负责装配进入其工作区域的工件,当一个工人在某工件离开其工作区域时未能完成装配任务,将放弃并转而装配下一个工件,而原先工件剩余的工作量假定在进入下一个工作站前已被完成。这种假设对实际问题做了相当大的简化,距实际实施还有一定距离。本文从混合装配线平均负荷平衡和瞬时负荷平衡两方面对MALB-P进行了研究。首先,根据计划期对各种产品的需求量确定平均生产节拍,并计算最小工作站数,对MALB-P建立数学模型,将MALB-P等效为SALB-P,采用遗传算法求解,优化目标是各工作站平均作业时间的均方差最小,即使各工作站平均负荷尽可能接近;然后,对遗传算法求解的一组较优解,用eM-Plant仿真软件从装配线瞬时负荷平衡方面进行仿真研究;最后,设计综合评价指标,同时兼顾平均负荷平衡和瞬时负荷平衡,并依据综合评价指标确定最优解。1问题描述和数学模型1.1m种不同品种产品的综合作业顺序图MALB-P可描述为:M种产品(称为一种基型和多种变型的产品)在同一条装配线上同时装配。按照工艺要求,每种产品的装配所包含的作业任务都有一定的先后顺序约束,该约束可用作业顺序图描述。图1为产品作业顺序图的一个例子,图中a,b,c分别为产品A,B,C的作业顺序图。由于不同品种产品的作业任务不尽相同,其作业顺序图也不完全相同。为研究M种不同变型产品混合装配的生产线平衡问题,首先将每种产品的作业顺序图合成为综合作业顺序图,图2为图1所示三种产品的综合作业顺序图。一个综合作业顺序图包含了M种产品装配的全部N个作业任务,对于同一种作业任务,不同品种产品的作业时间可能不同,当一种产品的装配不包含其中某种作业任务时,则将该任务的作业时间视为零。然后,根据作业任务的先后顺序约束及一个最小生产循环内M种产品的平均作业时间,将作业任务分配到各个工作站中。分配方案不同,各工作站的作业时间也不同,装配线平衡问题是求解一种满足约束条件的作业任务分配方案,使装配线上各工作站负荷均衡,减少各工作站的等待或阻塞时间,提高生产效率。1.2各工作站的负荷均衡优化本文研究的MALB-P属于MALB-P的第①类问题,即对于给定生产节拍,最小化工作站数。首先根据计划期内装配线上总作业量确定工作站数的下限,然后在算法运行的过程中,根据负荷情况自动调整工作站数。设在一个计划期T中,对第m种产品的需求量为Dm(m=1,2,…,M),则对M种产品的总需求量D=Μ∑m=1DmD=∑m=1MDm,平均生产节拍CΤ=Τ/Μ∑m=1DmCT=T/∑m=1MDm。在一个最小生产循环中对第m种产品的需求量为dm,dm=Dm/r,r为D1,D2,…,DM的最大公约数,对M种产品的总需求量d=Μ∑m=1dmd=∑m=1Mdm。第m种产品第i个作业任务的作业时间为tim,则最小工作站数可由式(1)计算:Smin=Μ∑m=1dmΝ∑i=1timCΤ⋅Μ∑m=1dm∑m=1Mdm∑i=1NtimCT⋅∑m=1Mdm。(1)式(1)计算结果是工作站数的下限,在平衡问题求解中可能会由于作业任务在作业时间方面的原因,或不同品种产品的作业时间差异的影响,导致所需工作站数大于Smin。例如装配线上有较多作业任务的平均作业时间较长,接近平均节拍。在作业分配过程中,若当前工作站已分配了部分作业任务,但作业时间远不足平均节拍,按照作业先后顺序约束,当前可分配的作业任务的平均作业时间很长,因此在工作站平均作业时间不超过平均节拍的约束下,该作业任务不能分配到当前工作站中,只能分配到下一个工作站中,致使当前工作站的剩余时间较长,导致装配线所需工作站数增加,这时工作站数量Smin不能满足需求,或者虽然按照平均负荷计算工作站数量Smin能够满足需求,但由于不同品种产品作业时间的差异,使个别品种产品在某个(或某些)工作站的作业时间超出平均节拍,而平均节拍是根据生产计划计算出的,在这种情况下也需要调整工作站数量。因此,本文对平衡问题求解时,随着作业分配需求对工作站数进行调整,即首先以Smin为基础,在求解过程中通过对各工作站平均负荷和瞬时负荷的检验来修正工作站数。在装配线运行中,各工作站负荷均衡非常重要,因为当负荷较均衡时,各工作站的等待和阻塞时间较短,工作站的利用率较高,生产效率高;而当负荷不均衡时,各工作站的等待和阻塞时间较长,工作站的利用率低,生产效率低。因此,本文在最小化工作站数的同时,设计了各工作站负荷均衡的优化目标。以各工作站负荷均衡为优化目标的MALB-P可描述为:minJ1=√S∑k=1(Μ∑m=1qmΤmk-S∑j=1Μ∑m=1qmΤmjS)2SJ1=∑k=1S⎛⎝⎜⎜⎜⎜∑m=1MqmTmk−∑j=1S∑m=1MqmTmjS⎞⎠⎟⎟⎟⎟2S−−−−−−−−−−−−−−−−−−−−ue001⎷ue000ue000ue000ue000ue000。(2)s.t.S∑j=1xij=1,i=1,⋯‚Ν∑j=1Sxij=1,i=1,⋯‚N,(3)S∑j=1jxij≤S∑l=1lxkl,i,k=1,⋯‚Ν,(4)Τmj=Ν∑i=1tmixij,m=1,2,⋯‚Μ,j=1,⋯‚S,(5)Μ∑m=1qmΤmj≤CΤ,j=1,⋯‚S,(6)xij∈{0,1},i=1,…,N,j=1,…,S。(7)式中:qm为第m种产品需求量占所有产品总需求量的比例,即qm=Dm/D(0≤qm≤1,Μ∑m=1qm=1)。目标函数(2)的优化目标是各工作站负荷的均方差最小,即各工作站负荷尽可能接近。约束条件(3)确保每个作业任务只能,且必须安排在一个工作站中;约束条件(4)确保作业任务的安排满足作业优先顺序,其中i是k的紧前任务;约束条件(5)计算第m种产品在工作站j中的总作业时间;约束条件(6)确保每个工作站的平均负荷不超过平均节拍CT;约束条件(7)给出了xij的取值范围,当第i个任务被安排到第j个工作站时,xij取值为1,否则取值为0。2装配线上各工作站的目标函数式(2)～式(7)所描述问题的解是一种作业任务的分配方案,即将混合装配线上的作业任务,在满足作业先后顺序及各工作站的平均负荷不超过平均节拍的约束条件下,分配到装配线上各个工作站中,使目标函数(2)达到最小。该问题是NP难题,因此本文采用遗传算法对问题进行求解。2.1基因串编码与解码基因串编码为一长为N的数据串,每一基因座的序号对应作业任务序号,基因座上的基因值表示该作业任务被分配到的工作站的编号,图3所示为一基因串编码与解码的例子。2.2任务集合及可行解编码将N个作业任务安排到S个工作站,需要满足作业先后顺序及各工作站的平均负荷不超过平均节拍的约束条件。初始种群由一组个体组成,这些个体是一组可行解的编码。产生有效个体基因码(其所表示的解是满足约束条件的可行解)的思路是,首先随机产生一个满足约束条件的解,然后对该可行解进行编码。具体步骤如下:步骤1设个体计数器count=1。步骤2随机产生一个可行解:(1)装配作业任务集合TA={ta1,ta2,…,taN};(2)根据综合作业顺序图,记录每一任务tai的紧前任务数目ni;(3)根据综合作业顺序图,给出每一任务taj的后续任务集合{bj1,bj2,…,bju},其中u为任务taj的后续任务数量;(4)设当前工作站为stp=st1,即初始化为第一个工作站,其中p(p=1,2,…,S)为当前工作站编号;(5)设循环计数器cc=1;(6)从集合TA中随机选择一个紧前任务数为零的任务安排到当前工作站stp中;(7)检查分配给当前工作站的任务的累计平均作业时间是否超过上限值(CT),若超过则取消最后一次的分配,转到(9),否则,转到(8);(8)根据(2),(3)和(6),修改相关任务的紧前节点数目;(9)cc=cc+1,如果cc≤ccmax转到(6),否则,转到(10),其中,ccmax为作业分配循环次数,NSmax≤ccmax<N,NSmax为装配线上一个工作站内所分配的作业任务数的最大值;(10)p=p+1,若p<S转到(5),否则转到(11);(11)剩余的任务安排到工作站sts中。步骤3对步骤2产生的可行解进行基因编码。步骤4count=count+1,如果count≤popsize,转步骤2,否则转步骤5。步骤5结束。2.3适应性函数2.3.1-j1-j1因为文中数学模型为最小值问题,所以适应度函数设计为f(J1)=1-J1μ。(7)式中μ为不小于J1max的常数。2.3.2遗传操作期适应度尺度变换在遗传算法运行的初期阶段,种群中个体适应度相差比较大,可能会有少数个体适应度比其他个体适应度高出很多,按照轮盘赌选择方法选择时,这几个高适应度个体在下一代种群中将占很高比例,降低了种群中个体的多样性,很容易陷入局部最优。因此,在遗传进化的初期应降低适应度尺度,以降低种群中个体适应度的差异程度,从而限制高适应度个体的复制数量,维护种群中个体的多样性。在遗传运行的后期阶段,种群中个体的平均适应度接近最佳个体的适应度,即种群中个体适应度比较接近,在遗传操作中,个体之间几乎没有竞争性,影响了对最优解的进一步搜索。为此,在遗传进化后期应提高适应度尺度,放大个体适应度间的差异,以提高个体之间的竞争性。本文采用的适应度尺度变换式为:f′(J1)=fav(J1)+y[f(J1)-fav(J1)]。(8)式中:fav(J1)为种群中个体平均适应度;f(J1)为原适应度;f′(J1)为尺度变换后的新适应度;y为尺度变换系数,是进化代数的函数:y=ymin+ymax-ymingen-1(g-1)。(9)式中:g为进化代数;gen为最大进化代数;ymin和ymax分别为y的最小值和最大值。从式(9)可以看出,y随g线性变化,当g=1时,y取最小值;当g=gen时,y取最大值。采用式(8)和式(9)进行适应度尺度变换,在遗传操作初期,适应度尺度最小,降低个体适应度的差异,维持种群中个体的多样性;随着进化过程的进行,适应度尺度呈线性增加;到进化后期,适应度尺度为最大值,使个体适应度间的差异放大,有利于进一步搜索最优解。2.4选择和坚持2.4.1适应度排序及复制选择操作采用最优保存策略和轮盘赌选择相结合的方法。首先将种群中的个体按照适应度由高至低排序,然后将适应度排在前列的若干个个体直接复制到下一代种群中,其余个体采用轮盘赌法选择。这种选择方法既保存了种群中的优良个体,又不降低种群中个体的多样性。2.4.2作业顺序约束交叉操作是从经过选择操作的个体中随机选两个个体,按照交叉概率pc进行交叉操作。MALB-P对遗传算法交叉操作的要求是:任意两个个体基因串经交叉操作后产生两个有效的个体基因,即这两个基因串解码结果是满足作业先后顺序约束的可行解。采用常规的单点或多点交叉很难保证所产生的新个体是有效的。例如,图4所示为多品种混合装配的综合作业顺序图,图5所示的两个基因串ch1和ch2分别表示两种不同的作业分配方案。如果ch1和ch2进行单点交叉,则得到ch1′和ch2′,如图6所示。ch1′和ch2′的解码结果如图7所示,由图7a可见,由于任务11和15被安排在第一个工作站内,不能满足作业先后顺序约束,故编码ch1′没有实际意义,是一个无效的基因。本文采用交叉后检验和修正的方法,保证解的有效性,即对交叉操作所产生的新基因串,按照作业先后顺序约束进行有效性检验,并对无效基因串进行部分作业任务的重新分配,将其调整为有效基因串。例如,对图6中的基因串ch1′进行调整,将任务11调整到第二个工作站;将任务15调整到第四个工作站,经过修正的基因串ch1″为有效基因,如图8所示。2.4.3体基因串上随机随机选择多个基因座上的基因按照pm变异概率进行变异操作。首先,在种群中随机选择一个个体,然后在该个体基因串上随机选择两个基因座,对这两个基因座上的基因值以概率pm进行交换。这种变异操作也可能产生无效个体,因此变异操作后,需要对新个体进行有效性检验,对于无效个体,通过重新分配部分作业任务来加以修正,使其成为有效个体。2.4.4显传统法参数的选择(1)增加个体多样性种群大小size表示种群中所含个体的数目,size选择较大时,可增加种群中个体的多样性,但算法的运行速度较慢;而size选择较小时,虽然可提高算法的运行速度,但降低了种群中个体的多样性,容易产生遗传算法的早熟现象,因此size取40～100较为合适。(2)对最优解的搜索交叉、变异参数是遗传操作的重要参数,影响对最优解的搜索性能。当交叉、变异概率pc和pm选择较小时,会影响到种群中个体的多样性,容易陷入局部最优;而当pc和pm选择较大时,可能会破坏种群中的优良个体,使种群中平均适应度下降,影响对最优解的搜索。因此本文采用变参数策略,按照参加交叉、变异的个体适应度分三种情况选择交叉、变异参数:①对种群中最优个体选择,交叉、变异概率选为0,即不参加交叉、变异操作,直接复制到下一代。②对适应度高于种群平均适应度的个体,交叉、变异概率依个体适应度与平均适应度差值大小在pc1,pm1与pc2,pm2之间线性变化,其中pc1,pm1为交叉、变异概率的上限值,pc2,pm2为交叉、变异概率的下限值。个体适应度与平均适应度的差值越大,说明该个体的适应度较高,选择的交叉、变异概率越低;而个体适应度与平均适应度的差值越小,说明该个体的适应度相对较低,选择的交叉、变异概率越高。③对适应度低于种群平均适应度的个体,选择较高的交叉、变异概率(pc1和pm1)。3装配线运行仿真研究采用遗传算法求解MALB-P时,力求分配给各个工作站的作业量尽可能接近,但混合装配线上不同品种产品装配所包含的作业任务和作业时间上的差异,使不同品种产品在同一工作站中的作业时间可能不同,同一品种产品在不同工作站中的作业时间也可能存在差异,以至于装配线瞬时负荷难以平衡。装配线瞬时负荷的不平衡,导致工作站等待和阻塞率增加,利用率降低。而瞬时负荷的平衡问题很难用数学模型描述与求解。为此,本文通过仿真的方法对混合装配线瞬时负荷平衡问题进行研究。采用离散事件系统仿真软件eM-Plant对遗传算法求解的一组较优解进行仿真研究,每个解代表一种作业分配方案,通过仿真研究,分析每一作业分配方案下装配线的瞬时负荷平衡情况。图9为应用eM-Plant对多品种混合装配线建模的一个例子,生产线上有workstation1,workstation2,workstation3和workstation4四个工作站,产品从Entrance流入,从Exit流出。EventController是事件控制器,通过事件控制器来控制事件发生时刻。ProcTime1,ProcTime2,ProcTime3和ProcTime4分别用于对上述四个工作站设定作业时间。每个产品在一个工作站中的作业时间等于该产品在该工作站中所需完成的全部作业任务的作业时间总和。由于不同品种产品包含的作业任务有所不同,而且对于相同的作业任务,不同品种产品的作业时间也可能不同。仿真研究就是将第2章遗传算法的求解结果在仿真模型中加以实现。通过运行仿真模型,研究各工作站间瞬态负荷的平衡性。具体实现过程是:首先,在ProcTimei(i=1,2,3,4)中,对遗传算法求解到的任务分配结果用Simtalk语言编程,定义分配到workstationi中的任务,以及每个品种产品所包含的任务和作业时间,以控制每种产品在各个工作站中的作业时间;然后,运行仿真模型,用Chart显示各工作站利用率、等待率和阻塞率等指标,Chart显示的仿真结果如图10所示。图10中的柱状图,显示出每个工作站工作时间、等待时间和阻塞时间的百分率,即利用率、等待率和阻塞率,反映出混合装配线瞬时负荷平衡情况。当装配线瞬时负荷不平衡率较高时,工作站就会产生较长的等待或阻塞时间,结果等待或阻塞率较高,利用率较低。图10a和图10b分别表示对两种不同的作业分配方案的仿真结果,图10a各工作站利用率平均值高于图10b,说明后者的装配线瞬时负荷平衡率低于前者。以各工作站利用率平均值J2作为评价混合装配线瞬时负荷平衡率的一个指标,当J2较高时,说明工作站的阻塞或等待率较低,瞬时负荷平衡率较高。式(2)给出的目标函数J1的优化结果使各工作站平均作业量均衡;评价指标J2反映了装配线瞬时负荷平衡率,因此综合优化目标函数设计为minJ=w1J1+w2(1-J2)。(10)式中w1,w2为权值。4生产效率较优分配模型设三种产品A,B,C在同一条装配线上混合装配,一天(8h或28800s)这三种产品的计划产量分别为DA=400,DB=200和DC=300。平均节拍CΤ=Τ/Μ∑m=1Dm=32s,三种产品的综合作业顺序图如图11所示,每个任务的作业时间如表1所示。在一个最小生产循环中,对每一种产品的需求量分别为dA=DA/100=4,dB=DB/100=2和dC=DC/100=3;对每一种产品需求比例分别为qA=4/9,qB=2/9和qC=1/3。用式(1)计算出工作站数量Smin=6。采用第3章介绍的遗传算法,求解的最优解如表2所示。从表中看出,各工作站平均负荷没有超过设计的平均节拍CT,说明按照平均负荷校验工作站数是满足要求的,因此求解过程中工作站数没有发生变化,即S=Smin=6。将求解结果输入到仿真模型中,进行瞬时负荷的校验,发现由于个别品种的瞬时负荷超过设计节拍,使装配线实际节拍达到36.5s,这种生产速率不能满足生产计划要求,需要增加一个工作站,以缩短装配线节拍。将工作站数调整为S=7,