串行生产线中机器维修工人的任务分配问题研究

鄢超波 张雷

对于制造业来说,其产品主要来自于庞大的生产线系统,生产线的效率(吞吐率) 越高,企业效益往往也就越好.然而生产线中的机器会发生随机故障,当生产线中某一台机器发生故障时,如果该机器没有得到及时的维修,就有可能使得系统吞吐率下降,进而导致企业利润减少.本文假设一台机器故障时,只能由已分配的某一名维修工人进行维修,显然如果为每台机器都配备一名维修工人,那么所有的机器故障都会得到立即维修,企业的损失也就最小.然而,这样会导致维修工人在大多数时间都处于空闲状态,极大地增加了企业的用人成本.如何在保证串行生产线系统吞吐率的情况下,使用尽可能少的维修工人来完成机器的维修任务,本文称这样一个问题为串行生产线中机器维修工人的任务分配问题.

在生产线领域,已经存在有大量的资料,文献中主要通过排队论[1]、分解[2]、仿真和近似[3−4]等方法来对生产线进行研究.当前生产线领域的研究方向主要是生产线的性能分析和优化,例如生产线平衡问题[5−6]和生产线中缓冲区大小分配问题[7−8]等.然而,尽管在生产线这一领域已经有了很多研究工作,但是根据文献调研,目前还没有相关文献在研究串行生产线中机器维修工人的任务分配问题.这也就是说,本文所研究的问题是一个全新的问题.对于这样一个新问题,有三类问题与之具有一定相似性.第一类问题是任务分配问题[9],该问题要求定义每一个任务分配给任意一个人的“成本”,然而在本文所研究的问题中吞吐率是一个整体的性能指标,难以定义每一个机器的维修任务分配给任意一个工人的“成本”,所以不能应用分配问题的算法来求解本文的问题.第二类问题是装箱问题[10−11],该问题要求将一定数量的物品放入容量相同的一些箱子中,使得所用的箱子数目最少,然而由于无法定义维修工人的“容量” (单个工人可以负责维修的机器数量),所以也不能直接应用装箱问题的算法来求解本文的问题.第三类问题是并行机调度问题和文献[12]中提出的线边缓冲区分配问题(Line-side buffer assignment problem,LBAP),其中并行机调度问题要求使用一定数量的机器完成一些相互独立的任务,使得完成时间最短,而LBAP 问题则是要求在保证总装线吞吐率的条件下,使用给定数量的司机完成物料传送任务.由于第三类问题中的LBAP 问题与本文所研究的新问题非常类似,因此可以借鉴文献[12] 中提出的带回溯的序贯分配算法(Sequential assignment with backtracking,SAB),来求解本文所研究的问题.该算法基于并行机调度问题[13]中的最长处理时间优先(Longest processing time,LPT)算法[14−15]和回溯策略,是一种启发式算法.

本文的贡献在于:1) 本文提出了一个全新的问题—串行生产线中机器维修工人的任务分配问题,并对其进行了建模;2) 合理地定义了机器的维修工作量,使得本文所研究的问题可以类比为并行机调度问题;3) 通过仿真实验,验证了文献[12] 中提出的SAB 算法,对本文所研究的问题同样适用,该方法在保证系统吞吐率的前提下,能够有效减少企业的用人成本.

本文的结构安排如下:第1 节介绍串行生产线,建立问题模型和仿真模型;第2 节定义和量化机器以及工人的维修工作量,并对维修工人数量的下界进行估计;第3 节描述带回溯的维修工人任务分配算法;第4 节进行仿真实验,验证本文方法的有效性;最后对本文的内容和贡献进行总结.

1 系统模型

1.1 串行生产线模型

