基于可用度评价的串行生产线缓冲分配方法

周炳海,余佳迪,邵健一

（同济大学机械与能源工程学院,上海201804）

基于可用度评价的串行生产线缓冲分配方法

周炳海,余佳迪,邵健一

（同济大学机械与能源工程学院,上海201804）

为有效和快速地分配缓冲区容量,提高串行生产线可用度和产出率,提出一种基于可用度评价的缓冲分配方法.在考虑串行生产线特性的同时,结合马尔科夫理论,通过分析设备状态及缓冲状态间的转化规律,建立串行生产线的可用度评价模型.在此基础上构建求解缓冲分配问题的遗传算法,并运用算例给出缓冲分配问题的解决过程.从产出率、在制品数量等方面将提出方法与其他分配方法进行比较,从而验证与评价数学模型的准确性.结果表明提出的缓冲分配方法是可行、有效的.

串行生产线；缓冲分配；可用度评价；马尔科夫

缓冲区是串行生产线的重要组成部分,合理分配有限的缓冲区容量对于平衡上下游设备之间的生产率差异,减轻由设备故障等因素引发的系统波动,提高系统可用性和产出率具有重要意义.

缓冲区设置问题（buffer allocation problem, BAP）一直是个研究热点.Manitz［1］提出了一种基于排队模型的分析方法来分析、配置缓冲区容量.Colledani等［2］提出了一种BAP分配方法,用以评价生产系统生产和物流方面的性能.Demir等［3］针对不稳定的生产线,提出一种模糊搜索方法,以确定生产线上缓冲区的位置及容量大小,使系统产出最大.Abdul-Kader等［4］建立了基于饥饿和阻塞状态的非线性优化模型,在此基础上进行缓冲区容量配置问题求解.Battini等［5］考虑到机器故障和加工时间的波动,建立了仿真模型,并对缓冲区的容量进行鲁棒性设计.Shi等［6］研究了加工速率呈非线性的缓冲区设置问题.Aksoy等［7］利用开放式排队网络和分解、扩展的方法,提出了一种渐进式的缓冲区容量优化方法.Helber等［8］考虑到设备加工时间的随机波动性,利用线性规划的方法进行缓冲区分配问题的求解.Pan等［9］通过分解生产系统的方法,解决了均衡、未均衡生产系统中的缓冲区分配问题.Hillier［10］以最大化系统收益为目标,建立了启发式算法,并进行了缓冲容量优化设计.Battini等［11］设计了基于实验的缓冲区容量分配算法.但上述文献都没有从设备的可用度角度来研究缓冲区容量分配.本文以带缓冲区的串行生产线为研究对象,建立了串行生产系统的可用度评价模型,并提出了一种基于可用度评价模型的缓冲区容量分配方法.

1 问题描述

本文所研究的串行生产线由n台设备（M1～Mn）串联组成,布局属于带缓冲的Flow shop生产线,设备间在制品缓冲区为B1～Bn－1,如图1所示.

图1 串行生产线Fig.1 Series production line

在缓冲区总容量给定的情况下,优化求解目标是最大化系统可用度.数学模型可表示为

式中：A为串行生产线的稳态可用度,Vi为缓冲区Bi的容量,V为生产线的缓冲区总容量,Vup为缓冲区Bi的容量上限.

为了有效描述评价串行生产线可用度,做如下假设：1）生产线第1台机器不饥饿,最后1台机器不堵塞；2）设备故障后无需等待,可立即开展维修作业,但需要一定的时间来修复；3）设备故障和修复过程都服从指数分布；4）所研究的串行生产线t＋1时刻系统状态的概率分布与t时刻以前的状态无关,仅与t时刻的状态有关,即系统满足Markov模型.

2 二级子系统可用度

串行生产线中由相邻2个设备及中间缓冲区组成的系统称为二级子系统,如图2所示.研究串行生产线可用度模型的核心思想描述如下：首先,计算二级子系统可用度；然后,使用一个虚拟设备来等效替换一个二级子系统,通过虚拟设备之间的不断等效替换最终构建成一个基于虚拟设备的二级子系统,并进行其可用度求解.

图2 二级子系统基本构成Fig.2 Basic components of subsystem

