不确定旅行时间

2024-10-06

不确定旅行时间（精选4篇）

不确定旅行时间篇1

液晶显示器的响应时间的典型测量是在黑白和白黑之间切换的时间。然而这种情况下的响应时间并非最长的响应时间, 灰阶之间切换的响应时间可能是黑白之间响应时间的数倍之长。测量灰阶时间响应和测量黑白变换的时间响应的主要区别是, 灰阶响应时间测量要求测量非常小的亮度变化 (尤其在测量一个或两个灰度级变化的响应时间时) , 而且这些亮度变化伴随着大量的噪声, 所以正确的测量方法和滤波技术变得尤为重要。而由于测量方法和滤波等信号处理技术而带来的对测量结果可靠程度的影响是必须考虑的问题[1]。

1 测量方法简述

灰阶响应时间在测量小亮度变化范围时, 对测量方法和设备的要求比测量黑白响应时间更高。正确测量灰阶响应时间需要适当的信号发生器和测量装置, 以及适当的测量技术及自动化的数据处理方法。

如图1所示, 视频信号发生器产生在两个灰阶之间变换的信号, 来驱动被测的显示设备。快速的测光装置把显示器发出的光转换成模拟电压信号来表示被测设备的响应时间变化。一个数据采集卡采集时间变化信号并将其数字化, 响应时间的定义是信号在两个阈值电压之间变化所用的时间。典型的阈值电压是信号幅度的10%和90%, 当然阈值是可以改变的。确定响应时间首先用软件确认脉冲的基线和顶线 (即脉冲幅度的0%和100%) , 然后根据这个值来确定响应时间的阈值, 进而计算出两个阈值之间的变化时间, 并用上升时间和下降时间表示。

2 测量不确定度的来源

1) 噪声。在进行灰阶响应时间测量时一个主要的问题就是如何处理好噪声对测量的影响, 灰阶响应时间要求测量出存在于大量噪声之中的亮度的微小变化。被测量的信号常常存在于噪声电平的下方。在LCD显示器的测量中有两种典型的噪声存在。一种是随机噪声, 主要由亮度闪烁噪声和热暗噪声组成。另一种是显示器的闪烁, 这是一种由于显示器自动刷新引起的周期性波动。随机性的噪声可以通过波形的多次平均或低通滤波器或二者的结合进行滤除。

2) 亮度测量装置的响应时间。亮度测量装置里的一个重要元器件是光电转换管, 它的响应时间直接影响测量结果的准确性。笔者曾看到过一款国外生产的灰阶响应时间测量系统, 其本身的光电转换时间大概在40μs。这对典型的灰阶响应时间来说, 基本可以忽略。当然也有针对更小的毫秒级的响应时间测量的光电转换器。

3) 脉冲信号底值和顶值的测量不确定度。如图2所示, 测量亮度变化引起的脉冲信号的上升时间首先要确定信号的底部和顶部的准确值, 然后才能确定最大幅度值的10%和90%点的位置, 进而读出两点间的时间差。显然, 整个信号的底值和顶值测量存在不确定度, 该不确定度必然传递到阈值, 使得10%到90%之间的变化时间有所偏差。

3 测量不确定度评定

1) 用滤波器对噪声处理过程中导致的波形失真引入的不确定度。现有灰阶响应时间测量系统中都选用了一种滤波技术, 很好地修正了滤波引起的响应时间测量失真, 而且显著改进了响应时间小于1/2滤波宽度时的测量不确定度。再结合重复测量, 使得滤波过程对响应时间测量的不确定度影响可以忽略。

2) 亮度测量装置响应时间引入的不确定度u1。根据国家计量技术规范JJF1059.1—2012“测量不确定度评定与表示”中相关说明, 由于仪器的滞后带来的不确定度按均匀分布考虑[2], 如前所述如果光电转换时间为40μs, 则由此引入的不确定度为

3) 脉冲信号底值和顶值的测量不准引入的不确定度u2[3]。如图2所示, 假设xL和xH分别代表最大值的10%和90%, 则 (tH-tL) 就是上升时间, xT和xB分别代表脉冲信号的最小值和最大值

由xL在阶跃波形曲线上以线性插值法找到相对应的时刻tL, 由xH在阶跃波形曲线上以线性插值法找到相对应的时刻tH。则阶跃信号上升时间为

可以认为xT和xB的测量误差在区间[-0.5Δx, 0.5Δx]内服从均匀分布, 则xT和xB的测量不确定度为

式中:Δx是测量系统的幅度测量误差, 可由系统技术说明书中查到。还可根据系统的数字采样存储器的存储位数和估计的采样区间计算得到Δx, 例如8位数字存储位数, 测量区间为[-3 V, 3 V], 则

xT与xB做不相关处理, 则由式 (1) 、 (2) 可得

其不确定度为

其实验方差为

其协方差为

