摘 要 在串行生产线中, 机器会发生随机故障(即机器不可靠), 因此需要维修工人及时维修, 使得故障的机器恢复加工能力, 否则就可能导致系统吞吐率降低. 如何在满足系统吞吐率的前提下, 使用尽可能少的维修工人来完成机器的维修任务, 本文称这样一个全新的问题为串行生产线中机器维修工人的任务分配问题. 针对该问题, 本文首先建立了问题的优化模型, 并将该优化问题转换为多个判定问题进行求解; 然后, 通过合理地定义机器的维修工作量, 使得判定问题可以类比为并行机调度问题; 最后, 采用了一种基于最长处理时间优先算法(Longest Processing Time, LPT)和回溯策略的启发式算法, 搜索最优的维修工人任务分配方式. 实验结果表明, 该方法能有效求解维修工人的任务分配问题.
关键词 生产系统, 机器维修, 任务分配, LPT算法, 回溯策略
对于制造业来说, 其产品主要来自于庞大的生产线系统, 生产线的效率(吞吐率)越高, 企业效益往往也就越好. 然而生产线中的机器会发生随机故障, 当生产线中某一台机器发生故障时, 如果该机器没有得到及时的维修, 就有可能使得系统吞吐率下降, 进而导致企业利润减少. 本文假设一台机器故障时, 只能由已分配的某一名维修工人进行维修, 显然如果为每台机器都配备一名维修工人, 那么所有的机器故障都会得到立即维修, 企业的损失也就最小. 然而, 这样会导致维修工人在大多数时间都处于空闲状态, 极大地增加了企业的用人成本. 如何在保证串行生产线系统吞吐率的情况下, 使用尽可能少的维修工人来完成机器的维修任务, 本文称这样一个问题为串行生产线中机器维修工人的任务分配问题.
在生产线领域, 已经存在有大量的资料, 文献中主要通过排队论[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]和回溯策略, 是一种启发式算法.
本文的贡献在于: 第一, 本文提出了一个全新的问题——串行生产线中机器维修工人的任务分配问题, 并对其进行了建模; 第二, 合理地定义了机器的维修工作量, 使得本文所研究的问题可以类比为并行机调度问题; 第三, 通过仿真实验, 验证了文献[12]中提出的SAB算法, 对本文所研究的问题同样适用, 该方法在保证系统吞吐率的前提下, 能够有效减少企业的用人成本.
本文的结构安排如下: 第一节介绍串行生产线, 建立问题模型和仿真模型; 第二节定义和量化机器以及工人的维修工作量, 并对维修工人数量的下界进行估计; 第三节描述带回溯的维修工人任务分配算法; 第四节进行仿真实验, 验证本文方法的有效性; 最后对本文的内容和贡献进行总结.
1 系统模型
1.1 串行生产线模型
串行生产线是指: 将机器以串行方式连接起来, 并通过物料储运设备将工件从第一个机器输送到与它相邻的下一个机器的生产系统, 如图1所示, 其中圆圈表示机器, 方框表示物料储运设备(即缓冲区). 在实际生产过程中, 机器总是会发生随机故障(即机器不可靠), 这些故障造成的影响会沿着生产线向上游和下游的机器传播. 例如, 当图1中的机器m2发生故障时, 其下游的机器m3不久便会加工完缓冲区b2中的所有工件, 然后进入饥饿状态, 同时机器m1则会在充满缓冲区b1后进入阻塞状态. 如果此时机器m2仍然没有被修复, 那么饥饿状态会继续向下游传播直至最后一台机器mM. 类似的, 阻塞状态也会向上游传播, 这种饥饿或堵塞的情况越严重, 串行生产线的吞吐率也就越低.
1.2 问题模型
图2给出了一个串行生产线中维修工人任务分配的例子, 其中实线部分表示一个拥有4台机器的串行生产线系统, 虚线部分表示一个拥有2名机器维修工人的维修排队系统. 当生产线中的某一台机器发生故障后, 该机器就会停止加工, 并进入到维修排队系统, 维修完成之后, 再返回生产线系统. 在图2中, 机器m1和机器m2的维修任务分给了维修工人r1, 而机器m3和机器m4的维修任务则分给了维修工人r2. 显然, 当改变维修工人的数量以及机器维修任务的分配方式时, 维修效率都可能会受到影响, 从而导致生产线的吞吐率发生变化. 那么如何合理分配机器的维修任务, 使得能够用尽可能少的维修工人, 满足串行生产线的吞吐率要求, 就成为了本文研究的核心内容.
3 带回溯的维修工人任务分配算法
由于本文所研究的判定问题(P2)与文献[12]中所研究的LBAP问题是同一类问题, 所以在求解判定问题(P2)时, 可以借鉴文献[12]中提出的SAB算法. 同时, 因为LBAP问题与并行机调度问题具有一定相似性, 所以SAB算法结合了并行机调度问题的经典解法, 即LPT算法(一种贪心算法), 并在此基础上引入了回溯策略, 使得该算法能够快速求得可行解, 并且以概率1收敛. 另外, 文献[12]中还将SAB算法与遗传算法进行了对比, 证明了在解决LBAP问题时, SAB算法的优越性. 在解决本文所研究的问题时, 采用LPT算法是因为判定问题(P2)与并行机调度问题也具有很强的相似性, 这一点在2.1节中已经进行了说明. 在并行机调度问题中要使任务总完成时间尽可能减少, 则需要使各个机器的任务量尽可能平均. 那么同理, 在判定问题(P2)中, 要提高生产线吞吐率, 则需要平衡维修工人的忙闲程度, 该步骤通过LPT算法即可实现. 而引入回溯策略则有两个原因: 首先, 由于串行生产线的吞吐率是由仿真得到的, 而仿真是带有一定误差的, 并不能完全代表真实值; 其次, 一般来说维修工人的忙闲程度越平衡, 系统吞吐率越高, 但是由于串行生产线系统的复杂性和随机性, 导致维修工人的忙闲程度最平衡时, 并不表示系统吞吐率也一定最高, 所以需要回溯来寻找更优的可行解.
参考SAB算法, 本文约定如果在一个分配方案中, 所有的机器都被分配给了维修工人, 则称这样的一个分配为完全分配, 否则称之为部分分配. 对于一个部分分配A来说, 如果在此基础上, 再分配一台机器, 得到部分分配或者完全分配A0 , 则称A为A0的父分配, 称A0为A的子分配. 假设未分配的机器都不会发生故障, 那么显然, 当一个部分分配的系统吞吐率小于T P0, 该部分分配的子分配也都不满足吞吐率要求. 通过这一性质, 我们便可以在算法的步骤5)中, 引入回溯策略, 确定下一步的搜索方向.
算法的具体步骤如下:
1)初始化N = Nlean, 并设置一个小的正数², 且0 < ² < 0.5, ²的值会影响回溯概率Pb, 同时设回溯次数为nb, nb的大小将影响单个判定问题中回溯寻找可行解的次数.
2)按照LPT算法的思想进行贪心分配, 将机器维修工作量Wr j 从大到小排序, 逐个将未分配的机器中Wr j 最大的机器, 分配给当前任务量最小的维修工人, 记当前分配方式为A.
3)仿真得到当前分配方式的吞吐率T P(A). 如果T P(A) < T P0, 则将N加1, 并返回步骤2), 否则说明直接通过贪心分配已找到一个可行解, 可以开始回溯寻找更优的可行解.
4)将N的值减1, 按照步骤2)中贪心分配的方法重新分配任务, 并更新当前分配方案A, 进入步骤5).
5)仿真得到当前分配方案A的吞吐率T P(A), 若T P(A) < T P0, 则设置回溯概率Pb = 1 − ², 否则设Pb = ². 产生一个满足(0,1)均匀分布的随机数ζ, 当A为一个部分分配时, 如果存在i ∈ {1, 2, . . . , N}, 使得子分配的生产线系统吞吐率满足要求, 并且有(i − 1) · (1 − Pb)/N < ζ ≤ i · (1 − Pb)/N, 则用该子分配替换当前分配, 否则使用A的父分配替换当前分配; 当A是一个完全分配时, 如果ζ ≤ 1 − Pb并且T P(A) ≥ T P0, 则保持A为当前分配, 并记录当前分配为一个可行解, 否则使用A的父分配取代当前分配. 将nb减1, 如果nb = 0, 则进入步骤6), 否则返回步骤5).
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所示.
对于这样一条具有8台机器的串行生产线, 本节首先对其分配8个维修工人, 使得所有的维修任务都能及时得到维修, 通过仿真得到系统的最大吞吐率T Pmax = 0.8868. 由于当维修工人数量小于机器数量时, 其吞吐率必然小于等于为每一台机器都分配一个维修工人时生产线系统的吞吐率, 所以可以设定T P0 = 0.95 ∗ T Pmax = 0.8424, 当仿真求出的系统吞吐率大于等于T P0时, 即认为该分配方式满足系统要求. 实验所得到的系统吞吐率和工人数量如表2所示, 同时表3中给出了具体的维修工人任务分配方案.
由表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个维修工人, 仿真得到T Pmax = 0.6930, 设定T P0 = 0.95 ∗ T Pmax = 0.6584, 然后按照算法步骤进行求解, 实验结果如表4所示.
由表4可知, 当只采用贪心分配时, 得到所需的工人数量为17, 当设置回溯次数为100时, 得到了只需要15个维修工人的分配方案, 节省了2个维修工人. 实验结果表明: 当串行生产线的机器参数为带有随机性的值时, 本文的方法仍然能够获得较好的可行解; 另外, 随着机器数量的增加, 解空间的规模呈爆炸性增长, 此时通过本文算法中的贪心分配仍可以迅速得到一个可行解, 同时通过回溯机制通常也可以找到更优的可行解.
5 结论
本文研究了串行生产线中机器维修工人的任务分配问题, 给出了一套系统化的解决方案. 首先, 本文构建了所研究问题的优化模型, 并将其转换为多个判定问题进行求解, 同时建立了串行生产线的仿真模型来求解系统吞吐率; 然后, 合理地定义了机器的维修工作量, 使得判定问题可以类比为并行机调度问题, 并估计了维修工人数量的下界; 最后, 采用一种基于LPT算法和回溯策略的启发式算法, 对该问题进行了求解. 实验结果表明, 本文采用的方法在不同机器数量和不同机器参数的串行生产线中, 都能较好的解决维修工人的任务分配问题, 在保证系统吞吐率的前提下, 有效地减少了企业的用人成本.——论文作者：鄢超波1, 2 张雷1, 2