二级子系统可用度大小由其设备参数和缓冲区容量决定.在评价二级子系统可用度过程中,首先对二级子系统的设备状态进行分类,描述出不同设备状态间的相互转化规律,并计算出系统稳态时处于各种状态的概率.然后,分别描述不同设备状态下缓冲区各状态间的相互转化规律,并分析其稳态概率.最后,综合分析设备和缓冲区状态,计算出二级子系统可用度.这里以包含设备M1、M2和缓冲区B1的二级子系统Sub1为例计算其可用度.

2.1 二级子系统设备状态变化规律

二级子系统Sub1中所包含的2个设备M1和M2各自有2种设备状态,故Sub1有4种设备状态,其设备状态空间Sys1可表示为

式中：状态X1,1表示Sub1中的2个设备均处于正常工作状态；状态X1,2表示Sub1中的设备M1正常工作,设备M2故障；状态X1,3表示Sub1中的设备M1故障,设备M2正常工作；状态X1,4表示Sub1中的2个设备均处于故障状态.

在故障和维修作业的作用下,Sub1的各状态可以相互转换,其状态转移情况如图3所示.

图3 二级子系统设备状态转移图Fig.3 Equipment states transition of subsystem

结合M1、M2设备参数,通过分析可以得到各状态间相互转化的规律,二级子系统Sub1各状态间的状态转移矩阵可表示为

式中：λi为设备Mi的故障率；μi为Mi的修复率.

根据Markov理论,系统在足够长的时间内最终会运行到一个稳定状态,即达到其稳态,Sub1设备状态的稳态方程可表示为

2.2 二级子系统缓冲区状态变化规律

二级子系统Sub1中缓冲区容量为V1（V1∈N＋）,故缓冲区的状态为：空、有1个在制品、有2个在制品、…、有V1－1个在制品、满等V1＋1个状态,因此Sub1中的缓冲区B1的状态空间Buf1可表示为

但对于二级子系统Sub1来讲,不同系统设备状态下的缓冲区在制品数量变化规律各不相同.当系统处于状态X1,4时,缓冲区中在制品数量不会发生任何变化,故在接下来的在制品数量变化规律的讨论中,不再考虑系统处于状态X1,4的情况.

1）Sub1处于X1,1状态：二级子系统处于X1,1状态时,系统中的2个设备均正常工作,M1为缓冲区B1提供在制品的同时,M2在不断消耗缓冲区B1中的在制品.在该状态下,缓冲区B1的状态变化情况如图4所示.

图4 X 1,1状态下的缓冲区状态转移图Fig.4 Buffer states transition under X 1,1

此时的缓冲区状态转移矩阵可表示为

式中：PBufi,j为Subi处于Xi,j状态时,缓冲区Bi的状态转移矩阵；γ＝（1－ω1）ω2；η＝ω1（1－ω2）；ε＝ω1ω2＋（1－ω1）（1－ω2）；ωi为设备Mi的生产率.

2）Sub1处于X1,2状态：二级子系统处于X1,2状态时,设备M1正常工作,设备M2故障.在此种状态下,M2不消耗B1中的在制品,而M1不断为缓冲区B1提供在制品.在该状态下,缓冲区B1的状态变化情况如图5所示.

图5 X 1,2状态下的缓冲区状态转移图Fig.5 Buffer states transition under X 1,2

此时的缓冲区状态转移矩阵可表示为

3）Sub1处于X1,3状态：二级子系统处于X1,3状态时,设备M1故障,设备M2正常工作.在此种状态下,M1不为缓冲区B1提供在制品,而M2却在消耗B1中的在制品.在该状态下,缓冲区B1的状态变化情况如图6所示.

图6 X 1,3状态下的缓冲区状态转移图Fig.6 Buffer states transition under X 1,3

此时的缓冲区状态转移矩阵可表示为

状态转移矩阵PBuf1,1、PBuf1,2、PBuf1,3均为（V1＋1）×（V1＋1）阶矩阵.当二级子系统处于不同设备状态下时,缓冲区稳态方程可表示为

求解不同j取值下的式（11）,便可以得到系统在X1,1,X1,2,X1,3状态下,缓冲区的稳态概率矩阵.结合实际情况可以知道,处于X1,2、X1,3状态下的缓冲区在足够长的运行时间后,必定会达到满或空的状态,即其缓冲区稳态运行时为满或空的状态.结合假设（4）,此种情况显然是不合理的,由于设备的及时维护,系统缓冲区未必能达到其稳态.为此,在二级子系统的可用度的评价过程中,将引入设备维护方面的参数对X1,2、X1,3状态下的缓冲区的稳态概率分布进行修正.