其相关系数为

由dx=x' (t) dt, 得

不确定度为

实验标准偏差为为

实验协方差为

4.1 测量不确定度的A类评定

如表1所示, 进行10次重复测量, 应用贝塞尔法求出重复性测量引入的实验标准偏差。

平均值:=16.65 ms。

用贝塞尔公式计算单次测量的实验标准偏差[2]为

平均值的实验标准偏差[2]为

A类不确定度为

4.2 测量不确定度的B类评定

1) 亮度测量装置响应时间引入的不确定度u1。由仪器技术资料得该测量仪器的广电转换时间为40μs, 由此引入的不确定度按均匀分布考虑, 则

2) 脉冲信号底值和顶值的测量不准引入的不确定度u2。由式 (19) 得

式中:Tr为实际测量的波形上升时间, 举例中取10次测量的平均值16.65 (ms) ;sx为测试仪器的幅度测量误差Δx引入的不确定度, 按均匀分布考虑, 。此处Δx=23.4 m V, 计算同式 (4) 。 (xT-xB) 为波形的顶值和底值的幅度差, 此例中取xT-xB=5.5 V。

3) 合成不确定度

4) 扩展不确定度

5 总结

本文通过对灰阶响应时间的测量过程的过程描述和测量仪器的性能分析, 研究了显示器的灰阶响应时间的测量不确定度的主要来源和评定方法, 并结合一个实例进一步阐述了灰阶响应时间测量不确定度的评定步骤。当然, 在实践应用中应该根据所使用的测试条件和仪器的实际情况和测量方法具体分析不确定度的来源。

参考文献

[1]温娜, 张谷一.灰阶响应时间测量[J].电视技术, 2009, 33 (12) :112-114.

[2]中华人民共和国国家质量监督检验检疫总局.JJF1059.1—2012测量不确定度评定与表示[M].北京:中国标准出版社, 2013.

[3]梁志国.方波上升时间的测量不确定度[J].计测技术, 2006 (3) :43-45.

不确定旅行时间篇2

在经典的排序问题中,通常假定工件的加工时间是确定的常数。但是,在现实加工过程中,由于机器或刀具条件、工人加工水平等因素的影响,工件的加工时间存在着不确定性,并且排程是在加工前进行的,此时不可能知道其准确值。对于不确定参数的处理方法,目前最常见的就是将其看做随机变量,利用概率分布的相关概念进行随机优化。可是,不确定参数具体服从什么概率分布是很难确定的。特别是在数据信息不全或者根本没有历史数据的情况下(比如企业追求产品多样化或引入了新的加工工艺时),概率信息就更难得到了。这时,可以替代随机优化的一种方法就是本文采用的鲁棒方法(robust approach)。

同型并行机排程是现代制造生产过程中经常遇到的问题,具有重要的现实和理论意义。本文要研究的就是在加工时间不确定,且没有概率信息的情况下,以最小化工期(最大完工时间)为目标的同型并行机(P‖Cmax)的鲁棒排程问题。

Daniels和Kouvelis[1]提出了鲁棒排程的概念:确定一个排程使得它有最好的最坏情景, 即在所有可能情景下的目标值与对应最优排程的目标值相比较都表现不错。它研究了加工时间不确定情况下, 以最小化总流程时间为目标的单机器排程问题。其中, 不确定的加工时间用“情景”(每一个情景代表工件加工时间的一种可能结果)来描述,并采用两种形式表达情景:离散数据和区间数据。采用了鲁棒方法中的两种决策标准分别建立模型:最小最大遗憾(又称鲁棒偏差)和相对鲁棒性。该文指出这一问题是NP-难问题,并提出了一种分支定界方法和启发式算法进行求解。Kouvelis和Daniels[2]利用最小最大遗憾准则研究了加工时间为离散数据和区间数据时的以最小化工期为目标的两个机器的流水作业鲁棒排程。

相对于给出具体数值,给出不确定参数的区间更方便、更符合实际,所以本文中的加工时间采用区间情景来刻画,并采用最小最大遗憾准则。对于最小最大遗憾准则的概念、适用情况等可参见[3]。

最小最大遗憾准则已经应用到许多带有区间参数的组合优化问题上(如最短路、旅行商、生成树、指派、背包、最小割等[4,5,6,7,8])。这一决策准则在作业排序问题中也已经有所应用,除了Daniels和Kouvelis[1,2]的研究外,Lebedev和Averbakh[9]讨论了加工时间为具有相同中心的区间,目标为最小化总流程的单机器鲁棒排程问题,指出工件个数为偶数时,该问题可以在O(nlogn)时间内求解,工件个数为奇数时,它为NP-难问题;Montemanni[10]针对Daniels和Kouvelis[1]研究的问题提出了一种新的混合整数规划模型,通过添加有效不等式可以快速地得到精确解;Kasperski和Zielinski[11]对Daniels和Kouvelis[1]中提到的问题给出了一种近似比为2的近似算法。也有一些特例存在多项式算法,Kasperski[12]利用最小最大遗憾法研究了加工时间和交货日期为区间以最小化最大延迟为目标的单机器鲁棒排程, 其中部分工件之间存在着顺序约束,文章给出了一个复杂度为O(n4)的多项式时间算法。Averbakh[13]对加工时间为区间以最小化工期为目标的有2个工件m个机器的流水作业鲁棒排程问题进行了探讨,指出它在O(m)时间内可解。

