基于流水线平衡的混合装配线排序模型

基于流水线平衡的混合装配线排序模型

0混合装配线上的品排序混合生产线必须解决两个独立而密切相关的问题：生产线平衡和产品序列。在以往的研究中,大多把混合装配线的平衡问题转化为单一装配线的平衡问题。产品排序问题是混合装配线研究的重点内容[1,4,5,6,7,8,9,10,11,12,13,14,15,16,17],混合装配线上产品排序主要涉及两个目标:负荷均衡化和平准化[7,8,10,11,12,14,15,16,17]。学术界对平准化目标的研究相对较多,但这些研究大都没有考虑流水线平衡的影响,而根据平准化的定义,物流的平准化应基于产品产出时间测定,流水线的平衡必然影响着产品的产出时间,即物流的平准化与流水线平衡存在着必然的联系。1计算d个产品排序的函数传统平准化模型可描述如下:混合装配线上生产M种产品,在一个时间段内,市场对这M种产品的总需求量为D单位,每个品种的需求量为Dm(m=1,2,…,M)单位,且Μ∑m=1Dm=D∑m=1MDm=D。传统平准化模型认为,在每种产品的加工时间是相同(不妨设为单位时间1)的假设下,等时间间隔地投入产品就会有等间隔的产品产出,而且生产D个产品的周期就为D时间单位。因此,传统平准化的研究实质是研究投入物流的均匀化,使各种产品的实际投入速率与理想投入速率大致相等。混合装配线上产品排序一般采用循环排序法。假设g为产品需求Dm的最大公因子,记dm=Dm/g,d=Μ∑m=1dmdm=Dm/g,d=∑m=1Mdm。把(d1,d2,…,dM)称为一个最小比例集,理论上,只对最小比例集中的d个产品排序,称为一个排序循环。实践中,重复排序循环g次,就达到了对D个产品排序的目的。引入0-1变量ymj,令ymj={1当排序队列中第j个位置上产品品种是m时0当排序队列中第j个位置上产品品种不是m时ymj=⎧⎩⎨⎪⎪⎪⎪⎪⎪⎪⎪1当排序队列中第j个位置上产品品种是m时0当排序队列中第j个位置上产品品种不是m时且有Μ∑m=1ymj=1∀j=1,2,⋯,d∑m=1Mymj=1∀j=1,2,⋯,d(1)d∑j=1ymj=dm∀m=1,2,⋯,Μ(2)式(1)保证在排序队列的一个位置上有且仅有一种产品;式(2)保证在排序队列的所有位置上,某一种产品的数量恰好为这种产品的需求量。在一个排序循环中,理想的投入速率即为需求速率,对于第m种产品而言,单位时间内的需求量为dm/d,用p=1,2,…,d表示产品排序队列中的位置序号(p=j表示产品排序队列中的第j个位置)。对于任意的整数p∈[1,d],在[1,p]内产品的理想投入量应为pdmd,实际投入量为p∑j=1ymj,实际投入和理想投入的偏差为Δ1=|p∑j=1ymj-pdmd|。对于第m种产品来说,传统的平准化模型要求对于任意的整数p∈[1,d],所有偏差Δ1=|p∑j=1ymj-pdmd|应尽可能地小,平准化的意义如图1所示。传统平准化模型的目标是使所有产品的所有实际投入和理想投入的偏差最小,因此目标函数为minΜ∑m=1d∑p=1(p∑j=1ymj-pdmd)2(3)传统的平准化模型是控制产品投入。在实践中,由于产品的差异化以及流水线中平衡延迟的存在,使得同一种产品在排序队列中的不同位置上加工时间不同,等时间间隔的均匀投入未必会产生均匀的产出。另外,物流的平准化应通过产出时间来衡量,而不应以投入时间来衡量。2线平衡方案的验证企业使用产成品(产出)而不是原材料和半成品(投入)来满足顾客的需求,因此,平准化应采用产品产出时间来衡量更为合理。流水线平衡是混合流水生产系统设计的源头,是决定产品产出时间的一个重要因素,100%的平衡是鲜见的,流水线平衡必然影响物流的平准化目标。考虑流水线平衡的平准化的思想是:在一个实际的排序循环中,从排序队列中第一个产品投入开始,到最后一个产品加工结束为止的制程(也叫制造周期、排序长度)内,每个产品的产出速率是均匀的。在流水线平衡方案确定后,如果一个排序循环对应的制程为T,其中第m种产品在T时间段内的产出量为dm,那么,单位时间的理想产出速率为rm=dm/T,则在制程T内的任意时刻t,第m种产品的理想产出为r*m=rmt=dmΤt(4)式(4)把平准化的衡量方式从传统的等投入时间间隔变为在制程T内不等的产出时间间隔。考虑流水线平衡的平准化实质是产出物流的均匀化,而且通过这种衡量方式将平准化与流水线的平衡结合起来更贴近问题的实际背景。在混合装配线上,不是对于每一个t∈[0,T]都有产品产出,在排序队列位置p上的产品加工结束时间就是这个产品在最后一个工作站(工作站K)加工结束离开流水线的时间,记为cKp。当t=cKp时,在t∈[0,T]内,第m种产品的理想产出为cKprm,而实际产出为p∑j=1ymj。因此,当排序队列中位置p上的产品产出时,第m种产品的理想产出与实际产出的偏差为Δ2=|p∑j=1ymj-cΚprm|‚这里,偏差Δ2的含义见图2。因此,考虑流水线平衡的平准化排序的目标为minΜ∑m=1D∑p=1(p∑j=1ymj-cΚprm)2(5)考虑流水线平衡的平准化模型与传统的不考虑流水线平衡的平准化模型的区别在于:考虑流水线平衡的平准化模型考虑了产品加工时间的差异,采用产出时间而不是投入时间来衡量产品的产出速率,把混合流水线的平衡与产品排序有机地结合起来。考虑流水线平衡的平准化模型为minΜ∑m=1D∑p=1(p∑j=1ymj-cΚpdmΤ)2s.t.Μ∑m=1ymj=1j=1,2,⋯,dd∑j=1ymj=1m=1,2,⋯,Μ3数值分析3.1平衡方案对比以Jackson问题为例,在一条混合装配线上生产一族规格相似的系列产品A、B、C,在某一时间段内,A、B、C三种产品的需求分别为1280单位、640单位、1280单位。假设设计节拍为12时间单位,三种产品的优先图分别为图3a、图3b和图3c,联合优先图为图3d,作业元素的时间在图中作业元素的右上角。假设流水线上工作站数K=4,给定两个平衡方案,见表1。在表1中的平衡方案下,不同产品在各个工作站内的加工时间是不同的,对两个平衡方案来说,产品A、B、C在4个工作站内的加工时间(负荷)见表2、表3。按照Thomopoulos的方法计算这两种平衡方案对应的平衡延迟BD,平衡延迟是衡量流水线不平衡程度的一个指标,这个指标越小,表示流水线平衡程度越高,当平衡延迟为零时,流水线达到100%平衡。平衡方案1对应的平衡延迟为BD=(12-10.4)+(12-11.6)+(12-10.2)+(12-7.6)12×4=17.1%平衡方案2对应的平衡延迟为BD=(12-9.8)+(12-4.6)+(12-7.6)+(17.8-12)12×4=41.3%显然,按照平衡延迟来衡量流水线的效率,流水线在平衡方案1下比在平衡方案2下的平衡效果好。在平衡方案1下,求解目标式(5),可得考虑流水线平衡的平准化的最优产品排序方案为C→C→B→A→A,目标函数为60.12。在平衡方案2下,求解目标式(5),可得考虑流水线平衡的平准化的最优产品排序方案为C→A→B→C→A,目标函数为62.00。采用目标追迹法,求解目标式(3),可以求得不考虑流水线平衡影响时平准化的最优产品排序方案为A→C→B→A→C,相应的目标函数为63.2。由此可见,工作站中不同产品操作时间的差异性对排序结果有显著影响,考虑流水线平衡的排序模型更贴近实际背景。3.2最优排序的确定仍然以上述Jackson问题为例来进行比较,采用循环排序法,只对5个产品排序,5个产品的所有可能排序为5!/(2×2)=30种。传统模型的思路是:假设每个工作站中每个产品的加工时间是完全相同的,排序时不考虑实际操作时间的差异性。优化目标函数式(3),采用列举法可以得到关于目标函数式(3)的最优排序为A→C→B→A→C。实际上,不同工作站中的不同产品的操作时间是有差异的,我们从所有可能的平衡方案(作业元素的分派顺序共有103个,对应着24种平衡方案)中,挑出工作站负荷最均衡的一个,该方案对应的工作站中的作业元素分别为{1,3,4},{2,5},{7,8},{6,9},与传统模型的最优排序结合起来计算目标函数式(5),可得结果为61.8658。考虑流水线平衡的排序模型的思路是:把24种平衡方案与30种排序方案一一组合,共有720种方案,在每一种方案下,计算目标函数式(5),可得结果为60.1237。对应的最优平衡方案中的作业元素分别为{2,5},{1,3,4},{6,7},{8,9},最优排序方案为C→A→C→B→A。通过对比可知,不考虑流水线平衡影响的传统模型仅仅是一种理想的模型(现实中是鲜见的),考虑流水线平衡的平准化排序模型能够得到更好的优化结果。4考虑线索平衡的平准化模型混