2.3 二级子系统可用度评价

在实际生产中,当设备Mi（i∈｛1,2,3,…, n｝）故障时,其前或其后的设备并不会立即停止作业,而会一直加工到2个设备间的缓冲区达到满或空的状态,因此能保证系统正常运行的状态包括：（a）系统处于X1,1时设备M2不空闲,即M1和M2都正常工作且缓冲区B1不满；（b）系统处于X1,2时设备M1不空闲,即M2故障,M1正常工作且缓冲区B1不满；（c）系统处于X1,3时设备M2不空闲,即M1故障,M2正常工作且缓冲区B1不空.

二级子系统Sub1处于X1,2状态时,其缓冲区B1“稳态”由其缓冲区初始状态、设备M1生产速率、设备M2的维护时间共同决定.此种情况下能保证二级子系统正常工作的概率可表示如下：

式中：Numi,j,0为Subi处于Xi,j状态时,缓冲区Bi中的在制品数量；PNumi,j,0为Subi处于Xi,j状态且Bi中在制品数量为Numi,j,0时,系统正常工作的概率；Num1,2,0∈Z,0≤Num1,2,0≤V1,且Num1,2,0服从的概率分布.

当二级子系统Sub1处于X1,3状态情况时,能保证二级子系统正常工作的概率可表示如下：

式中：Num1,3,0∈Z,0≤Num1,3,0≤V1,且Num1,3,0服从的概率分布.

当二级子系统Sub1缓冲区非空时,其稳态可用度可表示为

当二级子系统Sub1缓冲区为空时,其稳态可用度可表示为

3 串行生产线可用度

结合串行生产线的可靠性规律,由二级子系统

Sub1等效的虚拟设备M11的各种参数可以表示为

通过二级子系统的虚拟设备等效操作,并利用公式（4）～（18）便可求解出等效后的虚拟二级子系统的可用度.对于n台设备的串行生产系统,其虚拟设备的等效过程如图7所示.

等效过程的核心步骤描述如下：

Step1 将n台设备的串行生产系统拆解成i个二级子系统,其中i＝⎿n／2」.

若n＝2i,可以得到Sub1＝｛M1,B1,M2｝, Sub2＝｛M3,B3,M4｝…Subi＝｛M2i－1,B2i－1,M2i｝等i个二级串行子系统.

若n＝2i＋1,分解后可以得到i个二级子系统Sub1＝｛M1,B1,M2｝,Sub2＝｛M3,B3,M4｝,…Subi＝｛M2i－1,B2i－1,M2i｝和未能分解到二级子系统中的Mn.利用式（4）～（18）求解Subi的可用度并将其虚拟成为设备,并利用、Mn、Bn－1构成的二级子系统代替原有的Subi.

图7 二级子系统迭代过程Fig.7 Iteration process of subsystem

Step2 利用式（4）～（18）求解Step1中所得到的二级子系统的可用度,并将其虚拟成为设备｛,,…,｝.虚拟得到的i个设备｛,,…,｝和Step1中分解二级子系统所剩下的i－1个缓冲｛B2,B4,…,B2（i－1）｝构成新的串行生产线.

Step3 重复Step1和Step2步骤,最终可以得到原串行生产线等效二级子系统｛,B2k,｝,其中2k≤n,2k＋1≥n.利用式（4）～（18）便可以得到｛, B2k,｝的可用度,即串行生产线可用度的等效值.

串行生产线稳态可用度可表示为

4 求解算法

本文所研究的问题具有NP-Hard特性,传统的运筹学方法很难对其求解,而遗传算法隐含全局并行搜索特性非常适合本问题的求解,为此利用遗传算法来求解该目标函数.

遗传算法求解缓冲区设置问题的主要步骤描述如下：

Step1 初始化种群

Step2 个体评价

将初始种群代入所构建的可用度评价模型中,利用模型求解出各可行解的系统可用度,每条染色体的适应度值f（G）为其所对应系统的系统可用度,即A＝f（V1,V2,……,Vn－1）.

Step3 种群进化

1）选择运算

2）交叉运算

从种群中选择一对染色体α＝｛α1,α2,…,αK｝、β＝｛β1,β2,…,βK｝,根据一定的交叉概率pc进行单点交叉,得到子代染色体δ1、δ2,其中

3）变异运算

4）保留最优染色体

父代中适应度最大的染色体直接保留在子代种群中.