可以看出目前最小最大遗憾准则在含有区间参数的作业排程领域的研究仅停留在单机器排程和流水作业排程问题上。而对本文研究的并行机鲁棒排程还没有展开。此外,由于Kouvelis等[1,2,9,10,11,13]研究的排程问题的目标都是线性加和的形式,而并行机排程中最大完工时间的目标是瓶颈(bottleneck)问题的形式,所以这些文献中的相关方法在本文研究中受到限制。虽然Kasperski[12]考虑的最大延迟的目标也是瓶颈问题形式,能给本文的问题一些启示,但是它的确定性问题是多项式可解的,而本文研究的并行机问题在确定情况下就已经是NP-难问题了,所以它的多项式时间算法对于本文的问题也不适用。为了求解本文的问题,采用了Mausser等[14,15,16]提出的迭代松弛算法。Mausser等[14,15,16]利用鲁棒方法(其中一篇[15]是相对遗憾决策标准,其他两篇是最小最大遗憾决策标准)研究了目标函数中含有区间参数的线性规划问题,并给出了求解最优值的迭代松弛(iterative relaxation)算法。

综上,本文研究的是工件加工时间不确定且不知道其概率分布的情况下以工期为目标的同型并行机的鲁棒排程问题,其中加工时间用区间来描述,采用最小最大遗憾作为决策准则。希望通过研究这一问题发现它的一些性质,并找到这一复杂问题的求解算法,给以后并行机鲁棒排程的研究提供理论基础。

1 问题描述及数学建模

设有n个工件,工件集为J={1,2,…,n},有m个相同的机器,机器集为M={1,2,…,m}。每个工件可以在任意一台机器上加工,加工过程中不允许被中断。工件与工件的加工时间取值相互独立,对于每一个工件i∈J,它的加工时间不确定,只知道它在 $[\underline{p}_{i}, \bar{p}_{i}]$ 区间内取值, $0 < \underline{p}_{i} \leq \bar{p}_{i}$ .用S表示所有的可能情景, s表示一个情景,且在这一情景下,每个工件的加工时间为 $p_{i}^{s} \in [\underline{p}_{i}, \bar{p}_{i}] ‚ i \in J$ .设Ω表示所有可行排程的集合,一个可行排程表示成X=[xij]n×m, X∈Ω,其中xij说明工件i是否在机器j上加工,如果是取值为1,否则取值为0,即xij∈{0,1}。由于一个工件只能被分配到一台机器上加工,所以每一行所有列的数值加和应该为1,即可行排程必须满足约束条件 $\sum_{j = 1}^{m} x_{i j} = 1 ‚ i = 1, 2, \dots, n$ . 令F(X,s)表示排程X在情景s∈S下的最大完工时间:

$F (X, s) = \max_{j \in Μ} {\sum_{i = 1}^{n} p_{i}^{s} x_{i j}} (1)$

情景s下的最优排程(即最小化最大完工时间的排程)所对应的最大完工时间用F*s表示:

$F_{s}^{*} = \min_{X \in Ω} F (X, s) (2)$

这种单一情景下最优排程的求解就相当于传统的确定情形下以工期为目标的同型并行机排程问题,是一个NP-难问题,最优解可以通过分支定界的方法求解混合整数规划得到[17]。定义排程X的最大遗憾值如下:

$Ζ (X) = \max_{s \in S} {F (X, s) - F_{s}^{*}} (3)$

使得遗憾值最大的那个情景设为s0,被称为该排程的最坏情景。如果假设最坏情景s0下的最优排程为X*,那么上式还可以写为:

$Ζ (X) = F (X, s^{0}) - F (X^{*}, s^{0}) (4)$

鲁棒排程的目标是寻找一个排程,使得它的最坏情景最好,即最大遗憾值最小:

$\begin{array}{l} \min_{X \in Ω} {Ζ (X)} \\ = \min_{X \in Ω} \max_{s \in S} {F (X, s) - F_{s}^{*}} \\ = \min_{X \in Ω} {F (X, s^{0}) - F (X^{*}, s^{0})} \end{array} (5)$

称这一优化问题为并行机的鲁棒排程问题(简称RSPMP)。

综上,问题的数学模型如下:

