时间限制下单一最小路径输送之系统可靠度评估方法

摘要

一种时间限制下单一最小路径输送之系统可靠度评估方法，此单一最小路径系由一流量网路之一起点及一终点之间的数个传输边所组成。该方法之步骤如下：提供一模拟该流量网路的虚拟网路于一电脑中；输入一待传输物的需求量、成本限制及时间限制；将需求量分布于该虚拟网路之某一最小路径中，依据需求量及时间限制，以计算一容量向量，用以表示流量网路的流量分布状态；在此容量向量下，检查该最小路径传送该需求量之传输成本是否满足成本及时间限制；藉此定义一下界向量；计算任一最小路径的容量向量大于或等于下界向量的机率，即为系统可靠度。

主权项

一种时间限制下单一最小路径输送之系统可靠度评估方法，系利用一电脑执行一可靠度评估软体，以评估一实体流量网路之一系统可靠度，该电脑具有一输入单元、一运算单元及一输出单元，该可靠度评估软体系提供一虚拟网路，以模拟该实体流量网路，该虚拟网路包括一起点、一终点及复数传输边，该些传输边位于该起点及该终点之间，并且组成复数最小路径，该方法包括：由该输入单元接受由该可靠度评估软体之一使用者所输入之一待传输物的一需求量、一时间限制及一成本限制；定义该需求量系通过单一的一最小路径而进行传送，其中该最小路径系选自该虚拟网路之该些最小路径之其一；定义一传输时间，其中该传输时间系为将该需求量从该虚拟网路之该起点传送至该终点所需的时间，并且该传输时间系小于或等于该时间限制；根据该需求量、该时间限制，以及该传输时间所组成之一关系式，求算该最小路径的每一该传输边于每单位时间内所传送之一最大传输量，其系为该传输边之一负荷量；定义一容量向量，其由该最小路径之该些传输边的该些负荷量所组成，该些负荷量的数值系为随机性的变化，以对应该实体流量网路的流量分布状态；定义一传输成本，其中该传输成本系为将该需求量从该虚拟网路之该起点传送至该终点所需的成本；藉由该运算单元执行一成本检查，以检查该最小路径传送该需求量之该传输成本是否超过该成本限制；在该最小路径的该传输成本小于或等于该成本限制，并且该传输时间小于或等于该时间限制时，定义该容量向量为一下界向量；计算该虚拟网路之任一路径的容量向量大于或等于该些最小路径的该些下界向量的机率，并定义该机率为该实体流量网路的一系统可靠度；以及显示该系统可靠度于该输出单元上。如申请专利范围第1项所述之时间限制下单一最小路径输送之系统可靠度评估方法，其中将该需求量分布于该些最小路径之其一的步骤包括：找出该虚拟网路之该些最小路径，其中每一该最小路径系为该起点至该终点之间的该些传输边之一有序集合，并且没有任何回圈；计算每一该最小路径之一流量；将每一该最小路径的该流量转换成每一该传输边目前的该负荷量。如申请专利范围第2项所述之时间限制下单一最小路径输送之系统可靠度评估方法，其中计算该最小路径之该流量的步骤包括：对该最小路径的每一该传输边提供一前置时间，其中该些传输边的该些前置时间之总和系定义为该传输时间减去将该需求量除以该最小路径之该流量的结果值；利用该传输时间小于或等于该时间限制之关系式，求出该最小路径之该流量；以及当该最小路径之该流量小于该最小路径之一最大容量时，判断该最小路径之该下界向量存在。如申请专利范围第1项所述之时间限制下单一最小路径输送之系统可靠度评估方法，其中该成本检查之步骤包括：计算该最小路径传送该需求量时的该传输成本；比较该传输成本与该成本限制之数值大小；以及依据该传输成本与该成本限制之数值大小关系，判断该最小路径之该下界向量是否存在。如申请专利范围第1项所述之时间限制下单一最小路径输送之系统可靠度评估方法，其中上述计算该系统可靠度之步骤系包括交集互斥法、不交集事件法或状态空间分解法。如申请专利范围第1项所述之时间限制下单一最小路径输送之系统可靠度评估方法，更包括：定义该流量网路之传输能力的一期望值为该系统可靠度与该需求量的乘积。如申请专利范围第1项所述之时间限制下单一最小路径输送之系统可靠度评估方法，更包括：定义该流量网路之传输时间的一期望值为该系统可靠度与该时间限制的乘积。