Step4 终止检验

反复执行Step3若干次,直到种群的最优适应度值达到稳态状态,并输出种群中适应度最大的染色体个体作为最优解.

图8 染色体编码Fig.8 Chromosome encoding

5 算例分析

为了有效评价本文所提出的串行生产线可用度评价模型和缓冲区分配方法,本文结合实际工程应用需求,分别以包含5～10设备的串行生产线L5～L10为例进行算例分析,其中Li为包含i个设备的串行生产线.串行生产线中的设备参数如表1所示,其中各设备的操作时间t1＝1 s,设备故障密度函数和修复时间密度函数都服从负指数分布,分别为

串行生产线Li中设备按照从前向后的顺序为M1,M2,…,Mi.

基于本文所构建的可用度评价模型,利用遗传算法对6个串行生产线L5～L10分别按照总缓冲容量为120、150、180、210、240、270进行缓冲容量分配.其种群大小50,交叉率0.4,变异概率0.001,进化迭代次数200次,模型运行结果如图9所示,L5～L10系统可用度在模型迭代过程中不断优化,并在若干次迭代后最终趋于平稳,即缓冲区容量达到了较优的分配.

图9 不同串行生产线的缓冲分配方案Fig.9 Solution of BAP for different serial production lines

其中系统L5、L6、L7在模型运行过程中可用度的变化过程参考图9中左边的主坐标轴,系统L8、L9、L10参考图9中右边的辅坐标轴.所得到的各系统缓冲分配方案、系统可用度和搜索时间t2,如表2所示.

表2 缓冲区分配方案及系统可用度Tab.2 Solution of BAP and availability

为评价所构建评价模型在缓冲区分配问题上的有效性,本文将基于可用度评价模型得到的缓冲区分配结果与基于DDX［12-13］评价方法得到的缓冲区分配方案进行比较.此处,本文采用仿真模拟方法进行验证比较,即将2个模型所得到的缓冲区分配方案输入仿真模型,比较不同缓冲区分配方案下系统的性能.简化表示,利用M1表示基于DDX评价方法的缓冲区分配模型,M2表示基于可用度评价模型的缓冲区分配模型.

针对算例系统L5～L10,M1所得到的缓冲区分配方案及可用度如表3所示.

表3 M1所得缓冲区分配方案及产出率Tab.3 Solution of BAP and throughput based on M1

利用Witness分别为不同参数下的串行生产线L5～L10建立仿真模型,运行105个单位时间后,仿真结果如表4所示,表中asi为缓冲区Bi中的平均在制品数量；CW为各缓冲区平均在制品数量总和；E为串行生产线产出率.

表4 Witness仿真结果Tab.4 Result of Witness simulation

由表4可知,M1和M2所得到的缓冲区分配方案所得到的系统产出率相同,即2种方法都可以有效地进行缓冲区容量分配.但2种方法在控制系统在制品数量和评价系统产出率的效果上有所区别,其中在制品数量控制效果如图10所示,

图10 在制品总量控制比较Fig.10 Comparison of conwip controlling ability

由图10可知,对于不同的设备数量（5～10）,系统中在制品数量与设备数量并不存在一定的单调性.但在相同设备数量下,M2比M1能够更好的实现在制品数量控制.

算例分析中各设备加工时间t1＝1 s,因此M2所得到的系统可用度数值上等于系统产出率［14］.为此,对于M1和M2在评价系统产出率效果的比较如图11所示.

由图11可知,对于所有算例,M1和M2所得的产出率都与仿真结果有着一定的差距,但M2所得到的系统产出率更加贴近实际的仿真结果.因此相比M1而言,M2对串行生产系统的产出率评价效果更好.

图11 系统产出率评价效果比较Fig.11 Comparison of throughput assessment ability

图12 搜索时间比较Fig.12 Comparison of searching time

由表2、3和4可得,M1和M2这2种方法都能找到较优解,但其搜索速度有所区别.如图12所示,对于不同的设备数量（5～10）,搜索时间会随着设备数量的增加而增加.总体来说,在相同设备数量下, M2所需的时间要比M1少.

综上所述,对于上述算例系统,通过M1、M2这2种方法都可以得到较优的缓冲区配置方案,但M2方法在控制系统在制品数量和评价系统产出率方面效果更好.

6 结 语