$\begin{array}{l} (R S Ρ Μ Ρ) \min_{X} {\max_{s \in S} [F (X, s) - F_{s}^{*}]} (6) \\ s . t . \sum_{j = 1}^{m} x_{i j} = 1, i = 1, \dots, n (7) \\ x_{i j} \in {0, 1}, i = 1, \dots, n; j = 1, \dots, m (8) \end{array}$

在情景s已知时,表示该情境下最小工期的F*s是一个常数。由上式可以看出问题(RSPMP)的目标函数是非线性的,将其转换为如下的等价形式:

$\begin{array}{l} (R S Ρ Μ Ρ^{1}) \min z \\ s . t . \max_{j \in Μ} \sum_{i = 1}^{n} p_{i}^{s} x_{i j} - F_{s}^{*} \leq z, s \in S (9) \\ (7) 和 (8) \end{array}$

将非线性约束(9)再进行转换变为:

$\begin{array}{l} (R S Ρ Μ Ρ^{2}) \min z \\ s . t . \sum_{i = 1}^{n} p_{i}^{s} x_{i j} - F_{s}^{*} \leq z, s \in S; j = 1, \dots, m (10) \\ (7) 和 (8) \end{array}$

其中, z是连续变量, xij是0-1整数变量, 可见该问题是一个混合整数规划问题。求解这一问题之前先要求解每一个情景s下的F*s, s∈S,然后将代入问题(RSPMP2)再解一个混合整数规划问题。

定理1 问题RSPMP是NP-难问题。

证明当情景个数|S|=1,设为情景s,那么RSPMP的求解就相当于确定情境下同型并行机最优排程的求解,即求解F*s.因此,可以将F*s看作是RSPMP的特例。由于F*s是一个NP-难问题, 那么比其更复杂的问题RSPMP也是NP-难的。它的等价问题RSPMP1和RSPMP2自然也是NP-难问题。

2 求解方法

由于本文中的不确定参数是用区间表示的,那么相应的情景数目就有无限多个,这样导致了上面的混合整数规划无法求解。所以本节研究原问题的一些性质,给出几个定理使问题得到简化,然后用一种迭代松弛算法来求最优解,并分析这种算法的计算量。

2.1 最坏情景的估计

下面给出在已知一个排程X时,确定它的最坏情景及最大遗憾值的方法。首先定义几个概念。对于一个排程X,在某一情境s下,如果机器c∈M满足

$\sum_{i = 1}^{n} p_{i}^{s} x_{i c} = \max_{j \in Μ} \sum_{i = 1}^{n} p_{i}^{s} x_{i j} = F (X, s)$

称该机器为X排程在情景s下的关键机器,它决定了这一排程在这一情景下的最大完工时间。

令sj表示这样的一个情景:机器j上的工件加工时间都取其对应区间的上界,其他机器上的工件加工时间取下界。

定理2 对于每一个排程X都有一个机器c∈M满足:

①情景sc是X的最坏情景,

②机器c是X在情景sc下的关键机器。

证明设s0为X的最坏情景,机器c∈M为X在s0下的关键机器,情景s0下的最优排程为X*.根据(4)可得排程X的最大遗憾值为

$\begin{array}{l} Ζ (X) \\ = \max_{s \in S} {F (X, s) - F_{s}^{*}} \\ = F (X, s^{0}) - F (X^{*}, s^{0}) \\ = \sum_{i = 1}^{n} p_{i}^{s} x_{i c} - F (X^{*}, s^{0}) \end{array} (11)$

情景sc可以由s0通过以下变化得到:将关键机器c上的工件加工时间增加到对应区间的上界,非关键机器上工件加工时间减少到下界。显而易见,机器c也是排程X在情景sc时的关键机器。

下面考虑排程X在情景s0时的关键机器c上的工件加工时间增加和非关键机器上工件加工时间减少对X的最大遗憾值的影响。

第一种情况:当工件i在关键机器c上时,若它的加工时间ps0i增加Δ, 会有F(X,s0)增加Δ, F(X*,s0)不变或增加,但增加量≤Δ,所以F(X,s0)-F(X*,s0)不会减少。

第二种情况:当工件i不在关键机器上时,若它的加工时间ps0i减少Δ,则有F(X,s0)不变, F(X*,s0)减少或不变,所以F(X,s0)-F(X*,s0)增大或不变,即不会减少。

通过上述两种情况的分析,将s0用sc替代,Z(X)的值将不会减少,所以sc是排程X的最坏情景。

给定一个排程X,令其最坏情景为sc, c∈M,满足定理2,那么c为X在情景sc下的关键机器,结合sc的定义有 $F (X, s^{c}) = \sum_{i = 1}^{n} \bar{p}_{i} x_{i c}$ ,于是Z(X)的表达式可以写成:

$Ζ (X) = F (X, s^{c}) - F_{s^{c}}^{*} = \sum_{i = 1}^{n} \bar{p}_{i} x_{i c} - F_{s^{c}}^{*} (12)$