串行生产线是指:将机器以串行方式连接起来,并通过物料储运设备将工件从第一个机器输送到与它相邻的下一个机器的生产系统,如图1 所示,其中圆圈表示机器,方框表示物料储运设备(即缓冲区).在实际生产过程中,机器总是会发生随机故障(即机器不可靠),这些故障造成的影响会沿着生产线向上游和下游的机器传播.例如,当图1 中的机器m2发生故障时,其下游的机器m3不久便会加工完缓冲区b2中的所有工件,然后进入饥饿状态,同时机器m1则会在充满缓冲区b1后进入阻塞状态.如果此时机器m2仍然没有被修复,那么饥饿状态会继续向下游传播直至最后一台机器mM.类似的,阻塞状态也会向上游传播,这种饥饿或堵塞的情况越严重,串行生产线的吞吐率也就越低.

图1 串行生产线Fig.1 A serial production line

为便于分析串行生产线,本文做出以下假设:

1) 串行生产线的第一台机器不会由于原料短缺而发生饥饿,最后一台机器不会发生堵塞.

2) 机器mj加工一个工件所需的时间(即加工节拍) 为τj,j=1,2,···,M,且τj为一个常数.

3)缓冲区bj的容量为Cj,j=1,2,···,M −1,且Cj为非负整数.

4) 操作相关故障(Operation-dependent failure,ODF):机器只有在加工工件时才会发生故障,在阻塞或饥饿时不会发生故障.

5) 加工后阻塞(Blocked after services,BAS):一台机器如果处于工作状态,只要其上游缓冲区非空,就从中提取工件进行加工;如果加工结束时,下游缓冲区已满,则该机器被阻塞而暂时无法加工下一个工件,直到下游缓冲区有可用空间为止.

6) 用连续概率分布描述机器的可靠性模型,即用连续概率分布刻画机器的故障间隔时间和故障维修时间.如果机器的可靠性模型用负指数分布描述,则称为指数可靠性模型;此时,机器的故障率和维修率可以分别用λ和µ来表示.

1.2 问题模型

图2 给出了一个串行生产线中维修工人任务分配的例子,其中实线部分表示一个拥有4 台机器的串行生产线系统,虚线部分表示一个拥有2 名机器维修工人的维修排队系统.当生产线中的某一台机器发生故障后,该机器就会停止加工,并进入到维修排队系统,维修完成之后,再返回生产线系统.在图2 中,机器m1和机器m2的维修任务分给了维修工人r1,而机器m3和机器m4的维修任务则分给了维修工人r2.显然,当改变维修工人的数量以及机器维修任务的分配方式时,维修效率都可能会受到影响,从而导致生产线的吞吐率发生变化.那么如何合理分配机器的维修任务,使得能够用尽可能少的维修工人,满足串行生产线的吞吐率要求,就成为了本文研究的核心内容.

图2 串行生产线中维修工人任务分配Fig.2 Repairman allocation in a serial production line

设N为维修工人数量,TP为串行生产线的吞吐率(系统稳态运行时,最后一台机器单位时间内平均产出的工件数),要在满足串行生产线吞吐率的条件下,最小化维修工人数量,则本文所研究的优化问题模型可表示为:

其中,A为任务分配方式,TP(A) 表示维修任务分配方式为A时系统的吞吐率,TP0表示系统所需满足的吞吐率,A=(D1,D2,···,DN),Di表示第i个维修工人所负责机器的集合,D则代表所有机器的集合.

然而,由于优化问题P1 中维修工人的数量是不确定的,很难直接进行任务分配,于是本文考虑将该优化问题转化为多个判定问题进行求解.优化问题P1 对应的判定问题如下:

P2:给定维修工人数量N,判定是否存在一个维修任务分配方式A,使得系统能够满足以下约束条件:

求解多个判定问题的过程也就相当于在求解原优化问题,通过不断减小维修工人数量N的值,最终便可以找到满足系统吞吐率的最小维修工人数量.

1.3 串行生产线系统动态仿真模型

在第1.2 节中,本文已经给出了问题的优化模型以及转化后的判定问题模型,然而对于模型中串行生产线系统的吞吐率还没有给出评估方法.考虑到串行生产线系统所具有的复杂性和随机性,本节将通过借鉴文献[12] 中的方法,建立串行生产线系统动态模型,采用仿真的方法求解系统吞吐率.