本文提出的基于可用度评价的串行生产线缓冲区容量分配方法可优化串行生产线中缓冲区分配问题,同时为求解缓冲区分配问题提供了新思路.在控制系统在制品总量上,对比目前文献中的基于DDX缓冲区容量分配方法,本文所构建的方法有明显的优势.在系统产出率评价方面,该方法能够有效地改善串行线生产线的产出率.

（References）：

［1］MANITZ M.Queueing-model based analysis of assembly lines with finite buffers and general service times［J］.Computers&Operations Research,2008,35（8）：2520-2536.

［2］COLLEDANI M,TOLIO T.Integrated analysis of quality and production logistics performance in manufacturing lines［J］.International Journal of Production Research,2011,49（2）：485-518.

［3］DEMIR L,TUNALI S,ELIIYI D T.An adaptive tabu search approach for buffer allocation problem in unreliable non-homogenous production lines［J］.Computers& Operations Research,2012,39（7）：1477-1486.

［4］ABDUL-KADER W,GANJAVI O,BAKI F.A nonlinear model for optimizing the performance of a multiproduct production line［J］.International Transactions in Operational Research,2011,18（5）：561-577.

［5］BATTINI D,PERSONA A,REGATTIERI A.Buffer size design linked to reliability performance：A simulative study［J］.Computers&Industrial Engineering, 2009,56（4）：1633-1641.

［6］SHI Chuan,GERSHWIN S B.An efficient buffer design algorithm for production line profit maximization［J］.International Journal of Production Economics, 2009,122（2）：725-740.

［7］AKSOY H K,GUPTA S M.Near optimal buffer allocation in remanufacturing systems with N-policy［J］.Computers&Industrial Engineering,2010,59（4）：496 -508.

［8］HELBER S,SCHIMMELPFENG K,STOLLETZ R, et al.Using linear programming to analyze and optimize stochastic flow lines［J］.Annals of Operations Research,2011,182（1）：193-211.

［9］PAN Xiao-yong,WU Jiang,ZHANG Quan-wei,et al.The study of buffer allocation problem in complex production line［J］.TELKOMNIKA Indonesian Journal of Electrical Engineering,2014,12（3）：2342-2349.

［10］HILLIER M.Designing unpaced production lines to optimize throughput and work-in-process inventory［J］.IIE Transactions,2013,45（5）：516-527.

［11］BATTINI D,FACCIO M,PERSONA A,et al.Buffer design for availability：a new simulative study in case of infant and random failures［J］.International Journal of Services and Operations Management,2013,14（2）：157-174.

［12］DALLERY Y,DAVID R,XIE Xiao-lan.Approximate analysis of transfer lines with unreliable machines and finite buffers［J］.IEEE Transactions on Automatic Control,1989,34（9）：943-953.

［13］NAHAS N,AIT-KADI D,NOURELFATH M.A new approach for buffer allocation in unreliable production lines［J］.International journal of production economics,2006,103（2）：873-881.

［14］HOPP W J,SPEARMAN M L.工厂物理学［M］.北京：清华大学出版社,2002：248-283.

Buffer allocation method for series production lines based on availability assessments

ZHOU Bing-hai,YU Jia-di,SHAO Jian-yi
（School of Mechanical Engineering,Tongji University,Shanghai 201804,China）

To quickly and effectively solve buffer allocation problems and improve the availability and throughput of series production lines,a buffer allocation method based on availability assessments was proposed.Combining with the characteristic of serial production lines and the Markov theory,an availability assessment model was structured based on the analysis of the machine and buffer states transition rule.On the basis of the descriptions mentioned above,a genetic algorithm for solving buffer allocation problems was constructed.Numerical examples were presented to show the solving process of buffer allocation problems.To verify and evaluate the accuracy of the mathematical model,the proposed method was compared with other methods from the aspects of throughput and the number of work-in-process.The results indicate that the proposed allocation method is feasible and valid for buffer allocation problems.

series production line；buffer allocation；availability assessment；Markov

10.3785／j.issn.1008-973X.2015.05.012

TP 16

A

1008-973X（2015）05-0893-08

2014-10-17. 浙江大学学报（工学版）网址：www.journals.zju.edu.cn／eng

国家自然科学基金资助项目（61273035,71471135）；国家“863”高科技研究发展计划资助项目（2009AA043000）.

周炳海（1965－）,男,教授,博导,从事预防性维护建模,制造系统／物流系统调度、建模、仿真的研究.E-mail：bhzhou＠tongji.edu.cn