定理3 给定一个排程X,其最大遗憾值可以表达成:

$Ζ (X) = \max_{j \in Μ} {\sum_{i = 1}^{n} \bar{p}_{i} x_{i j} - F_{s^{j}}^{*}} (13)$

证明因为(12)中c∈M,所以由(12)可以得到:

$Ζ (X) \leq \max_{j \in Μ} {\sum_{i = 1}^{n} \bar{p}_{i} x_{i j} - F_{s^{j}}^{*}} (14)$

假设存在一个机器k∈M使得 $Ζ (X) < \sum_{i = 1}^{n} \bar{p}_{i} x_{i k} - F_{s^{k}}^{*}$ .因为机器k并不一定是排程X在情景sk下的关键机器,所以 $F (X, s^{k}) \geq \sum_{i = 1}^{n} \bar{p}_{i} x_{i k}$ .那么有Z(X)<F(X,sk)-F*sk,但是这与最大遗憾Z(X)的定义矛盾。所以式(14)中只有等号成立,小于号不成立。

通过上述分析,给定一个排程X,就能确定sj, j=1,2,…,m,然后计算出F*sj,再根据定理3求得Z(X)及关键机器c,再根据定理2就可以确定出最坏情景sc.

2.2 迭代松弛算法

通过上述最坏情景的分析,了解到最大遗憾出现在工件加工时间为端点值(上界或下界)的情景,由此可以将情景集合S限制到到端点值组成的情景。然而,即便如此,端点情景也有2n个,计算量还是相当大。为此,借鉴Mausser等[14,15,16,18]提出的迭代松弛算法来求解混合整数规划问题RSPMP2的最优解。这一松弛过程首先利用有限个情景的集合Γ0来代替所有情景集合S,然后在迭代过程中不断地添加新的情景,直到求得最优解。设在第h次迭代时情景集合为Γh,此时RSPMP3的松弛问题为:

$\begin{array}{l} (R S Ρ Μ Ρ^{2} - R^{h}) \min z \\ s . t . \sum_{i = 1}^{n} p_{i}^{s} x_{i j} - F_{s}^{*} \leq z, s \in Γ^{h}; j = 1, \dots, m (15) \\ (7) 和 (8) \end{array}$

称 $\sum_{i = 1}^{n} p_{i}^{s} x_{i j} - F_{s}^{*} \leq z ‚ j = 1, 2, \dots, m$ 为一组遗憾割。每增加一个情景就会有一组遗憾割增加。设第h次迭代后, RSPMP2-Rh得到的最优解为Xh,目标值为zh,它是原问题的一个下界。利用定理2和定理3就能求出排程Xh所对应的最大遗憾值Z(Xh)及最坏情景 $\hat{s}$ h, Z(Xh)为原问题的一个上界, $\hat{s}$ h 添加到情景集合Γh中形成Γh+1,伴随产生一组遗憾割。随着情景的不断增多,约束条件增加,求解松弛问题得到的下界呈非递减趋势。所以,经过有限次迭代,上下界相等时得到的解就是最优解了。其迭代过程如下:

第一步:初始化。LB=0, Γ0=Φ, h=0, X0为中间情景(各工件的加工时间取区间的中值)时得到的最优排程。

第二步:根据定理2和定理3可以计算排程Xh的最大遗憾Z(Xh)及最坏情景 $\hat{s}$ h.

第三步:如果Z(Xh)≤LB,停止,Xh是原问题的最优解。否则,将 $\hat{s}$ h添加到情景集合Γh中形成Γh+1.

第四步:h=h+1,通过求解RSPMP2-Rh得到Xh和zh,令LB=zh,回到第二步。

下面分析这一迭代松弛算法的计算量。第一步中初始解的求解是求一个确定情境下同型并行机排程的计算量,是指数时间增长的。Mokotoff[17]提出的方法结合软件CPLEX可以快速求解这一问题。第二步中求排程最大遗憾的计算量可以由式(13)看出,主要由机器数目m及F*sj的求解决定,要求m个F*sj,而一个F*sj的求解又是一个确定问题的计算量。第四步松弛问题的求解是一个混合整数规划求解,它的计算量随着所增加的遗憾割数目的增加而增加,每迭代一次,就会增加一个情景,同时增加m个约束条件,其中F*s的求解在第二步已经得到。假设得到最优解时,迭代了H次,那么一共计算过1+mH次确定性问题。综上说明这一算法的计算时间主要取决于确定性问题的计算时间及机器数目m和迭代次数H.其中确定性问题的计算时间主要是由机器数目m和工件数目n所决定的。

3 结论

