Formulation and Solution Methodology for Repairman Allocation Problem in Serial Production Lines
-
摘要: 在串行生产线中, 机器会发生故障而且故障间隔时间随机, 因此需要维修工人及时维修, 使得故障的机器恢复加工能力, 否则就可能导致系统吞吐率降低. 如何在满足系统吞吐率的前提下, 使用尽可能少的维修工人来完成机器的维修任务, 本文称这样一个全新的问题为串行生产线中机器维修工人的任务分配问题. 针对该问题, 本文首先建立了问题的优化模型, 并将该优化问题转换为多个判定问题进行求解; 然后, 通过合理地定义机器的维修工作量, 使得判定问题可以类比为并行机调度问题; 最后, 采用了一种基于最长处理时间优先算法(Longest processing time, LPT)和回溯策略的启发式算法, 搜索最优的维修工人任务分配方式. 实验结果表明, 该方法能有效求解维修工人的任务分配问题.Abstract: In serial production lines, machines are usually unreliable, i.e., they may break down randomly. In this situation, repairmen have to promptly repair the breakdown machines to recover their processing capability, or else the system throughput may drop. With the consideration of labor cost, how many repairmen should be employed in a production system to meet a desired throughput is called the repairman allocation problem. In this paper, the repairman allocation problem is formulated and solved. Specifically, first, it is transformed into a series of decision problems, each of which is a problem of assigning all machines to a fixed number of repairmen while guaranteeing the required throughput. Then, workloads of machines and of repairmen are defined and quantified by machine parameters. On the basis of the workloads, the decision problems are analogous to the parallel machine scheduling (PMS) problem, thus an algorithm, which is designed based on the longest processing time (LPT) algorithm for solving PMS and backtracking, is adopted to solve the decision problems. Extensive results show that this algorithm can effectively solve the decision problems, and thus, effectively solve the repairman allocation problem.
-
Key words:
- Production systems /
- machine maintenance /
- repairman allocation /
- LPT algorithm /
- backtracking
-
对于制造业来说, 其产品主要来自于庞大的生产线系统, 生产线的效率(吞吐率)越高, 企业效益往往也就越好. 然而生产线中的机器会发生随机故障, 当生产线中某一台机器发生故障时, 如果该机器没有得到及时的维修, 就有可能使得系统吞吐率下降, 进而导致企业利润减少. 本文假设一台机器故障时, 只能由已分配的某一名维修工人进行维修, 显然如果为每台机器都配备一名维修工人, 那么所有的机器故障都会得到立即维修, 企业的损失也就最小. 然而, 这样会导致维修工人在大多数时间都处于空闲状态, 极大地增加了企业的用人成本. 如何在保证串行生产线系统吞吐率的情况下, 使用尽可能少的维修工人来完成机器的维修任务, 本文称这样一个问题为串行生产线中机器维修工人的任务分配问题.
在生产线领域, 已经存在有大量的资料, 文献中主要通过排队论[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中的机器$ m_2 $发生故障时, 其下游的机器$ m_3 $不久便会加工完缓冲区$ b_2 $中的所有工件, 然后进入饥饿状态, 同时机器$ m_1 $则会在充满缓冲区$ b_1 $后进入阻塞状态. 如果此时机器$ m_2 $仍然没有被修复, 那么饥饿状态会继续向下游传播直至最后一台机器$ m_M $. 类似的, 阻塞状态也会向上游传播, 这种饥饿或堵塞的情况越严重, 串行生产线的吞吐率也就越低.
为便于分析串行生产线, 本文做出以下假设:
1) 串行生产线的第一台机器不会由于原料短缺而发生饥饿, 最后一台机器不会发生堵塞.
2) 机器$ m_j $加工一个工件所需的时间(即加工节拍)为$ \tau_j $, $ j = 1, 2, \cdots, M $, 且$ \tau_j $为一个常数.
3) 缓冲区$ b_j $的容量为$ C_j $, $ j = 1, 2, \cdots, M-1 $, 且$ C_j $为非负整数.
4) 操作相关故障(Operation-dependent failure, ODF): 机器只有在加工工件时才会发生故障, 在阻塞或饥饿时不会发生故障.
5) 加工后阻塞(Blocked after services, BAS): 一台机器如果处于工作状态, 只要其上游缓冲区非空, 就从中提取工件进行加工; 如果加工结束时, 下游缓冲区已满, 则该机器被阻塞而暂时无法加工下一个工件, 直到下游缓冲区有可用空间为止.
6) 用连续概率分布描述机器的可靠性模型, 即用连续概率分布刻画机器的故障间隔时间和故障维修时间. 如果机器的可靠性模型用负指数分布描述, 则称为指数可靠性模型; 此时, 机器的故障率和维修率可以分别用$ \lambda $和$ \mu $来表示.
1.2 问题模型
图 2给出了一个串行生产线中维修工人任务分配的例子, 其中实线部分表示一个拥有4台机器的串行生产线系统, 虚线部分表示一个拥有2名机器维修工人的维修排队系统. 当生产线中的某一台机器发生故障后, 该机器就会停止加工, 并进入到维修排队系统, 维修完成之后, 再返回生产线系统. 在图 2中, 机器$ m_1 $和机器$ m_2 $的维修任务分给了维修工人$ r_1 $, 而机器$ m_3 $和机器$ m_4 $的维修任务则分给了维修工人$ r_2 $. 显然, 当改变维修工人的数量以及机器维修任务的分配方式时, 维修效率都可能会受到影响, 从而导致生产线的吞吐率发生变化. 那么如何合理分配机器的维修任务, 使得能够用尽可能少的维修工人, 满足串行生产线的吞吐率要求, 就成为了本文研究的核心内容.
设$ N $为维修工人数量, $ TP $为串行生产线的吞吐率(系统稳态运行时, 最后一台机器单位时间内平均产出的工件数), 要在满足串行生产线吞吐率的条件下, 最小化维修工人数量, 则本文所研究的优化问题模型可表示为:
$$ \begin{eqnarray} {\rm P1: }\;\;\;\;{\rm min}\;\;\;\;N \end{eqnarray} $$ (1) $$ \begin{eqnarray} \;\;\;\;{\rm s.t.} \;\;\;\;TP(A)\ge TP_0 \end{eqnarray} $$ (2) $$ \begin{eqnarray} \;\;\;\;\;\;\;\;\bigcup\limits_{i = 1}^{N}D_i = D \end{eqnarray} $$ (3) $$ \begin{eqnarray} \;\;\;\;\;\;\;\;D_i \cap D_{i{'}} = 0, \ i\ne i{'}, \\ \;\;\;\;\;\;\;\;\qquad{i}, i{'} = 1, 2, \cdots, N \end{eqnarray} $$ (4) 其中, $ A $为任务分配方式, $ TP(A) $表示维修任务分配方式为$ A $时系统的吞吐率, $ TP_0 $表示系统所需满足的吞吐率, $ A = (D_1, D_2, \cdots, D_N) $, $ D_i $表示第$ i $个维修工人所负责机器的集合, $ D $则代表所有机器的集合.
然而, 由于优化问题P1中维修工人的数量是不确定的, 很难直接进行任务分配, 于是本文考虑将该优化问题转化为多个判定问题进行求解. 优化问题P1对应的判定问题如下:
P2: 给定维修工人数量$ N $, 判定是否存在一个维修任务分配方式$ A $, 使得系统能够满足以下约束条件:
$$ \begin{eqnarray} \quad&{\rm s.t.} \;\;\;\;TP(A)\ge TP_0 \end{eqnarray} $$ (5) $$ \begin{eqnarray} &&\bigcup\limits_{i = 1}^{N}D_i = D \end{eqnarray} $$ (6) $$ \begin{eqnarray} D_i \cap D_{i{'}} = 0, \ i\ne i{'}, \\ {i}, i{'} = 1, 2, \cdots, N \end{eqnarray} $$ (7) 求解多个判定问题的过程也就相当于在求解原优化问题, 通过不断减小维修工人数量$ N $的值, 最终便可以找到满足系统吞吐率的最小维修工人数量.
1.3 串行生产线系统动态仿真模型
在第1.2节中, 本文已经给出了问题的优化模型以及转化后的判定问题模型, 然而对于模型中串行生产线系统的吞吐率还没有给出评估方法. 考虑到串行生产线系统所具有的复杂性和随机性, 本节将通过借鉴文献[12]中的方法, 建立串行生产线系统动态模型, 采用仿真的方法求解系统吞吐率.
在串行生产线中, 系统的运行主要是机器对工件的加工活动, 对于串行生产线中的第$ k $个工件来说, 它在通过第$ j $台机器时的三个主要活动时间点为:
1) $ T_j^e(k) $: 第$ k $个工件从第$ j $台机器的上游缓冲区离开, 到达第$ j $台机器的时间点.
2) $ T_j^f(k) $: 第$ k $个工件在第$ j $台机器中加工结束的时间点.
3) $ T_j^a(k) $: 第$ k $个工件从第$ j $台机器离开, 到达第$ k $台机器的下游缓冲区的时间点.
系统的动态过程可表示如下:
$$ \begin{equation} T_j^e(k) = \max(T_{j-1}^a(k), T_j^a(k-1)) \end{equation} $$ (8) $$ \begin{equation} T_j^f(k) = T_{j}^e(k)+T_j^p(k) \end{equation} $$ (9) $$ \begin{equation} T_j^a(k) = \max(T_{j}^f(k), T_{j+1}^e(k-C_j)) \end{equation} $$ (10) 式(8) $ \sim $ (10)中, $ j = 1, 2, \cdots, M $, $ k = 1, 2, \cdots, K $, $ M $为总的机器数量, $ K $为总的工件数量, $ C_j $为第$ j $台机器的下游缓冲区的容量, $ T_j^p(k) $为第$ k $个工件在第$ j $个机器中的加工时间, $ T_j^p(k) $的取值如下所示:
$$ \begin{equation} T_j^p(k) = \left\{ \begin{array}{ll} \tau_j, & d_j(k) = 0 \\ \tau_j+T_j^d(k), & d_j(k) = 1 \\ \end{array} \right. \end{equation} $$ (11) 上式中, $ d_j(k) $的值表示第$ k $个工件在第$ j $台机器上加工时机器是否会发生故障, 当$ d_j(k) $为0时, 表示不会发生故障, 其加工时间为该机器的加工节拍$ \tau_j $; 当$ d_j(k) $为1时, 表示会发生故障, 其加工时间为该机器的加工节拍$ \tau_j $加上一个带有随机性的故障时间段$ T_j^d(k) $, 该故障时间段等于实际维修时间与等待维修时间的总和. 其中, 实际维修时间可以用满足一定概率分布的随机数代替, 而等待维修时间则需要在仿真过程中根据维修工人实时的忙闲情况计算得到. 对于$ d_j(k) $的值, 则可通过式(12)进行判断:
$$ \begin{equation} k_l = \left \lfloor {{t_j^d(l)}/{\tau_j}} \right \rfloor+1, \ l = 1, 2, \cdots , L_j \end{equation} $$ (12) 式中, $ t_j^d(l) $表示第$ j $台机器发生第$ l $次故障前该机器实际加工工件的总时间, $ L_j $为第$ j $台机器总的故障次数. 式(12)表示第$ j $台机器的第$ l $次故障发生在加工第$ k_l $个工件的过程中, 当$ k = k_l $时, $ d_j(k) = 1 $, 否则$ d_j(k) = 0 $.
仿真时, 设置初始条件如下:
$$ \begin{equation} T_0^a(k) = 0, \ k = 1, 2, \cdots, K \end{equation} $$ (13) $$ \begin{equation} T_j^a(0) = 0, \ j = 1, 2, \cdots, M \end{equation} $$ (14) $$ \begin{equation} T_j^e(k) = 0, \ k \le 0, \ j = 1, 2, \cdots, M \end{equation} $$ (15) 通过递推求解式(8) $ \sim $ (10), 便可建立串行生产线的系统动态仿真过程, 通过统计系统稳定生产时最后一台机器的加工效率, 则可得到系统吞吐率.
2. 问题结构分析
2.1 维修工作量的定义和量化
针对判定问题P2, 本节首先定义和量化机器的维修工作量, 并将该量化指标作为求解判定问题P2时的分配依据; 然后通过定义工人的维修工作量, 推导出机器的维修工作量与工人的维修工作量之间的关系.
在生产系统中, 一般用$ MTBF $ (Mean time between failure)来表示机器的平均故障间隔, 用$ MTTR $ (Mean time to repair)来表示机器的平均修复时间. 那么在系统稳定运行期间, 第$ j $台机器的总维修时间$ T_j^r $可以表示如下:
$$ \begin{equation} T_j^r = n_j^d \cdot MTTR_j \end{equation} $$ (16) 式中, $ n_j^d $为第$ j $台机器在系统稳定运行时间$ T $中故障的次数. 而第$ j $台机器在系统稳定运行期间, 实际加工工件的总时间$ T_j^o $可以表示为:
$$ \begin{equation} T_j^o = n_j^d \cdot MTBF_j \end{equation} $$ (17) 加工的总工件数$ K $为:
$$ \begin{equation} K = TP \cdot T \end{equation} $$ (18) 那么, $ T_j^o $也可以表示为:
$$ \begin{equation} T_j^o = K \cdot \tau_j \end{equation} $$ (19) 联立式(16) $ \sim $ (19)则有:
$$ \begin{equation} T_j^r = \frac{ \tau_j \cdot TP \cdot T \cdot MTTR_j}{MTBF_j} \end{equation} $$ (20) 定义第$ j $台机器的维修工作量$ W_j^r $为系统每加工一个工件时, 该机器平均所需要的维修时间, 则有:
$$ \begin{equation} W_j^r = \frac{ \tau_j \cdot MTTR_j}{MTBF_j} \end{equation} $$ (21) 至此, 本文将机器的维修工作量, 量化为了只与机器自身参数相关的一个指标, 使得各个机器的维修工作量可以直接进行比较.
对于维修工人来说, 第$ i $个维修工人的总维修时间$ T_i^{rr} $为:
$$ \begin{equation} T_i^{rr} = \sum\limits_{m_j \in {D_i}} {T_j^r} \end{equation} $$ (22) 定义第$ i $个维修工人的维修工作量$ W_i^{rr} $为系统加工每一个工件时, 该工人平均花费的维修时间, 则有:
$$ \begin{equation} W_i^{rr} = \frac {T_i^{rr}}{K} \end{equation} $$ (23) 联立式(19) $ \sim $ (23), 则有:
$$ \begin{equation} W_i^{rr} = \sum\limits_{m_j \in {D_i}} {W_j^r} \end{equation} $$ (24) 在判定问题P2中, 要求使用给定数量的维修工人对多个机器进行维修, 判定是否存在一种任务分配方式, 使得系统能够满足吞吐率要求. 这就类似于在并行机调度问题中, 要求采用给定数量的机器, 完成多个加工任务, 判定是否可以找到一种任务分配方式使得任务总完成时间满足要求. 其中, 判定问题P2中的"维修工人"对应于并行机调度问题中的"机器", "机器维修任务"对应于"加工任务", 而"机器维修工作量"则对应于"加工时间". 在并行机调度问题中要求任务的加工时间满足可加性, 由式(24)可知, 在判定问题P2中机器维修的任务量也满足可加性. 考虑到判定问题P2与并行机调度问题具有很强的相似性, 所以本文在求解判定问题P2时, 将借鉴并行机调度问题中的经典方法, 即LPT算法.
2.2 维修工人数量的下界估计
针对判定问题P2, 当给定的维修工人数量较少时, 可能不存在可行的分配方法. 由此, 本节将参考文献[12]中求解司机数量下界的方法, 推导出维修工人数量的下界. 在验证分配方式是否可行时, 当给定的维修工人数量小于该下界, 则不需要进行仿真求解, 直接判定不可行.
定义第$ i $个维修工人的利用率$ \Gamma_i $为系统稳定运行时, 一个单位时间中该工人的平均工作时间, 则有:
$$ \begin{equation} \Gamma_i = \frac{T_i^{rr}}{T} \end{equation} $$ (25) $$ \begin{equation} \Gamma_i\le1 \end{equation} $$ (26) 结合式(20) $ \sim $ (22)以及式(24) $ \sim $ (26), 则有:
$$ \begin{equation} TP \cdot W_i^{rr} \le1 \end{equation} $$ (27) 结合式(5)和式(24), 则有:
$$ \begin{equation} TP_0 \cdot \sum\limits_{m_j \in D_i} {W_j^r} \le1, \ \forall i = 1, 2, \cdots, N \end{equation} $$ (28) 当把所有机器的维修工作量乘以$ TP_0 $时, 则有:
$$ \begin{equation} TP_0 \cdot \sum\limits_{m_j \in D} {W_j^r} = N_{lean} \le N_{lean}^* \end{equation} $$ (29) 上式中, $ N_{lean} $表示当所有维修工人的利用率都为1时所需维修工人数量的下界, $ N_{lean}^* $表示系统实际所需维修工人数量的下界. 然而由于$ N_{lean}^* $很难直接求解, 所以本文转而用$ N_{lean} $来估计$ N_{lean}^* $, 在求解单个判定问题P2时, 当$ N<N_{lean} $, 则可以直接判定此时不存在可行解.
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 $的子分配. 假设未分配的机器都不会发生故障, 那么显然, 当一个部分分配的系统吞吐率小于$ TP_0 $, 该部分分配的子分配也都不满足吞吐率要求. 通过这一性质, 我们便可以在算法的步骤5)中, 引入回溯策略, 确定下一步的搜索方向.
算法的具体步骤如下:
1) 初始化$ N = N_{lean} $, 并设置一个小的正数$ \epsilon $, 且$ 0< \epsilon <0.5 $, $ \epsilon $的值会影响回溯概率$ P_b $, 同时设回溯次数为$ n_b $, $ n_b $的大小将影响单个判定问题中回溯寻找可行解的次数.
2) 按照LPT算法的思想进行贪心分配, 将机器维修工作量$ W_j^r $从大到小排序, 逐个将未分配的机器中$ W_j^r $最大的机器, 分配给当前任务量最小的维修工人, 记当前分配方式为$ A $.
3) 仿真得到当前分配方式的吞吐率$ TP(A) $. 如果$ TP(A)<TP_0 $, 则将$ N $加1, 并返回步骤2), 否则说明直接通过贪心分配已找到一个可行解, 可以开始回溯寻找更优的可行解.
4) 将$ N $的值减1, 按照步骤2)中贪心分配的方法重新分配任务, 并更新当前分配方案$ A $, 进入步骤5).
5) 仿真得到当前分配方案$ A $的吞吐率$ TP(A) $, 若$ TP(A)<TP_0 $, 则设置回溯概率$ P_b = 1- \epsilon $, 否则设$ P_b = \epsilon $. 产生一个满足(0, 1)均匀分布的随机数$ \zeta $, 当$ A $为一个部分分配时, 如果存在$ i \in \{ 1, 2, \cdots, N \} $, 使得子分配的生产线系统吞吐率满足要求, 并且有$ (i-1)\cdot(1-P_b)/N< \zeta \le i \cdot(1-P_b)/N $, 则用该子分配替换当前分配, 否则使用$ A $的父分配替换当前分配; 当$ A $是一个完全分配时, 如果$ \zeta \le 1-P_b $并且$ TP(A) \ge TP_0 $, 则保持$ A $为当前分配, 并记录当前分配为一个可行解, 否则使用$ A $的父分配取代当前分配. 将$ n_b $减1, 如果$ n_b = 0 $, 则进入步骤6), 否则返回步骤5).
6) 若在步骤5)中找到可行解, 则返回步骤4)寻找更优的可行解, 否则算法结束.
算法说明: 步骤1) $ \sim $ 3), 通过简单的贪心分配, 可迅速获得一个可行解, 缩小搜索范围; 步骤4) $ \sim $ 6)结合贪心分配和回溯策略, 求解优化问题P1, 其实质是对于多个判定问题P2的求解. 在步骤4) $ \sim $ 6)中对于单个判定问题求解时, 本文的算法与文献[12]中的SAB算法基本相同, 其不同点仅在于本文的算法步骤中, 去除了SAB算法里可行解的可信度这一参数. 这是由于本文在求解吞吐率时, 仿真时间设定较长, 吞吐率的精度已经可以满足实验要求, 为了简化算法步骤, 则去除了该参数.
4. 实验结果及分析
为了验证本文方法的有效性, 第4.1节将对一条具有8台机器的串行生产线进行仿真实验, 并对仿真结果进行定性分析. 第4.2节将仿真一条具有50台机器的串行生产线, 其中机器的参数带有一定随机性, 由此进一步来验证本文方法的可靠性.
4.1 8台机器串行生产线仿真实验
本节采用一条具有8台机器的串行生产线, 设定所有机器的可靠性模型为指数可靠性模型, 机器之间的缓冲区容量均设为5个工件, 机器的加工节拍统一设置为1 (分钟), $ \epsilon $取值为0.15, 机器的其他具体参数如表 1所示.
表 1 机器参数Table 1 Machine parameters机器编号 故障率(次/分钟) 维修率(次/分钟) 维修工作量(分钟) 1 0.2 5 0.04 2 0.2 5 0.04 3 0.6 5 0.12 4 0.6 5 0.12 5 0.4 5 0.08 6 0.4 5 0.08 7 0.2 5 0.04 8 0.2 5 0.04 对于这样一条具有8台机器的串行生产线, 本节首先对其分配8个维修工人, 使得所有的维修任务都能及时得到维修, 通过仿真得到系统的最大吞吐率$ TP_{\max} = 0.8868 $. 由于当维修工人数量小于机器数量时, 其吞吐率必然小于等于为每一台机器都分配一个维修工人时生产线系统的吞吐率, 所以可以设定$ TP_0 = 0.95\times TP_{\max} = 0.8424 $, 当仿真求出的系统吞吐率大于等于$ TP_0 $时, 即认为该分配方式满足系统要求. 实验所得到的系统吞吐率和工人数量如表 2所示, 同时表 3中给出了具体的维修工人任务分配方案.
表 2 实验结果Table 2 Experimental results回溯次数 吞吐率(个/分钟) 工人数(人) 0 0.8867 5 10 0.8428 4 50 0.8589 4 100 0.8589 4 由表 2可知, 当回溯次数为0时, 即就是只采用简单的贪心分配进行求解时, 得出所需的维修工人数量为5. 当设置回溯次数为10, 则得到了只需要4个维修工人的分配方案, 当回溯次数增加到50后, 找到了维修工人数量为4时, 吞吐率更大的可行解. 实验结果表明: 对于机器参数给定的小型串行生产线, 本文的方法能够快速地求解出一个比较好的解, 同时随着回溯次数的增加, 找到更优的可行解的可能性也随之增加.
表 3 维修工人任务分配Table 3 Repairman task allocation回溯次数 分配方案 0 $ D_1 = \{m_{3}\} $, $ D_2 = \{m_{4}\} $, $ D_3 = \{m_{5}, m_{7}\} $, $ D_4 = \{m_{6}, m_{8}\} $, $ D_5 = \{m_{1}, m_{2}\} $ 10 $ D_1 = \{m_{3}\} $, $ D_2 = \{m_{4}, m_{7}\} $, $ D_3 = \{m_{1}, m_{5}\} $, $ D_4 = \{m_{2}, m_{6}, m_{8}\} $ 50 $ D_1 = \{m_{2}, m_{3}\} $, $ D_2 = \{m_{4}\} $, $ D_3 = \{m_{1}, m_{5}\} $, $ D_4 = \{m_{6}, m_{7}, m_{8}\} $ 100 $ D_1 = \{m_{2}, m_{3}\} $, $ D_2 = \{m_{4}\} $, $ D_3 = \{m_{1}, m_{5}\} $, $ D_4 = \{m_{6}, m_{7}, m_{8}\} $ 4.2 50台机器串行生产线仿真实验
在第4.1节中, 为了方便分析, 采用了一条相对简单的具有8台机器的串行生产线, 其中机器的维修率、故障率以及加工周期都是直接给定的. 本节将采用一条具有50台机器的串行生产线进行仿真实验, 仍旧设定所有机器的可靠性模型为指数可靠性模型, 机器之间的缓冲区容量为5个工件, $ \epsilon $取值为0.15. 但是, 机器参数的设置更为随机, 令50台机器的故障率$ \lambda $、维修率$ \mu $和加工节拍$ \tau $分别为满足(0, 1)、(2, 10)和(0.8, 1.2)的均匀分布.
对于这样一条具有50台机器的串行生产线, 首先对其分配50个维修工人, 仿真得到$ TP_{\max} = 0.6930 $, 设定$ TP_0 = 0.95\times TP_{\max} = 0.6584 $, 然后按照算法步骤进行求解, 实验结果如表 4所示.
表 4 50台机器实验结果Table 4 Experimental results of 50 machines回溯次数 吞吐率(个/分钟) 工人数(人) 0 0.6600 17 100 0.6586 15 由表 4可知, 当只采用贪心分配时, 得到所需的工人数量为17, 当设置回溯次数为100时, 得到了只需要15个维修工人的分配方案, 节省了2个维修工人. 实验结果表明: 当串行生产线的机器参数为带有随机性的值时, 本文的方法仍然能够获得较好的可行解; 另外, 随着机器数量的增加, 解空间的规模呈爆炸性增长, 此时通过本文算法中的贪心分配仍可以迅速得到一个可行解, 同时通过回溯机制通常也可以找到更优的可行解.
5. 结论
本文研究了串行生产线中机器维修工人的任务分配问题, 给出了一套系统化的解决方案. 首先, 本文构建了所研究问题的优化模型, 并将其转换为多个判定问题进行求解, 同时建立了串行生产线的仿真模型来求解系统吞吐率; 然后, 合理地定义了机器的维修工作量, 使得判定问题可以类比为并行机调度问题, 并估计了维修工人数量的下界; 最后, 采用一种基于LPT算法和回溯策略的启发式算法, 对该问题进行了求解. 实验结果表明, 本文采用的方法在不同机器数量和不同机器参数的串行生产线中, 都能较好地解决维修工人的任务分配问题, 在保证系统吞吐率的前提下, 有效地减少了企业的用人成本.
-
表 1 机器参数
Table 1 Machine parameters
机器编号 故障率(次/分钟) 维修率(次/分钟) 维修工作量(分钟) 1 0.2 5 0.04 2 0.2 5 0.04 3 0.6 5 0.12 4 0.6 5 0.12 5 0.4 5 0.08 6 0.4 5 0.08 7 0.2 5 0.04 8 0.2 5 0.04 
下载: 导出CSV
表 2 实验结果
Table 2 Experimental results
回溯次数 吞吐率(个/分钟) 工人数(人) 0 0.8867 5 10 0.8428 4 50 0.8589 4 100 0.8589 4
下载: 导出CSV
表 3 维修工人任务分配
Table 3 Repairman task allocation
回溯次数 分配方案 0 $ D_1 = \{m_{3}\} $, $ D_2 = \{m_{4}\} $, $ D_3 = \{m_{5}, m_{7}\} $, $ D_4 = \{m_{6}, m_{8}\} $, $ D_5 = \{m_{1}, m_{2}\} $ 10 $ D_1 = \{m_{3}\} $, $ D_2 = \{m_{4}, m_{7}\} $, $ D_3 = \{m_{1}, m_{5}\} $, $ D_4 = \{m_{2}, m_{6}, m_{8}\} $ 50 $ D_1 = \{m_{2}, m_{3}\} $, $ D_2 = \{m_{4}\} $, $ D_3 = \{m_{1}, m_{5}\} $, $ D_4 = \{m_{6}, m_{7}, m_{8}\} $ 100 $ D_1 = \{m_{2}, m_{3}\} $, $ D_2 = \{m_{4}\} $, $ D_3 = \{m_{1}, m_{5}\} $, $ D_4 = \{m_{6}, m_{7}, m_{8}\} $
下载: 导出CSV
表 4 50台机器实验结果
Table 4 Experimental results of 50 machines
回溯次数 吞吐率(个/分钟) 工人数(人) 0 0.6600 17 100 0.6586 15
下载: 导出CSV
-
[1] 张于贤, 李娜, 肖吉军. 基于排队论的生产线量化分析及优化. 制造业自动化, 2014, 7: 59-61 https://www.cnki.com.cn/Article/CJFDTOTAL-JXGY201407018.htmZhang Yu-Xian, Li Na, Xiao Ji-Jun. Quantitative analysisand optimizationofthe production line based on the queuing theory. Manufacturing Automation, 2014, 7: 59-61 https://www.cnki.com.cn/Article/CJFDTOTAL-JXGY201407018.htm [2] Yang F J, Gao K Z, Simon I W, Zhu Y T, Zhu R. Decomposition methods for manufacturing system scheduling: a survey. IEEE/CAA Journal of Automatica Sinica, 2018, 5(2): 389-400 doi: 10.1109/JAS.2017.7510805 [3] Zhao Y J, Yan C B, Zhao Q C, et al. Efficient simulation method for general assembly systems with material handling based on aggregated event-scheduling. IEEE Transactions on Automation Science and Engineering, 2010, 7(4): 762-775 doi: 10.1109/TASE.2009.2034135 [4] Li J S, Meerkov S M. Production Systems Engineering, New York: Springer, 2009. 17-37 [5] Xiao F L, Shao L P. Optimizing production line balance based on witness simulation. In: Proceedings of the 8th International Conference on Logistic, Informatics and Service Sciences. Toronto, ON, Canada: IEEE, 2018. 1-5 [6] Borba L, Ritt M, Miralles C. Exact and heuristic methods for solving the robotic assembly line balancing problem. European Journal of Operational Research, 2018, 270(1): 146-156 doi: 10.1016/j.ejor.2018.03.011 [7] Horng S L, Lin S S. Merging artificial immune system and ordinal optimization for solving the optimal buffer resource allocation of production line. In: Proceedings of the 9th International Conference on Knowledge and Smart Technology. Chonburi, Thailand: IEEE, 2017. 6-11 [8] Sophie W, Andrea M, Raik S. Optimization of buffer allocations in flow lines with limited supply. ⅡSE Transactions, 2018, 50(3): 191-202 doi: 10.1080/24725854.2017.1328751?src=recsys [9] Zou D X, Gao L Q, Li S. A novel global harmony search algorithm for task assignment problem. Journal of Systems and Software, 2010, 83(10): 1678-1688 doi: 10.1016/j.jss.2010.04.070 [10] Camacho G A, Cuellar D, Álvarez D. Heuristic approach for the multiple bin-size bin packing problem. IEEE Latin America Transactions, 2018, 16(2): 620-626 doi: 10.1109/TLA.2018.8327421 [11] 李孙寸, 施心陵, 张松海, 董易, 高莲, 基于多元优化的三维装箱问题的研究. 自动化学报, 2018, 44(1): 106-115 doi: 10.16383/j.aas.2018.c160381Li Sun-Cun, Shi Xin-Ling, Zhang Song-Hai, Dong Yi, Gao Lian. Multi-variant optimization algorithm for three dimensional container loading problem. Acta Automatica Sinica, 2018, 44(1): 106-115 doi: 10.16383/j.aas.2018.c160381 [12] Yan C B, Zhao Q C, Huang N J, Xiao G X, Li J S. Formulation and a simulation based algorithm for line-side buffer assignment problem in systems of general assembly line with material handling. IEEE Transactions on Automation Science and Engineering, 2010, 7(4): 902-920 doi: 10.1109/TASE.2010.2046892 [13] Sels V, Coelho J, Dias A M, Vanhoucke M. Hybrid tabu search and a truncated branch-and-bound for the unrelated parallel machine scheduling problem. Computers and Operations Research, 2015, 53: 107-117 doi: 10.1016/j.cor.2014.08.002 [14] Massabò I, Paletta G, Ruiz-Torres A J. A note on longest processing time algorithms for the two uniform parallel machine makespan minimization problem. Journal of Scheduling, 2016, 19(2): 207-211 doi: 10.1007/s10951-015-0453-x [15] Braun O, Chung F, Graham R. Worst-case analysis of the LPT algorithm for single processor scheduling with time restrictions. OR Spectrum, 2016, 38(2): 531-540 doi: 10.1007/s00291-016-0431-5 期刊类型引用(5)
1. 贾之阳，倪泽军，王遵君，王钢. 小批量多返工生产系统瞬态性能分析和优化. 控制与决策. 2024(08): 2746-2754 . 
百度学术2. 李书明，杨卫，万然，崔童谣，范玉龙. 卷包车间故障维修智能呼叫系统的设计. 现代信息科技. 2024(14): 112-116 . 百度学术3. 顾文斌，王贤良，苑明海，裴凤雀. 面向置换流水车间生产过程的瞬态产能计算方法. 工业工程与管理. 2023(04): 70-81 . 百度学术4. 张友鹏，苏中集，石磊，张美艳. 基于嵌套粒子群结构的复杂系统维修决策优化方法. 计算机集成制造系统. 2023(11): 3800-3811 . 百度学术5. 秦敏敏，刘立芳，齐小刚. 面向维修资源分配调度的遗传-长鼻浣熊混合优化算法. 智能系统学报. 2023(06): 1322-1335 . 百度学术其他类型引用(4)
-
下载:
计量
- 文章访问数: 687
- HTML全文浏览量: 230
- PDF下载量: 162
- 被引次数: 9
