多品种流水线平衡问题的人力成本模型

多品种流水线平衡问题的人力成本模型

安装的流水生产线是一种高产、稳产的运行生产线，尤其是在产品的最终安装上。过去，设计的线条主要适用于单品种的大批量生产，没有灵活性，无法满足市场上多品种小批量的需求。基于订单生产的生产能力是未来制造业的发展方向，因此，在20世纪70年代和80年代，许多制造商设计并建立了多种生产混合生产线。考虑到工人在生产线上的负荷平衡，有许多采用在线生产的方法。所谓的在线生产平衡是指根据技术条件的限制，在生产线上组织和合理调整所有安装完成的过程，使每个工作场所（也称工作站）的负荷尽可能充足、平衡。流水线平衡问题最早由B.Bryton于1954年在他的硕士论文中提出,Salveson于1955年首先建立了单品种装配流水线的数学模型,并给出了模型的解法.目前流水线平衡主要应用于新建流水线的设计和现有流水线的优化与改进.从研究方向看主要集中在以下三个方面:(1)使流水线的循环时间最短;(2)使流水线的工作站数最少;(3)使产品单件成本最低.经过近50年的发展,现在已经有很多种流水线平衡方法,20世纪六七十年代的由Baybars、Ghosh和Gagnon提出的基于启发式算法的单品种的流水线平衡方法,Bowman等人提出的基于整数规划的优化搜索算法的单品种流水线平衡方法,Hadi和Erdal提出的二进制规则.较之于单品种流水线平衡问题,多品种装配流水线因为产品不同,使得各操作的差异性很大,从而不能制定出固定的工作站负荷.就此问题,DavidW.He和AndrewKusiak指出目前的多品种流水线平衡有以下三种方法:(1)通过库存调度与建立相应流水线的分支线方法;(2)制定产品的标准工序时间;(3)模块化生产方式.基于订单生产,就是企业的生产计划是以客户订单为驱动的一种生产方式,较之传统的生产计划制定,它主要有以下一些特点,即企业生产什么,生产多少,何时交货等都是由客户决定.因此,如何在满足客户要求的前提下,降低生产成本、提高利润就成为企业所面临的紧要课题.本文就订单生产条件下多品种装配流水线的平衡问题,给出一种以优化人力成本为目标的装配流水生产线的人力成本模型;并结合标准遗传算法,给出一种结合蒙特卡罗方法与启发式邻域搜索方法的混合遗传算法,来解决流水线平衡问题;最后结合实例数据给出验证结果.1基于订单的生产模式对企业生产组织提出更高的要求,开发生产设备,从生产设备和生产设备订单生产使得产品的产量与生产时间的波动性特别大,因此,较之传统的生产组织方式,基于订单的生产模式对企业的生产系统的柔性提出了更高的要求,如生产设备的柔性化、高效的物流调度、人员的多岗位适应性等.这样就对企业的生产组织提出了更高的要求,即如何根据生产订单配置生产人员,从而使得生产成本得到极好的控制.2安装一条完整的水线的劳动力成本模型2.1作业时间和作业频次N为总的产品种类数量;Pi为第i种产品的数量,i=1,2,…,N;Ti为产品i的生产节拍时间(TU);H为加工产品需要的人数;Li为第i位工人的人力成本率(MU/TU),i=1,2,…,H;WT为流水线的实际作业时间;S为流水线的作业班次.其中MU(monetaryunit)表示货币单位,TU(timeunit)表示时间单位.假设:(1)装配流水线的物料供应及时;(2)流水线的工人都可进行多工位操作;(3)操作之间不存在动作关联性;(4)基于产品的更新与作业变化周期较短,所以不考虑学习曲线的作用.2.2装配机器人的人力成本虽然很多的装配流水生产线都已经配置了现代化的作业工具,如定扭矩的自动扳手、自动监测的装配仪表等,但就整体而言,装配流水生产线仍以工人的手工劳动为主,这是因为现今产品的装配关系越来越复杂,而要完成如此复杂的操作是当今的装配机器人难以完成的.因此研究如何降低装配线的人力成本是极具现实意义的.2.2.1选择适当的节拍流水生产的一大特点就是按节拍生产,通过合理的人员配置与工位调整得到适当的流水线的节拍,是流水线平衡的主要问题之一.在得到流水线的节拍后就可根据下式计算流水线的实际作业时间.WΤ=Η×Ν∑i=1(Τi×Ρi).(1)WT=H×∑i=1N(Ti×Pi).(1)2.2.2工资的最小计算单位对流水线上工人人力成本计算是以该流水线的生产节拍来衡量的,尽管流水线存在各工人的负荷不是非常平衡的问题.每个操作工的技术水平和实际工龄的差别会造成每位工人的工资水平不一样.通常企业是按照员工的实际工作日来计算员工的工资的,即工资的最小计算单位是日.综合以上各种因素,我们用Li表示第i位工人的人力成本率(MU/TU),Li就等于该人月工资除以实际工作日数.我们知道,通过流水线平衡后产生的时间是很难满足整班次的安排的,所以在此还需考虑工人的加班成本,设工人的加班成本率为Le(MU/TU),所以生产N种产品的人力成本C为C=min{Η∑i=1[Li×S+Le×(WΤ-S)],Η∑i=1[Li×(S+1)]},(2)S=[WΤSΤ]-×SΤ,(3)C=min{∑i=1H[Li×S+Le×(WT−S)],∑i=1H[Li×(S+1)]},(2)S=[WTST]−×ST,(3)其中,式(1)中的ST表示标准工作时间的换算单位因子,通常我们用一班8h为标准,[A]-表示不大于A的最大正整数.2.3水线生产的人力成本基于订单生产的多品种装配流水线平衡的目标就是在满足订单的前提下,尽可能地降低流水线生产的人力成本.用数学的方式表达如下:minC=Η∑i=1[Li×S+Le×(WΤ-S)],s.t.WΤ≤ΟΤ,(4)minC=∑i=1H[Li×S+Le×(WT−S)],s.t.WT≤OT,(4)(4)式中的OT表示订单的交货时间.3采用混合遗传统计法调整装载水的平衡3.1线性关系和复配算法装配流水生产线平衡的目标就是在既定的优化目标前提下,使得流水线设置的工位数和配备操作人员合理,同时使得各操作工人的生产负荷尽量均衡,接近流水线的生产节拍,减少工人忙闲不均现象,使流水线按节拍运转和高效率生产.解决流水线平衡的算法很多,本文运用结合蒙特卡洛法与启发式邻域搜索的混合遗传算法.3.2基于遗传算法的自然遗传算子遗传算法是由美国J.Holland教授于1975年在其编写的《自然与人工系统中自适应》中系统提出的.它是一类借鉴生物界自然选择和自然遗传机制的随机化搜索算法.遗传算法的基本思想:首先产生一系列适合的所给问题环境的种群,用适应度评价指标对此种群进行检测,保留适应度高的个体,并结合各种遗传算子如选择、杂交、变异等对此种群进行遗传操作,产生下一代种群,如此循环,直到满足一定的条件.3.3第一代种群的产生:蒙特卡洛法蒙特卡洛法是以统计抽样理论为基础,利用随机数,通过对有关随机变量的统计、抽样实验和随机模拟,求得统计特征值作为待解问题的数值解.本文将采用蒙特卡洛法产生用于遗传算法的第一代种群.3.4组合优化的效率问题设有一非空的队列L={l1,l2,l3,…,ln-1,ln},该队列有元素顺序关系约束,且必存在li≠0.现要求把该队列分解成K个子队列,必须使得子队列的差异尽可能小,即使分组后的队列平滑指数SΙ=Κ∑i=1[Li-(Ν∑j=1lj/Κ)]2SI=∑i=1K[Li−(∑j=1Nlj/K)]2最小,其中,K、L、N是已知的,且有0<K<N.看到此问题,我们很自然就会想到组合优化中经典问题——背包问题(knapsackproblem),显然,此问题属于有多个背包的背包问题,此类问题属于NP完全问题,它的可行解空间规模为(CΚΝKN×K(N-K))/K!,当问题规模非常小的时候,用穷举法可以搜索到全局最优解,例如,当元素总数部不超过11,它的运算规模为105.当元素总数部不超过20,它的运算规模为109.因此,精确地求解此问题的全局最优解是不太可能的.针对此类问题,很多学者从不同角度提出了许多方法,如Bowman和White等提出的基于整数规划的算法,Gutjahr和Albracht提出的基于最短路径搜索策略的算法,Jackson提出的基于动态规划理论的优化算法.不过传统的各种算法都不同程度地制约于问题的规模,例如Bowman和White等提出的基于整数规划的算法的问题规模不能超过50项.遗传算法作为一种新型的、模拟生物进化过程的随机化搜索、优化方法,近十几年来在组合优化领域得到广泛运用,并已在解决许多经典组合优化问题中显示了良好的性能和效果.因此,我们选用遗传算法来解决此问题,以求在此类资源规划问题的算法方面做出一些探索.3.5混合遗产转让法3.5.1基于遗传空间的优化问题的编码编码遗传算法不能直接处理解空间的解数据,因此必须通过编码将它们表示成遗传空间的基因串结构.遗传算法的编码方式有很多种,如一维染色体编码、多参数映射编码、可变染色体长度编码等.在此我们采用二值的二维染色体编码方式,这样使得遗传空间与解空间的映射变得简单明了,同时二值的编码方式又使得其模式识别率达到最高.如N=10,K=5的自成组优化问题的一个基于遗传空间的第m个解Xm的具体编码如下:Xm=[10010000000000000011011000000000001010000000010100],xij={1,当lj∈Li;0,当lj∉Li;i=1,2,⋯,Κ,j=1,2,⋯,Ν.Xm=⎡⎣⎢⎢⎢⎢⎢⎢10000001000010010000000100000100010000010100001000⎤⎦⎥⎥⎥⎥⎥⎥,xij={1,当lj∈Li;0,当lj∉Li;i=1,2,⋯,K,j=1,2,⋯,N.3.5.2初始种群的生成和算法根据模式定理可知,遗传算法的搜索过程就是不断地游历解的编码空间的模式集,因此,选取恰当的初始种群能在一定程度上改善遗传算法的收敛速度.我们采用蒙特卡洛法产生初始种群,因为这样可从一定程度上保证初始种群的多样性,也就避免了后继的遗传法出现病态遗传的现象.具体做法先从队列L中选出最大的K个元素,分别分至K个子队列中,然后对剩余元素进行蒙特卡洛模拟试验,即把0至1的区向均匀划分成K个子区间,根据每次产生的随机数落在何区间,就把此元素归入对应的队列.如此往复产生适当数量的初始解.3.5.3遗传算法最优设遗传算法在搜索进化过程中一般不需要其它外部信息,仅用适应度函数来评价解的优劣.因为遗传算法只能求目标函数的最大值,所以,我们取适应度函数f(L)=SΙ1-Κ∑i=1[Li-(Ν∑j=1lj/Κ)]2.f(L)=SI1−∑i=1K[Li−(∑j=1Nlj/K)]2.3.5.4基于排序机制的策略遗传算法的遗传操作包括选择(selection)、交叉(crossover)和变异(mutation)三个基本遗传算子.在选择遗传方面,我们采用基于排序机制的策略,即根据种群各个体的适应度大小进行排序,使得适应度最大的排在第一,最小的排在最后.在交叉遗传方面,我们采用多段交叉策略,即把两个染色体基因中多段同时进行交叉.在变异遗传方面.我们采用逆转算子的策略,即以一定的逆转概率选择某一条染色体的基因进行逆转交叉.其中,结合融入问题知识的启发式方法进行邻域搜索,从而加快算法的收敛速度,改善标准遗传算法的性能(具体的应用实例见后文).本算法的基本流程如图1所示.4处理人力资源模型的方法根据人力成本模型,初步算出最优的人员配置计划,然后运用混合遗传算法算出实际的生产节拍,从而确定实际的人力成本.具体流程如图2所示.5使用实例和结论5.1混合遗传算法平衡在一条人工装配流水线上完成不同品牌轿车的后桥装配任务,这两种产品分别记为SAN、PAS,它们相应的操作集合如表1所示.所有工人都具有多工位作业能力,且所有操作时间均为统计值,物料配备充足.订单要求如下:生产PAS200件,SAN400件,生产时间为10h.所有员工的工资等级相同.即L=80元/d、Le=240元/d.根据产品的操作列表可知PAS的Τ[Τ1]=10∑i=1l1i=491.01T[T1]=∑i=110l1i=491.01(s),SAN的Τ[Τ2]=10∑i=1l2i=465.66(s).如此按上述人力成本计算算法进行运算得到结果如表2.此问题的算法规模分为1026与1023,理想的节拍时间为¯Τ[Τ1]=491.01÷10=49.101(s),¯Τ[Τ2]=465.66÷10=46.566(s).显然传统的排序方法对如此大规模的问题是很难得到令人满意的结果的.运用混合遗传算法分别在第13代与第6代就得到近似最优解,计算出平衡后的操作子集如表3所示.节拍时间分别为51s和48s.具体运算步骤为:(1)运用蒙特卡洛法产生初始种群;(2)进行邻域搜索;(3)进行遗传操作,分别得到PAS和SAN的近似最优解的适应度函数为fPAS13=29.26463,fSAN6=19.89676.WΤ=10×2∑ii=1(51×200+48×400)=29400(s),S=[8.178]+×8=8(h),C=860(元).5.2在混合遗