考虑到现实生活中不确定因素的普遍存在及并行机排程的实际应用价值,本文研究了加工时间不确定情况下以最大完工时间为目标的同型并行机鲁棒排程,其中各工件加工时间为区间形式,采用了最小最大遗憾作为决策准则。通过分析给出的定理1证明了该问题(RSPMP)是NP-难问题,且由于区间数据包含有无限个情景,所以无法求解其最优解。接下来通过对最坏情景的估计,定理2证明出最大遗憾只会出现在与关键机器相关的端点值情景处,定理3给出了最大遗憾值的计算公式。最后,对于该问题提出了一种迭代松弛的方法,应用此方法可以求出最优解。但是,迭代松弛方法的计算量会随着迭代次数的增加而增加且很大程度上依赖于确定情况下并行机排程的计算复杂度,计算效果令人不是很满意,所以,以后的研究可以从减少迭代次数这一点入手进行改进,还可以提出其他的近似算法。此外,最小最大遗憾在排程领域的应用目前仅停留在单机器排程和两机器的流水作业排程,未来的研究可以将其扩展到并行机的其他问题上。

摘要：在现实作业排程中,工件加工时间常常是不确定的。考虑到同型并行机的现实和理论意义,本文研究了加工时间不确定情况下以工期(最大完工时间)为目标的同型并行机排程问题。为了确定最优鲁棒排程,采用最小最大遗憾准则。其中,加工时间没有给出概率信息,而是用区间表示。经证明,该问题是一个NP-难问题且求解困难。为简化问题便于求解,本文给出了最大遗憾的计算公式,还证明出最坏情景出现在端点值,即各工件加工时间不是取区间上界就是下界。然后,提出了一种可以求出该问题最优解的迭代松弛算法并分析了其计算量。最后总结了本文的主要研究工作以及未来的研究方向。

不确定旅行时间篇3

关键词：北斗终端OEM模块测试,首次定位时间,不确定度

1 引言

北斗终端OEM模块是北斗终端的核心处理器件, 一般集成有基带芯片、射频芯片和相应的外围电路, 其性能直接决定导航终端设备的质量和性能。北斗终端OEM模块测试结果表明了北斗终端O E M模块性能的优劣, 测试结果准确度的高低客观反映测试系统的能力。首次定位时间作为北斗终端的重要被测参数之一, 测试设备系统误差和测试过程中的随机误差等因素都会影响其测试结果。一般采用不确定度来定量表示首次定位时间测试结果的可信程度, 用于评估北斗终端OEM模块首次定位时间测试结果的准确性。因此, 分析影响首次定位时间测试结果的因素, 建立合理、有效且简化的测试系统模型, 分析影响测试结果的来源是建立北斗终端OEM模块测试系统的重要任务之一。

2 不确定度的定义和来源

2.1 不确定度的定义

测量不确定度简称不确定度, 1999年公布实施的《测量不确定度评定与表示》对不确定度的定义为:不确定度用来表征合理赋予被测量值的分散性, 是测量结果含有的一个参数, 与测量结果相关联[1]。不确定度与常说的准确度相似, 但又有区别:准确度是定性的表示测试结果和“真值”之间的相近程度的概念, 无法定量给出测试结果;而不确定度是量化表示测量结果准确程度高低的数值, 可量化表示测试结果的可信程度。因此, 在实际工程测试系统中, 常采用不确定度来衡量测试系统的测试结果。

2.2 不确定度的来源

根据CNAS-GL05《测量不确定度要求的实施指南》对不确定度的分析, 测量不确定度可能来自于以下几方面:

⊙对被测量的定义不完善;

⊙实现被测量的定义的方法不理想;

⊙取样的代表性不够, 即被测量的样本不能代表所定义的被测量;

⊙对测量过程受环境影响的认识不周全, 或对环境条件的测量与控制不完善;

⊙对模拟仪器的读数存在人为偏移;

⊙测量仪器的分辨力或鉴别力不够;

⊙赋予计量标准的值或标准物质的值不准;

⊙引用于数据计算的常量和其他参量不准;

⊙测量方法和测量程序的近似性和假定性;

⊙在表面上看来完全相同的条件下, 被测量重复观测值的变化。

对于特定测试系统来说, 不确定度可能的来源包括以上的所有因素或部分因素。不同的测试系统随建立的系统模型、测试设备、测试方法、测试环境等因素的变化, 不确定度的来源也会发生相应的变化, 以上影响因素变化时, 不确定度也要随之变化。

3 不确定度的评估

3.1 标准不确定度

不同来源的因素对测量不确定度的影响不同, 评定测量标准不确定度的方法可分为三类[2]:

(1) A类标准不确定度

A类标准不确定度评估采用观测统计学分析方法进行评估, 对输入量xi进行n次独立的等精度测量, 得到的测量结果分别为:x1, x2, …, xn, 则单次测量结果的实验标准差:

式中, 为算数平均值:

观测列的不确定度为:

A类标准不确定度评估适用于稳定且在系统中考虑了B类中环境等因素的影响测量系统。A类评估方法中, 统计样本数量n影响A类标准不确定度的结果, 样本数量n越大, 不确定度结果越精确。