在串行生产线中,系统的运行主要是机器对工件的加工活动,对于串行生产线中的第k个工件来说,它在通过第j台机器时的三个主要活动时间点为:

1)(k):第k个工件从第j台机器的上游缓冲区离开,到达第j台机器的时间点.

2)(k):第k个工件在第j台机器中加工结束的时间点.

3)(k):第k个工件从第j台机器离开,到达第k台机器的下游缓冲区的时间点.

系统的动态过程可表示如下:

式(8)～(10) 中,j=1,2,···,M,k=1,2,···,K,M为总的机器数量,K为总的工件数量,Cj为第j台机器的下游缓冲区的容量,(k) 为第k个工件在第j个机器中的加工时间,(k) 的取值如下所示:

上式中,dj(k) 的值表示第k个工件在第j台机器上加工时机器是否会发生故障,当dj(k) 为0 时,表示不会发生故障,其加工时间为该机器的加工节拍τj;当dj(k) 为1 时,表示会发生故障,其加工时间为该机器的加工节拍τj加上一个带有随机性的故障时间段(k),该故障时间段等于实际维修时间与等待维修时间的总和.其中,实际维修时间可以用满足一定概率分布的随机数代替,而等待维修时间则需要在仿真过程中根据维修工人实时的忙闲情况计算得到.对于dj(k) 的值,则可通过式(12) 进行判断:

仿真时,设置初始条件如下:

通过递推求解式(8)～(10),便可建立串行生产线的系统动态仿真过程,通过统计系统稳定生产时最后一台机器的加工效率,则可得到系统吞吐率.

2 问题结构分析

2.1 维修工作量的定义和量化

针对判定问题P2,本节首先定义和量化机器的维修工作量,并将该量化指标作为求解判定问题P2时的分配依据;然后通过定义工人的维修工作量,推导出机器的维修工作量与工人的维修工作量之间的关系.

在生产系统中,一般用MTBF(Mean time between failure) 来表示机器的平均故障间隔,用MTTR(Mean time to repair) 来表示机器的平均修复时间.那么在系统稳定运行期间,第j台机器的总维修时间可以表示如下:

式中,为第j台机器在系统稳定运行时间T中故障的次数.而第j台机器在系统稳定运行期间,实际加工工件的总时间可以表示为:

加工的总工件数K为:

那么,也可以表示为:

联立式(16)～(19) 则有:

定义第j台机器的维修工作量为系统每加工一个工件时,该机器平均所需要的维修时间,则有:至此,本文将机器的维修工作量,量化为了只与机器自身参数相关的一个指标,使得各个机器的维修工作量可以直接进行比较.

对于维修工人来说,第i个维修工人的总维修时间为:

定义第i个维修工人的维修工作量为系统加工每一个工件时,该工人平均花费的维修时间,则有:

联立式(19)～(23),则有:

在判定问题P2 中,要求使用给定数量的维修工人对多个机器进行维修,判定是否存在一种任务分配方式,使得系统能够满足吞吐率要求.这就类似于在并行机调度问题中,要求采用给定数量的机器,完成多个加工任务,判定是否可以找到一种任务分配方式使得任务总完成时间满足要求.其中,判定问题P2 中的“维修工人” 对应于并行机调度问题中的“机器”,“机器维修任务” 对应于“加工任务”,而“机器维修工作量” 则对应于“加工时间”.在并行机调度问题中要求任务的加工时间满足可加性,由式(24) 可知,在判定问题P2 中机器维修的任务量也满足可加性.考虑到判定问题P2 与并行机调度问题具有很强的相似性,所以本文在求解判定问题P2时,将借鉴并行机调度问题中的经典方法,即LPT算法.

2.2 维修工人数量的下界估计

针对判定问题P2,当给定的维修工人数量较少时,可能不存在可行的分配方法.由此,本节将参考文献[12] 中求解司机数量下界的方法,推导出维修工人数量的下界.在验证分配方式是否可行时,当给定的维修工人数量小于该下界,则不需要进行仿真求解,直接判定不可行.

