简介：製造系統是一由物料搬運設施來連接各工作站所形成的網路系統。為了提高生產力，吾人必須評估製造系統的績效，以將系統之設計參數最佳化，進而發展控制運作的方針。在典型的製造系統中，工件完成前須經過不同工作站的處理。若工件到達時，工作站正在忙碌，則它必須在佇列中等候。這個簡單的事實使得等候網路模式能適宜地應用於製造系統之分析與設計。本文乃應用等候網路理論，在製造系統中各站的區域儲存區為有限容量的情況下，建立一分析模型，以評估製造系統之作業績效。
關鍵詞：製造系統、等候網路、阻塞、績效評估
排队网络被广泛地用于模拟柔性制造系统的系统设计及系统性能分析中。由于许多实际的柔性制造系统是由一个工件运送系统和一组加工域所组成，每个加工域包含数台机床及一个(或两个)有限容量的局部库区，这意味着在实际系统中循环的零件常常会遇到堵塞情况。近年来，排队网络模式被广泛地应用于复杂系统分析，特别是弹性制造系统的规划与计算机系统的分析，但大多数的模式均假定制造系统中存储空间容量是无限的，即未考虑阻塞问题。根据Hopp的固定数量在制品协议，当工件完成其所有的作业并准备离开制造系统时，新的工件方被指派至系统中以取代完成的工件。因此，在开放式模型中，在制品存货是系统绩效的衡量值;而在封闭式模型中它却成了一个控制参数。本文以允许阻塞的封闭式排队网络模式，评估存储区为有限容量的制造系统作业绩效。
1 封闭式排队网络模型及算法
Gordon将排队理论中的M/M/si队列推广为任意连接的封闭式排队网络。网络中共有M个节点，节点i有si位服务者。各节点实行先到先服务(FCFS)规则，其服务时间为互相独立的指数分配，且有无限容量的排队空间。封闭式网络中不论是外来的输人或离开都不被允许。封闭式排队网络在任一时点的状态空间是M维的向量，其中ni为第i站的顾客人数，N为封闭式排队网络系统中的顾客总数，所有可能的状态所形成的状态空间为:
可以证明 当排队网络的稳定状态存在时，网络中节点i的运作具有泊松分布ai，ai为下列流量平衡方程式的解:
式中:凡为从节点i向节点j转移的概率。如节点i的相对利用率小于1，则稳定状态存在。可以证明稳定状态的分布为:
式中fi(ni)为泊松分布密度函数。具有乘积形式解的排队网络模式虽然比一般排队网络模式有更多的假设限制，但其有解析解，而且可适当地修正模式，因此有很大的应用空间。式(3)即为具有乘积形式的稳定状态概率分配的解析解，只要求出正规化常数G(N,M)，就可计算排队网络的相关绩效衡量。例如，顾客的平均排队时间与长度。
具有乘积形式解的封闭式排队网络的求解算法以Buzen折积算法，和Reiser均值分析算法为主，其余的算法大都是这两种方法的延伸。Chandy指出除了均值分析算法外，所有的算法都须明确地决定正规化常数。折积算法与均值分析算法在计算上各有其优缺点，Reiser指出均值分析算法的主要优点是快速且容易实施，但当其涉及具有负载相关服务者网络时，易产生数值上的不稳定;而折积算法在实施上较准确，但记忆储存空间大且易发生浮点运算溢位的问题。因此，当网络中无负载相关服务者或多重服务者时，则均值分析算法是较优选择;而当网络中有负载相关服务者时，选择折积算法或均值分析算法应该根据所需的结果而定。
nextpage 2 封闭式排队网络在制造系统绩效评估中的应用
制造系统是一由物料搬运设施来连接各工作站所形成的网络系统，采用排队网络模式对其进行分析，可获得以下的制造系统绩效衡量。
1)产能及产出衡量:所谓产出即在给定的工件输人下，完成工件离开系统的频率;而产能即为工件输人趋近无穷大时的最大产出率。
2)流程时间相关衡量:包括工件在系统的平均流程时间和在各机器的平均流程时间。
3)在制品相关衡量:包括系统中的平均总工件数及各机器中的平均工件数。
4)其他衡量:工件阻塞时间、机器闲置时间及机器利用率等。
以下先分析制造系统的实体运作，并应用具乘积形式的封闭式排队网络，评估区域存储区为有限容量的制造系统作业绩效。
2.1 具有阻塞影响的系统描述
本文建立以下有关制造系统的假设:
1)共有M个工作站，N个托板;每一托板均属于同一等级。
2)工作站由中央型MHS中央存储区)来连接(见图1)。
图1 制造系统概念性架构
3)工作站(节点)i有si台机器(服务者)和固定有限的区域储存容量K(i=1,2,...,M)，其中各站区域存储区兼具输人存储区与输出存储区的功能，所以每一工作站的最大工件数量是，以防止死锁情况的发生。
4)每一计划中的作业时间为指数分配，作业顺序可被转换成稳定的转移概率....M)。
5)采用先到先服务与先阻塞先解除的规则。
根据通常采用的物流策略，工作站将工件处理完毕时，应由以下程序决定:首先决定是否将工件运送到下游的工作站存储区;如果下游工作站储存区已满，尝试将工件运送到中央存储区;如果上述两存储区均已满，且目前工作站的存储区尚有空位，则工件应在目前的工作站储存区排队;假如目前的工作站存储区都已满，则机器阻塞且停止。
由以上分析可知，制造系统中工作站的状态应有三种:忙碌、闲置与阻塞。其中忙碌状态表示工作站正在处理工件;闲置状态即指输人存储区没有工件在排队处理;阻塞发生是因输出存储区(包括下游工作站、中央及目前工作站存储区)已满。
nextpage 2.2 消除阻塞的内部相互关系
截至目前为止，允许阻塞发生排队网络模式尚无法求出解析解，因此以无阻塞封闭式排队网络模式(CAN-Q)建立下面三个基本程序，来消除阻塞内部相互关系，以求得制造系统的绩效衡量(见图2)。
图2 消除阻塞的相互关系程序图
下面讨论消除工作站间的阻塞相互关系的近似计算。首先根据物流策略，认为阻塞情形发生时，下列五种情况必须同时存在。
1)工件在工作站i已处理完毕，且根据转移概率，运送至工作站j。
2)下游工作站j的区域存储区已满，以概率##来度量。
3)中央存储区已满，以概率来度量。
4)目前所在的工作站i区域存储区已满，以概率来度量。
5)如果目前工作站i的区域存储区没有尚待处理工件，则阻塞不会发生。
其中最后一种情况较不易量化，以Fi近似表示工作站i区域存储区全为已完成工件的概率:
式中:为工作站j可用的中央存储区空间;为工作站实际可用存储总空间。
由于阻塞延长工件在工作站的停留时间，且因为工作站的处理时间均为指数分布，所以其剩余处理时分配与原分布相同。因此，依据式(5)来修正各站的处理时间平均处理时间
:
2.3 算法描述
启发式算法(BLKQ)中所需要的参数，除了各工作站的存储区容量和中央存储区容量外，其余均与CAN-Q的输人参数相同，算法步骤如下。
1)输人工作站数、封闭式网络工件总数、产品种类、各站机器数与存储区容量(MHS尚须输入平均搬运时间)以及各产品制造计划及产品组合。
2)计算各站相对工作负荷与正规化常数。
3)由正规常数求出系统及各站的绩效衡量。
4)根据计算各站近似期望完工工件数与各站全为已完成工件的近似概率，并以式(4)来量化阻塞发生的五种情况，以便修正各站的平均处理时间。
5)令第k次反复时，上游工作站为i，下游工作站
nextpage 2.4 应用实例
本文第2.3节所提出的BLKQ算法，已在个人计算机上以FORTRAN语言程序化，所有范例的误差界限ε均为 。
运用BLKQ算法对制造系统进行各种绩效衡量，再利用这些绩效衡量找出瓶颈现象之所在。今以Solberg(1980,1981)模式中的数据，考虑一个四站(包括MHS )的制造系统(见表1)，生产两种产品(见表2和表3)，产品组合为两种产品均等分配，即每一产品占总产出量之比例是相等的。
系统中的总工件数由15开始往上逐渐增加，以了解阻塞情形对绩效衡量的影响。表4显示增加系统中的工件数对生产率、在系统中的平均时间以及算法反复次数对系统均会有影响。其中生产率B与平均流程时间B为采用BLKQ所产生的结果，生产率C与平均流程时间C为采用CAN-Q所产生的结果，故由表4可了解到使用无阻塞封闭式排队网络模式(采用CAN-Q)与允许阻塞发生的封闭式排队网络模式(采用BLKQ)的显著差异。当总工件数为15时，BLKQ模式所产生的结果，与CAN-Q模式完全相同。当阻塞情形一旦发生(总工件数超过巧时)，两者之间的差异就会显现出来。
表1 制造系统中工作站
normal style="TEXT-ALIGN: center" align=center>工作站
normal style="TEXT-ALIGN: center" align=center>名稱
normal style="TEXT-ALIGN: center" align=center>平均處理時間
normal style="TEXT-ALIGN: center" align=center>1
normal style="TEXT-ALIGN: center" align=center>搬運工具
normal style="TEXT-ALIGN: center" align=center>4 min.
normal style="TEXT-ALIGN: center" align=center>2
normal style="TEXT-ALIGN: center" align=center>銑床
normal style="TEXT-ALIGN: center" align=center>參見各產品的製程計劃
normal style="TEXT-ALIGN: center" align=center>3
normal style="TEXT-ALIGN: center" align=center>鑽床
normal style="TEXT-ALIGN: center" align=center>參見各產品的製程計劃
normal style="TEXT-ALIGN: center" align=center>4
normal style="TEXT-ALIGN: center" align=center>檢驗站
normal style="TEXT-ALIGN: center" align=center>參見各產品的製程計劃
表2 产品1的制造计划
normal style="TEXT-ALIGN: center" align=center>作業
normal style="TEXT-ALIGN: center" align=center>工作站
normal style="TEXT-ALIGN: center" align=center>時間
normal style="TEXT-ALIGN: center" align=center>頻率
normal style="TEXT-ALIGN: center" align=center>1
normal style="TEXT-ALIGN: center" align=center>銑床
normal style="TEXT-ALIGN: center" align=center>20 min.
normal style="TEXT-ALIGN: center" align=center>1
normal style="TEXT-ALIGN: center" align=center>2
normal style="TEXT-ALIGN: center" align=center>鑽床
normal style="TEXT-ALIGN: center" align=center>30 min.
normal style="TEXT-ALIGN: center" align=center>1
normal style="TEXT-ALIGN: center" align=center>3
normal style="TEXT-ALIGN: center" align=center>檢驗站
normal style="TEXT-ALIGN: center" align=center>15 min.
normal style="TEXT-ALIGN: center" align=center>.5
normal style="TEXT-ALIGN: center" align=center>4
normal style="TEXT-ALIGN: center" align=center>銑床
normal style="TEXT-ALIGN: center" align=center>14 min.
normal style="TEXT-ALIGN: center" align=center>1
表3 产品2的制造计划
normal style="TEXT-ALIGN: center" align=center>作業
normal style="TEXT-ALIGN: center" align=center>工作站
normal style="TEXT-ALIGN: center" align=center>時間
normal style="TEXT-ALIGN: center" align=center>頻率
normal style="TEXT-ALIGN: center" align=center>1
normal style="TEXT-ALIGN: center" align=center>鑽床
normal style="TEXT-ALIGN: center" align=center>90 min.
normal style="TEXT-ALIGN: center" align=center>1
normal style="TEXT-ALIGN: center" align=center>2
normal style="TEXT-ALIGN: center" align=center>銑床
normal style="TEXT-ALIGN: center" align=center>30 min.
normal style="TEXT-ALIGN: center" align=center>1
表4 CAN-Q与BLKQ的比较及系统中的工件数对绩效衡量影响
normal style="TEXT-ALIGN: center" align=center>總工件數
normal style="TEXT-ALIGN: center" align=center>生產率B
normal style="TEXT-ALIGN: center" align=center>生產率C
normal style="TEXT-ALIGN: center" align=center>平均流程時間B
normal style="TEXT-ALIGN: center" align=center>平均流程時間C
normal style="TEXT-ALIGN: center" align=center>反覆次數
normal style="TEXT-ALIGN: center" align=center>備註
normal style="TEXT-ALIGN: center" align=center>15
normal style="TEXT-ALIGN: center" align=center>2.960
normal style="TEXT-ALIGN: center" align=center>2.960
normal style="TEXT-ALIGN: center" align=center>304.04
normal style="TEXT-ALIGN: center" align=center>304.02
normal style="TEXT-ALIGN: center" align=center>2
normal style="TEXT-ALIGN: center" align=center>收斂
normal style="TEXT-ALIGN: center" align=center>16
normal style="TEXT-ALIGN: center" align=center>2.968
normal style="TEXT-ALIGN: center" align=center>2.969
normal style="TEXT-ALIGN: center" align=center>323.41
normal style="TEXT-ALIGN: center" align=center>323.38
normal style="TEXT-ALIGN: center" align=center>2
normal style="TEXT-ALIGN: center" align=center>收斂
normal style="TEXT-ALIGN: center" align=center>17
normal style="TEXT-ALIGN: center" align=center>2.975
normal style="TEXT-ALIGN: center" align=center>2.975
normal style="TEXT-ALIGN: center" align=center>342.87
normal style="TEXT-ALIGN: center" align=center>342.84
normal style="TEXT-ALIGN: center" align=center>2
normal style="TEXT-ALIGN: center" align=center>收斂
normal style="TEXT-ALIGN: center" align=center>18
normal style="TEXT-ALIGN: center" align=center>2.980
normal style="TEXT-ALIGN: center" align=center>2.980
normal style="TEXT-ALIGN: center" align=center>362.41
normal style="TEXT-ALIGN: center" align=center>362.39
normal style="TEXT-ALIGN: center" align=center>2
normal style="TEXT-ALIGN: center" align=center>收斂
normal style="TEXT-ALIGN: center" align=center>19
normal style="TEXT-ALIGN: center" align=center>2.874
normal style="TEXT-ALIGN: center" align=center>2.984
normal style="TEXT-ALIGN: center" align=center>396.72
normal style="TEXT-ALIGN: center" align=center>382.00
normal style="TEXT-ALIGN: center" align=center>3
normal style="TEXT-ALIGN: center" align=center>收斂
normal style="TEXT-ALIGN: center" align=center>20
normal style="TEXT-ALIGN: center" align=center>2.871
normal style="TEXT-ALIGN: center" align=center>2.987
normal style="TEXT-ALIGN: center" align=center>417.99
normal style="TEXT-ALIGN: center" align=center>401.68
normal style="TEXT-ALIGN: center" align=center>3
normal style="TEXT-ALIGN: center" align=center>收斂
normal style="TEXT-ALIGN: center" align=center>21
normal style="TEXT-ALIGN: center" align=center>2.870
normal style="TEXT-ALIGN: center" align=center>2.990
normal style="TEXT-ALIGN: center" align=center>439.08
normal style="TEXT-ALIGN: center" align=center>421.40
normal style="TEXT-ALIGN: center" align=center>3
normal style="TEXT-ALIGN: center" align=center>收斂
normal style="TEXT-ALIGN: center" align=center>22
normal style="TEXT-ALIGN: center" align=center>2.869
normal style="TEXT-ALIGN: center" align=center>2.992
normal style="TEXT-ALIGN: center" align=center>460.01
normal style="TEXT-ALIGN: center" align=center>441.17
normal style="TEXT-ALIGN: center" align=center>3
normal style="TEXT-ALIGN: center" align=center>收斂
normal style="TEXT-ALIGN: center" align=center>23
normal style="TEXT-ALIGN: center" align=center>2.870
normal style="TEXT-ALIGN: center" align=center>2.994
normal style="TEXT-ALIGN: center" align=center>480.82
normal style="TEXT-ALIGN: center" align=center>460.98
normal style="TEXT-ALIGN: center" align=center>3
normal style="TEXT-ALIGN: center" align=center>收斂
normal style="TEXT-ALIGN: center" align=center>24
normal style="TEXT-ALIGN: center" align=center>2.871
normal style="TEXT-ALIGN: center" align=center>2.995
normal style="TEXT-ALIGN: center" align=center>501.51
normal style="TEXT-ALIGN: center" align=center>480.82
normal style="TEXT-ALIGN: center" align=center>3
normal style="TEXT-ALIGN: center" align=center>收斂
normal style="TEXT-ALIGN: center" align=center>25
normal style="TEXT-ALIGN: center" align=center>2.405
normal style="TEXT-ALIGN: center" align=center>2.996
normal style="TEXT-ALIGN: center" align=center>623.62
normal style="TEXT-ALIGN: center" align=center>500.68
normal style="TEXT-ALIGN: center" align=center>10
normal style="TEXT-ALIGN: center" align=center>收斂
normal style="TEXT-ALIGN: center" align=center>26
normal style="TEXT-ALIGN: center" align=center>2.385
normal style="TEXT-ALIGN: center" align=center>2.997
normal style="TEXT-ALIGN: center" align=center>654.06
normal style="TEXT-ALIGN: center" align=center>520.56
normal style="TEXT-ALIGN: center" align=center>11
normal style="TEXT-ALIGN: center" align=center>收斂
normal style="TEXT-ALIGN: center" align=center>27
normal style="TEXT-ALIGN: center" align=center>2.364
normal style="TEXT-ALIGN: center" align=center>2.997
normal style="TEXT-ALIGN: center" align=center>685.35
normal style="TEXT-ALIGN: center" align=center>540.47
normal style="TEXT-ALIGN: center" align=center>12
normal style="TEXT-ALIGN: center" align=center>收斂
normal style="TEXT-ALIGN: center" align=center>28
normal style="TEXT-ALIGN: center" align=center>2.081
normal style="TEXT-ALIGN: center" align=center>2.998
normal style="TEXT-ALIGN: center" align=center>807.39
normal style="TEXT-ALIGN: center" align=center>560.39
normal style="TEXT-ALIGN: center" align=center>20
normal style="TEXT-ALIGN: center" align=center>未收斂
normal style="TEXT-ALIGN: center" align=center>29
normal style="TEXT-ALIGN: center" align=center>2.340
normal style="TEXT-ALIGN: center" align=center>2.998
normal style="TEXT-ALIGN: center" align=center>743.44
normal style="TEXT-ALIGN: center" align=center>580.32
normal style="TEXT-ALIGN: center" align=center>13
normal style="TEXT-ALIGN: center" align=center>收斂
*生產率單位為 個/小時，時間單位為分。
nextpage 3 结语
本文在制造系统为指数处理时间且允许阻塞发生封闭式排队网络的假设下，运用一个近似算法以求取制造系统的绩效衡量。这个反复算法的应用限制是收敛问题。Apostal指出除非固定点问题压缩变换能被辨识，否则算法无法收敛。另外，就近似效果而言，Wysk指出对于一般性处理时间的制造系统，应用指数分配可得到良好的近似效果。再者，根据实际的测试显示:当系统中的总工件数愈大时，反复次数就愈多，容易发生实数运算溢位。因此，对于较大系统，将使BLKQ算法遇到计算困难。但针对实际需要，BLKQ算法可作为了解和预测制造系统行为的一个起步。综上所述，以下几点可作为后续研究方向:
1)BLKQ模式中使用指数分配的服务时间，而实际的问题中尚有其他不同的分配形式，值得做进一步研究。
2)BLKQ模式仅考虑单一的工作等级，可推广至多重工作等级。
3)BLKQ算法的结果，可进一步与制造系统仿真模式的结果比较，进而验证启发式算法的正确性。