(2) B类标准不确定度

当输入量的估计量xi无法通过重复测量得到结果时, 则采用B类标准不确定度评估方法进行评估。B标准类不确定度评估的来源包括:校准证书、检定证书、生产厂的说明书、检测依据的标准、引用手册的参考数据、以前测量的数据、相关材料特性的知识等。若校准证书、检定证书、生产厂的说明书、检测依据标准等证书文献中给出扩展不确定度U (xi) 和包含因子k, 则xi的B类标准不确定度可根据扩展不确定度U (xi) 和包含因子k获得:

(3) 合成标准不确定度

为综合考虑A类标准不确定度和B类标准不确定的影响, 可采用合成标准不确定度的评估方法。合成标准不确定度评估公式为:

大部分测试系统的测试不确定度都是A类标准不确定度和B类标准不确定度综合的结果, 因此, 合成标准不确定度可以更全面的分析、评估测试结果, 首次定位时间测量不确定度可采用合成不确定度进行结果评估。

3.2 扩展不确定度

扩展不确定度又称报告不确定度, 是指被测对象以较高的包含概率 (通常为95%) 存在的区间宽度, 通常采用标准不确定度乘以包含因子k来计算:

当不确定度分量较多而且大小比较接近, 且为正态分布时, 包含因子可取k=2;当不确定度中支配地位分量的概率分布非正态分布时, 根据支配地位分量的分布选取包含因子k;当不确定度中A类分量比重较大且测量次数较少时, 包含因子k应查t分布表获得。一般检测报告中, 扩展不确定度应由标准不确定度和包含因子两项乘积的形式明确列出。

4 首次定位时间测试不确定度分析

4.1 北斗终端OEM模块测试系统模型

根据系统的功能要求, 可将北斗终端OEM模块测试系统简化为待测北斗OEM模块、模拟信号源、频率合成器、衰减器、控制计算机和评估计算机 (可与控制计算机为同一台) 、控制评估软件和数据服务器组成[3]。测试系统能够在模拟闭环环境中对北斗OEM模块进行测试评估:信号源为北斗O E M模块提供模拟信号;双频信号通过频率合成器形成一路信号, 经过衰减器进入待测模块;待测北斗OEM模块将接收到的模拟信号根据相应的协议解析为授时、定位、速度以及其他用户需要的数据;测试软件解析OEM模块的输出数据流并提取出待测参数, 通过与信号源的模拟控制信号参数进行对比得到相应的测试结果。测试结果和测试数据存储在数据服务器中供测试软件随时调用或进一步分析使用。测试系统模型如图1所示。

4.2 影响首次定位时间的因素

通过分析对比北斗OEM模块测试系统中的环境、样品、设备和流程等因素与不确定度来源可知, 首次定位时间测试不确定度中包括:

⊙样品OEM模块不能完全代表被测对象引起的A类不确定度;

⊙频率合成器的稳定性带来的测量误差引起的B类不确定度;

⊙衰减器的稳定性带来的测量误差引起的B类不确定度;

⊙样品OEM模块测量重复性引起的A类不确定度;

⊙配置测试场景参数差异引起的B类不确定度;

⊙测试环境差异引起的B类不确定度。

各不确定度分量的类型和分布如表1所示。

4.3 标准合成不确定度的计算

由于各不确定度分量之间互不相关, 可采用合成不确定度的近似算法:

4.4 扩展不确定度的计算

由于各不确定度分量大小相近, 且不包含占支配地位的分量, 则包含概率为95%对应的包含因子k=2。因此, 扩展不确定度可由Uc (x) =ucx) ×2计算获得。因此, 首次定位时间的扩展不确定度的算法为:

其中, 各影响因素的标准不确定度分量可由表1查询计算获得。

5 结束语

北斗终端OEM模块测试系统作为评估OEM模块性能的重要手段之一, 其测试的准确性和可信性决定了系统的测试能力。根据不确定度的定义和计算方法, 结合测试系统的简化模型, 分析影响首次定位时间的因素, 根据各不确定度分量的类型和分布计算得到测试系统的标准不确定度和扩展不确定度。若利用此类方法对各待测指标的不确定度进行分析和计算, 可对北斗终端OEM模块测试系统的测试能力进行完整的评估。

参考文献

[1]JIF1059-1999.测量不确定度评定与表示[S].

[2]CNAS-GL05.测量不确定度要求的实施指南[S].

不确定旅行时间篇4

1 数学模型

1.1 VRPTW问题描述

假设中心仓库有k辆载重均为Q的车,为n个等待客户服务,已知仓库中心和每个客户端位置坐标、客户的货物需求量和允许的服务的时间窗口以及服务时间。试寻求最优的车辆配送路线,使得分派到车辆数最少,且配送过程中的总行驶路程最短。