定义第i个维修工人的利用率Γi为系统稳定运行时,一个单位时间中该工人的平均工作时间,则有:

结合式(20)～(22) 以及式(24)～(26),则有:

结合式(5) 和式(24),则有:

当把所有机器的维修工作量乘以TP0时,则有:

3 带回溯的维修工人任务分配算法

由于本文所研究的判定问题P2 与文献[12] 中所研究的LBAP 问题是同一类问题,所以在求解判定问题P2 时,可以借鉴文献[12] 中提出的SAB 算法.同时,因为LBAP 问题与并行机调度问题具有一定相似性,所以SAB 算法结合了并行机调度问题的经典解法,即LPT 算法(一种贪心算法),并在此基础上引入了回溯策略,使得该算法能够快速求得可行解,并且以概率1 收敛.另外,文献[12] 中还将SAB 算法与遗传算法进行了对比,证明了在解决LBAP 问题时,SAB 算法的优越性.在解决本文所研究的问题时,采用LPT 算法是因为判定问题P2与并行机调度问题也具有很强的相似性,这一点在第2.1 节中已经进行了说明.在并行机调度问题中要使任务总完成时间尽可能减少,则需要使各个机器的任务量尽可能平均.那么同理,在判定问题P2中,要提高生产线吞吐率,则需要平衡维修工人的忙闲程度,该步骤通过LPT 算法即可实现.而引入回溯策略则有两个原因:首先,由于串行生产线的吞吐率是由仿真得到的,而仿真是带有一定误差的,并不能完全代表真实值;其次,一般来说维修工人的忙闲程度越平衡,系统吞吐率越高,但是由于串行生产线系统的复杂性和随机性,导致维修工人的忙闲程度最平衡时,并不表示系统吞吐率也一定最高,所以需要回溯来寻找更优的可行解.

参考SAB 算法,本文约定如果在一个分配方案中,所有的机器都被分配给了维修工人,则称这样的一个分配为完全分配,否则称之为部分分配.对于一个部分分配A来说,如果在此基础上,再分配一台机器,得到部分分配或者完全分配A′,则称A为A′的父分配,称A′为A的子分配.假设未分配的机器都不会发生故障,那么显然,当一个部分分配的系统吞吐率小于TP0,该部分分配的子分配也都不满足吞吐率要求.通过这一性质,我们便可以在算法的步骤5) 中,引入回溯策略,确定下一步的搜索方向.

算法的具体步骤如下:

1) 初始化N=Nlean,并设置一个小的正数∊,且0<∊<0.5,∊的值会影响回溯概率Pb,同时设回溯次数为nb,nb的大小将影响单个判定问题中回溯寻找可行解的次数.

2) 按照LPT 算法的思想进行贪心分配,将机器维修工作量从大到小排序,逐个将未分配的机器中最大的机器,分配给当前任务量最小的维修工人,记当前分配方式为A.

3) 仿真得到当前分配方式的吞吐率TP(A).如果TP(A)

4) 将N的值减1,按照步骤2) 中贪心分配的方法重新分配任务,并更新当前分配方案A,进入步骤5).

5) 仿真得到当前分配方案A的吞吐率TP(A),若TP(A)

6) 若在步骤5) 中找到可行解,则返回步骤4)寻找更优的可行解,否则算法结束.

算法说明:步骤1)～3),通过简单的贪心分配,可迅速获得一个可行解,缩小搜索范围;步骤4)～6)结合贪心分配和回溯策略,求解优化问题P1,其实质是对于多个判定问题P2 的求解.在步骤4)～6)中对于单个判定问题求解时,本文的算法与文献[12]中的SAB 算法基本相同,其不同点仅在于本文的算法步骤中,去除了SAB 算法里可行解的可信度这一参数.这是由于本文在求解吞吐率时,仿真时间设定较长,吞吐率的精度已经可以满足实验要求,为了简化算法步骤,则去除了该参数.

4 实验结果及分析

为了验证本文方法的有效性,第4.1 节将对一条具有8 台机器的串行生产线进行仿真实验,并对仿真结果进行定性分析.第4.2 节将仿真一条具有50 台机器的串行生产线,其中机器的参数带有一定随机性,由此进一步来验证本文方法的可靠性.

4.1 8 台机器串行生产线仿真实验

本节采用一条具有8 台机器的串行生产线,设定所有机器的可靠性模型为指数可靠性模型,机器之间的缓冲区容量均设为5 个工件,机器的加工节拍统一设置为1 (分钟),∊取值为0.15,机器的其他具体参数如表1 所示.

表1 机器参数Table 1 Machine parameters

对于这样一条具有8 台机器的串行生产线,本节首先对其分配8 个维修工人,使得所有的维修任务都能及时得到维修,通过仿真得到系统的最大吞吐率TPmax=0.8868.由于当维修工人数量小于机器数量时,其吞吐率必然小于等于为每一台机器都分配一个维修工人时生产线系统的吞吐率,所以可以设定TP0=0.95×TPmax=0.8424,当仿真求出的系统吞吐率大于等于TP0时,即认为该分配方式满足系统要求.实验所得到的系统吞吐率和工人数量如表2 所示,同时表3 中给出了具体的维修工人任务分配方案.

表2 实验结果Table 2 Experimental results

表3 维修工人任务分配Table 3 Repairman task allocation

由表2 可知,当回溯次数为0 时,即就是只采用简单的贪心分配进行求解时,得出所需的维修工人数量为5.当设置回溯次数为10,则得到了只需要4 个维修工人的分配方案,当回溯次数增加到50 后,找到了维修工人数量为4 时,吞吐率更大的可行解.实验结果表明:对于机器参数给定的小型串行生产线,本文的方法能够快速地求解出一个比较好的解,同时随着回溯次数的增加,找到更优的可行解的可能性也随之增加.

4.2 50 台机器串行生产线仿真实验

在第4.1 节中,为了方便分析,采用了一条相对简单的具有8 台机器的串行生产线,其中机器的维修率、故障率以及加工周期都是直接给定的.本节将采用一条具有50 台机器的串行生产线进行仿真实验,仍旧设定所有机器的可靠性模型为指数可靠性模型,机器之间的缓冲区容量为5 个工件,∊取值为0.15.但是,机器参数的设置更为随机,令50 台机器的故障率λ、维修率µ和加工节拍τ分别为满足(0,1)、(2,10) 和(0.8,1.2) 的均匀分布.

对于这样一条具有50 台机器的串行生产线,首先对其分配50 个维修工人,仿真得到TPmax=0.6930,设定TP0=0.95×TPmax=0.6584,然后按照算法步骤进行求解,实验结果如表4 所示.

表4 50 台机器实验结果Table 4 Experimental results of 50 machines

由表4 可知,当只采用贪心分配时,得到所需的工人数量为17,当设置回溯次数为100 时,得到了只需要15 个维修工人的分配方案,节省了2 个维修工人.实验结果表明:当串行生产线的机器参数为带有随机性的值时,本文的方法仍然能够获得较好的可行解;另外,随着机器数量的增加,解空间的规模呈爆炸性增长,此时通过本文算法中的贪心分配仍可以迅速得到一个可行解,同时通过回溯机制通常也可以找到更优的可行解.

5 结论

本文研究了串行生产线中机器维修工人的任务分配问题,给出了一套系统化的解决方案.首先,本文构建了所研究问题的优化模型,并将其转换为多个判定问题进行求解,同时建立了串行生产线的仿真模型来求解系统吞吐率;然后,合理地定义了机器的维修工作量,使得判定问题可以类比为并行机调度问题,并估计了维修工人数量的下界;最后,采用一种基于LPT 算法和回溯策略的启发式算法,对该问题进行了求解.实验结果表明,本文采用的方法在不同机器数量和不同机器参数的串行生产线中,都能较好地解决维修工人的任务分配问题,在保证系统吞吐率的前提下,有效地减少了企业的用人成本.