1.2 数学模型

式中:M为车辆数目集,M={k=1,2,…,m},m是一个待定的决策的变量;C为客户集,C={i,j=1,2,…,m},i,=0时为中心仓库;dij为客户i与客户j之间的距离;qi为客户i的需求量;sik为车辆k到达客户i的时间;si为车辆在客户i处的服务时间。

式(1)表示总行车路程最短;式(2)表示指派最少的车辆;式(3)表示从中心仓库出发点车辆数不能超过故有的车辆数m;式(4)表示每一个客户只能有一辆车辆服务且每个客户均能得到服务;式(5)表示保证车辆从中心仓库出发并最终回到中心仓库;式(6)表示每辆车辆运送的货物重量不能超过车辆的定额载荷;式(7)表示每辆车服务的客户总数不能大于客户总数目;式(8)客户i允许的服务时间窗口。

2 算法设计

2.1 染色体的编码方式及初始群体的生成

本文染色体采用自然数编码方式。即染色体V={vi},(i=1,2,…,n,vi表示染色体的基因,对应于第i个客户的编号,如,V={4,2,5,3,1}就是一条染色体。染色体中没有路线分界点的基因位。

初始群体个体初始化的方法是前相插入法,生成一个好的可行个体,然后在此个体的邻域内生成部分个体,这些个体数占初始群体规模的十分之一,余下的十分之九的个体随机产生。

2.2 适应函数的构造

本文适应函数的构造采用Murata,Ishibuchi和Tanaka提出的随机权重法(random-weight approach)[7,8]。该方法能够使得遗传算法具有可变搜索方向,在整个Pareto前沿面上进行均匀采样的能力。

设最小化的q个目标函数,权重和目标(weighted-sum objective)如下所示:

其中fk(x)=zk,k=1,2,随机权重wk由下式计算:

其中ri是非负随机数。

但是式(9)实际存在问题,那就是fk(x)之间的单位不统一,而且两者之间的数据相差几十倍,这样如果不将其进行改进,f1(x)的量有可能将f2(x)的量“淹没”,这样就会导致f2(x)这个目标值名存实亡。鉴于此,本文将其改进为:

其中fkmax,x是每一代过程中种群最大值。

2.3 交叉操作

首先随机地在染色体串中选择一个交叉区域。如两父串及交叉区域为,A=1|234|5,B=2|341|5,然后将B的交叉区域放到A的最前面,将A的交叉区域放到B的最前面,分别得到A′=34112345,B′=23423415,最后分别在A′和B′中最交叉区域后依次删除与交叉区域相同的点,得到最终交叉后产生的两个新染色体,A〃=34125,B〃=23415。该方法对维持种群的多样性有较好的作用。

2.4 变异操作

传统的均匀操作不便于对某一重点区域进行局部搜索,其局部操作能力较差,故本文采用非均匀变异操作[9]。在进行由V=v1v2…vk…vp向V'=v1v2…v'k…vp的非均匀变异操作时,若变异点vk的基因值取值范围为[Ukmin,Ukmax],则新的基因值v'k由下式确定:

式中,表示范围内符合非均匀分布的一个随机数,要求随着进化代数t的增加,接近于0的概率也逐渐增加。本文定义:

式中t是循环变量,T是最大进化代数,b是一个系统参数,决定算法的收敛压力,r是一个内均匀产生的随机数。

2.5 混合并行遗传算法

多目标优化问题的遗传算法的选择操作有并列选择法、排序选择法和共享函数法等多种方法。各种方法都有自己的优缺点[9],鉴于此,本文混合使用上述几种求解多目标优化问题的方法,尽可能的克服各自的缺点,而充分发挥各自的优点。把它叫做混合并列选择法[9],其选择过程如下:

(1)并列选择过程。按所求多目标优化问题的子目标函数的个数,将整个群体均等划分为一些子群体,各个子目标函数在相应的子群体中产生其下一代群体。

(2)保留Perato最优个体过程。在每一代的过程中,对于各个子群体中的Perato最优个体,不让其参与个体的交叉和变异运算,而是让其直接保留到下一代子群体中。这样可以避免因交叉和变异运算导致的破坏良好的染色体,加快其搜索速度。

(3)共享函数处理过程。若得到的Perato最优个体是数量已超过规定的群体规模,则需要利用共享函数法对最优个体进行挑选,以形成规定规模的新一代群体。

3 实例与分析

为了测试算法的有效性,分别采用文献[10-13]的5个典型问题进行了测试,并于目前已知的最好解进行了比较。

算法用Java语言编程,在PC586兼容机上运行。参数设置:种群规模M=100,最大进化代数为200,交叉概率pc=0.8,pm=0.001。计算最好目标值和最差目标值,然后计算平均值,测试结果如表1所示。以问题1(见表2)为例,给出所求最好解的各条路径。