不确定加工时间

2024-10-02

不确定加工时间（精选5篇）

不确定加工时间篇1

在经典的排序问题中,通常假定工件的加工时间是确定的常数。但是,在现实加工过程中,由于机器或刀具条件、工人加工水平等因素的影响,工件的加工时间存在着不确定性,并且排程是在加工前进行的,此时不可能知道其准确值。对于不确定参数的处理方法,目前最常见的就是将其看做随机变量,利用概率分布的相关概念进行随机优化。可是,不确定参数具体服从什么概率分布是很难确定的。特别是在数据信息不全或者根本没有历史数据的情况下(比如企业追求产品多样化或引入了新的加工工艺时),概率信息就更难得到了。这时,可以替代随机优化的一种方法就是本文采用的鲁棒方法(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-难问题且求解困难。为简化问题便于求解,本文给出了最大遗憾的计算公式,还证明出最坏情景出现在端点值,即各工件加工时间不是取区间上界就是下界。然后,提出了一种可以求出该问题最优解的迭代松弛算法并分析了其计算量。最后总结了本文的主要研究工作以及未来的研究方向。

关键词：同型并行机,加工时间不确定,最小最大遗憾,迭代松弛算法

不确定加工时间篇2

不确定因素作用下的柔性作业车间调度问题是在柔性作业车间调度问题 (flexiblejob-shopschedulingproblem,FJSP)的基础上,考虑车间环境的随机性和动态性,处理不确定因素对调度目标影响的一类调度算法,是车间调度领域的一类关键问题。实际的生产环节中,由于生产环境具有动态性和随机性,导致加工时间、工件到达时间和机床故障率等因素很难用一个确定的值来描述[1],因此,建立在调度参数确定情况下的柔性作业车间调度方案已经难以满足生产的需求。与此同时,不确定因素扰动下的柔性作业车间调度问题受到越来越多研究者的关注,成为目前FJSP领域的研究热点之一[2]。

对于不确定因素扰动下的作业车间调度方法主要分为动态重调度和静态预调度两类[3]。采用动态重调度方法会反复产生重调度方案[4],对扰动因素进行处理时,虽然方案具有较好的时效性,但是频繁地修正生产计划,对物料计划、人员派遣会产生连锁反应,从而造成生产混乱。静态预调度方法是提前考虑不确定因素对于调度结果的影响,提前对调度结果作出修正,但是如何对不确定因素的扰动进行描述和预测,是预调度中的一大难题。

制造过程中不确定因素的处理方法主要有随机数学方法、模糊数学方法、冗余处理方法等。Xia等[5]采用随机数学方法处理加工时间不确定的单机调度问题,设计惩罚函数对超期和提前问题进行处理。但是随机数分布往往通过大量历史数据的分析获得,而大量生产数据的统计在中小批量的生产模式中难以实现。李平等[6]采用三角模糊数来处理加工时间不确定的JobShop问题时,运用隶属度函数将连续的大数据量问题转化为离散的小数据量问题来处理。但是其隶属函数的构造对历史数据具有较强的依赖性,并不适用于产品种类多、变化快的中小批量生产模式。Zhang[7]采用冗余处理方法中的最小最大遗憾方法对批量生产环境下,需求不确定的调度问题进行求解。但是该方法计算规模较大,在处理大型问题时难以实时求解。

国内外学者大多对大批量作业车间的不确定因素处理进行研究。鲁建厦等[8]针对加工时间不确定的批量混合装配车间调度问题进行研究,运用随机数学理论对实际作业时间的波动情况进行处理;Ponsich等[9]对加工时间不确定情况下的大批量生产调度问题,采用了遗传算法进行求解。Hufner等[10]针对大批量产品生产调度问题,采用了随机整数规划方法进行处理。综上可知,学者们对于大批量问题的研究较为充分,而对于多品种小批量生产模式下的研究较少。但是,多品种小批量的作业模式因为其产品覆盖广、作业柔性高,被广泛应用于我国中小型制造业中,因此,针对多品种小批量环境下,不确定因素扰动的作业车间鲁棒调度问题具有重要意义。

本文针对多品种小批量生产模式下,加工时间不确定的柔性作业车间调度问题进行研究,采用基于冗余处理的方法处理加工时间不确定的波动问题,并建立了鲁棒预调度模型。设计了两阶段遗传算法,依次获取了问题冗余解和最优解,为缩小搜索规模,设计了顺序搜索机制,简化了搜索方式,使复杂环境下的鲁棒调度算法具有了较大的应用潜力。

1问题描述与模型建立

1.1不确定因素的处理

多品种小批量环境中,加工时间不确定的柔性作业车间调度问题具有如下特点:加工柔性高,零件种类多样多变、数量较少,工序加工时间的变化规律难以通过历史数据的统计分析得到但其大致的区间可以通过预估确定。

对于三种常用的不确定因素处理方法(随机数学方法、模糊数学方法、冗余处理方法)进行分析和对比可知:随机数学方法需要大量历史数据来构建分布函数,模糊数学方法需要历史数据来构建隶属度函数,这两种方法对历史数据依赖性大,不适用于柔性作业车间的生产模式,因此采用冗余处理方法建立数学模型。

加工时间不确定的冗余处理方法通过对加工时间进行抽样,取样本中的目标函数值和最优情况偏离最大的情况,即最大冗余情况作为调度求解中不确定因素的扰动状态,并在此状态下,对调度问题进行求解,其原理如图1所示。冗余调度方法是在最劣的时间样本下求取最优调度方案,确保在各种加工时间场景下,最优方案具有鲁棒性和性能指标的优势。

1.2基于冗余机制的鲁棒预调度模型建立

以柔性作业车间为对象,采用冗余调度方法,以最大完工时间为目标,构建考虑加工时间不确定变化的鲁棒调度模型:

约束函数:

式(1)表示目标函数为在最大冗余情况下最大完工时间达到最小时所对应的调度方案,式中X为工序调度方案的集合,S为每一道工序加工时间的集合,Cij为第i个工件、第j个工序的完工时间;式(2)表示工件的起始加工约束,表示任何工件都要求在0时刻以后开始加工;式(3)表示同一时刻同一机器只能加工一个零件,Ci1j1k表示机器k上加工的零件i1的第j1道工序的完工时间,Pi1j1表示零件i1的第j1道工序的加工时间,Qi1i2k表示机器上工序的排列顺序,其取值情况如下:

式(4)表示同一工件先后工序之间的工艺约束,且工序加工过程不存在人为中断,Ci(j-1)表示位于Cij工序的前一个工序的完工时间,Pij表示工件i工序j的加工时间;式(5)表示n个工件m个工序所对应的加工时间集合;其中Pij ∈(p1,p2,…,pt)表示该工序对应的机器共有t台,其对应的加工时间依次为(p1,p2,…,pt),当算法筛选完加工设备之后,选取相应的加工时间作为工件i工序j的加工时间;式(6)表示所有的加工时间都是有界的且在界限之间波动,分别为工件i的第j个工序的加工时间上下界的集合。

2 基于顺序搜索机制的两阶段遗传算法

2.1基于冗余调度模型的顺序搜索机制

对于加工时间不确定的冗余调度问题,首先对寻找使得目标函数的性能最为保守的冗余解然后在冗余状态下,对于寻找使f(x,s)最小的最优解,即其中,s表示各个工位的某一种加工时间状态,x表示某一种调度方案,f(x,s)表示当前调度问题的完工时间。

目前,常采用两层次嵌套的方法求解基于冗余处理的鲁棒调度[3]。对于n个工件m道工序p个机器的柔性制造系统调度问题而言,共需计算qkn×mpn×m次,其中k为加工时间样本数量,q为一次方案求解需要的计算次数,该遍历方法随问题规模增长呈指数增长,难以适应复杂问题的求解。

为提高鲁棒调度算法的求解速度,根据下述引理[11],采用顺序搜索结构搜索最优解。

由引理1和引理2可知,当f(x,s)取得可行解时,FJSP种群的最优解x1,可以同时和加工时间进化种群的最优解s1、s2配套实现最优,即两个种群的搜索进化可以互为依托,同步进行。基于此,本文采用基于顺序搜索的方式,实现快速求解。

2.2两阶段遗传算法设计

基于顺序搜索机制设计两阶段遗传算法对问题进行快速求解,其流程见图2。在第一阶段算法中,在FJSP种群空间中对加工时间种群进行搜索获取最大冗余状态;在第二阶段算法中,在加工时间种群中对FJSP种群进行搜索优化,获取最优调度结果。两阶段算法互为依托,反复搜索进化,得到最优解。

对于采用顺序搜索机制的算法,对其效率分析如下:假设染色体种群数均为N,每一次解码需要计算p次,遗传算法总共迭代计算M次,则总共需要计算机计算2MpN次。通过对比可知,采用顺序搜索的求解方式在搜索速度上达到了乘数级别,相比传统的嵌套求解方式在求解速度上具有巨大的优势。

在算法实现上,共对加工时间进化染色体、工序排列染色体、机器指定染色体三种染色体进行优化,在加工时间进化种群和FJSP优化种群两个种群空间中实现遗传算法的遗传优化。对于加工时间进化种群,选取作为适应值函数,对于FJSP优化种群,选取作为适应值函数,采用排序选择算子对染色体进行筛选;对工序排列染色体、机器指定染色体、工序时间进化染色体分别采用POX交叉方式、均匀交叉方式、双点交叉方式,采用基本位变异方法对三种染色体进行变异操作。

3案例分析

采用某公司柔性生产线实际案例对算法进行正交试验,优化算法关键参数。同时为分析算法输出方案的鲁棒性和目标性能,将标准遗传算法与本文的鲁棒调度算法输出结果进行比较,并在eM-Plant环境下建立仿真调度模型,对算法输出方案鲁棒性进行评价。

3.1参数优化和求解

采用武汉某柔性生产线10个工件、3步工序、4台机器的实际完全柔性作业案例作为源数据,采用正交试验法对遗传算法中的POX交叉概率、双点交叉概率、均匀交叉概率进行优化。对POX交叉概率的三个水平分别为A1=0.3、A2=0.5、A3=0.7,双点交叉概率的三个水平分别为B1 =0.4、B2=0.6、B3=0.8,均匀交叉概率的三个水平分别为C1=0.4、C2=0.6、C3=0.8三种情况下的算法运行结果依次进行正交测试,测试结果见表1。

为了直观显示测试结果,将数据经过处理之后以图的形式表示,如图3所示。

通过参数测试结果发现,POX交叉概率为0.5,双点交叉概率为0.8,均匀交叉概率为0.8时,算法性能表现较好。在此基础上,设置其他参数如下:重调度种群规模为20,变异概率都设置为0.005,循环次数设置为100,调度结果见图4。程序在CPU:CORETMi7-2.0GHz,RAM:4GB的环境下运行。

采用标准遗传算法和本文提出的鲁棒算法进行对比,采用相同的算法参数并在相同环境下对同一问题进行计算,其输出方案见图5。

3.2调度方案仿真与分析

在完成算法的求解之后,对方案的鲁棒性进行评价。常见的鲁棒性评价方式有:随机数学计算法、离散事件仿真法。Rahmani等[12]采用随机数学原理模拟不确定因素发生,从而计算方案的鲁棒性。但是其参数的数值根据经验设定,在复杂因素影响下欠缺数据的真实性。因此,本文采用离散事件仿真的方法,评价方案的鲁棒性。首先定义车间调度方案的鲁棒性如下:

其中,M(s)是一个随机变量表示不确定因素影响下实际的最大完工时间;δ(s)=| M(s)Mo(s)|表示预期最大完工时间和实际最大完工时间之间的差值;r是权重函数,其值在(0,1)之间。由于Mo(s)是确定的,M(s)和δ(s)的期望值等同于E(M(s))=E(δ(s))+Mo(s)。因此作业车间调度方案的鲁棒性可以等同为

在计算R(s)的基础上,对鲁棒性进行分析,采用R(s)和r·E(Mo(s))的接近程度反映调度方案的相对鲁棒性,计算得其偏差为

采用R(s) 与平均单机工序工时之和r∑(T/4)的偏差反映该方案实际性能与目标性能的偏差:

在eM-Plant环境中建立仿真调度模型,对算法输出方案进行分析。归纳出工件的约束关系和加工时间数据(表2),作为仿真数据的输入。

min

对仿真模型多次运行,并将结果和未考虑加工时间不确定的柔性作业车间的调度方案进行对比。其计算结果如表3所示(其中r=0.7)。

分析可知,在加工时间不确定情况下,本文提出的算法产生的方案在相对鲁棒性和实际性能上都有较好的表现,在对不确定性作出有效的规避的同时发挥了良好的调度性能。

4结语

本文针对中小批量环境下加工时间不确定的柔性作业车间调度问题,结合冗余处理方法构建鲁棒调度模型,并提出顺序搜索机制,降低搜索规模。对算法参数进行优化和修正,并进行了仿真实验。该算法的主要特性有以下两点:1普适性。算法采用冗余处理方法构建模型,对加工历史数据依赖性低,算法稍作调整,便适用于其他的车间调度问题。2快速性。算法针对两层嵌套结构,创新采用顺序搜索机制,有效减少了计算量,在乘数时间内获得不确定因素扰动下的调度方案。

综合考虑本文的工作和领域的发展,进一步的研究可以关注于以下两点:1增加算法在复杂问题下的性能分析实验和同类算法之间的对比实验;2对多种不确定因素耦合作用下的车间调度问题进行研究。

摘要：针对中小批量环境下加工时间不确定的柔性作业车间调度问题,采用冗余处理方法构建了以最大完工时间为目标的鲁棒调度模型。为降低算法的搜索规模和提高算法的求解速度,提出了顺序搜索机制,并设计两阶段遗传算法,分阶段获取冗余状态和最优结果。采用某柔性生产线的数据进行正交试验,优化了算法关键参数,并构建了柔性生产线仿真模型,对调度结果的鲁棒性和优化目标性能进行了分析。结果表明,该算法在目标性能和鲁棒性上都显著优于标准遗传算法,能有效处理加工时间不确定的柔性作业车间调度问题。

灰阶响应时间测量不确定度的评定篇3

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]:为保证生鲜切面的品质, 必须对生活饮用水进行净化水处理, 来限制其总碱度含量;只有维持一定的碱度才能降低水中碳酸根离子、碳酸氢根离子、氢氧根离子达到较好效果。本实验室采用不确定度的计算, 将生鲜切面加工用水的总碱度控制在比较精确的数据范围内, 以此来达到生鲜切面品质要求。

本文以滴定法测量日式生鲜切面食品加工用水中总碱度[2]的实例, 具体阐述对国家计量技术规范JJF1059-1999《测量不确定度评定与表示》的理解和实际评估应用[3,4]。

1 材料与方法

1.1 材料

生活饮用水;净化处理后食品加工使用水。

1.2 仪器

滴定管:25mL;移液管:50mL;锥形瓶:250mL。

1.3 试剂

盐酸滴定溶液;指示剂:甲基橙。

1.4 设备

电子分析天平;便携式快速水质检测仪;水处理器 (净水器) 。

2结果与讨论

2.1 测量步骤

样品的测定

吸取50.0mL水样于250mL锥形瓶中, 加4滴甲基橙指示剂, 用盐酸标准溶液滴定至试液由黄色突变为橙色。

2.2 建立数学模型

由计算公式得到数学模型

加工用水中总碱度:

V0为滴定水样消耗盐酸标准溶液的体积, mL;

V为水样体积, mL;

50.04为与1.00mL氢氧化钠标准溶液[c (NaOH) =1.000mol/L]相当的以克表示的总碱度 (以CaCO3计) 的质量。

3 测量不确定度各分量的来源及量化

从数学模型可见, 加工用水中总碱度测量的不确定度分量由下式中几个因素组成:

urel (1) 为样品重复性测量引入的不确定度;

urel (2) 为标准溶液配制引入的不确定度;

urel (3) 为滴定消耗HCL体积引入的不确定度;

urel (4) 为水样体积引入的不确定度。

3.1 样品重复性测量引入的不确定度评定 (urel (1) )

由上表数据统计得, n = 10 , 均值= 9.30 mg / L , 相对偏差SD=0.234mg/L

样品重复性测量相对标准不确定度为:

3.2 标准溶液配制引入的不确定度评定 (urel (2) )

3.2.1 标准溶液c (HCL) 引入的不确定度评定

HCL标准溶液【 c ( HCL ) = 0.10 0 0±0.0 0 03 mol/L】GBW (E) 080495, 证书给出的标准不确定度为0.0003mol/L。按正态分布, 其相对不确定度= 0.003。

3.2.2 标准溶液稀释的不确定度

稀释过程:取10.00mL HCL标准溶液 (0.1000mol/L) 于100mL容量瓶, 纯水定容至刻度。对10mL移液管、100mL容量瓶进行不确定度计算。

由鉴定证书给出10 mL移液管、100 mL容量瓶的最大允许误差分别为±0.02 mL、±0.10 mL, 使用三角形分布, 其校准不确定度分别为0.008mL、0.041mL。10 mL移液管、100mL容量瓶使用变动性的标准偏差分别为0.002mL, 0.02mL。由于移取标准溶液的温度和稀释时的温度一致, 故忽略温度对不确定度的影响。因此, 10mL移液管的不确定度为

其相对不确定度为0.0082/10=0.00082;100mL容量瓶的不确定度为

其相对不确定度为0.046/100=0.00046。

标准溶液配制引入的相对不确定度:

3.3 滴定消耗HCL体积引入的的不确定度 (urel (3) )

滴定体积1.45mL , 取10 mL滴定管5 mL区间的允许差为±0.025 m L, 使用三角形分布, 其标准不确定度为0 .010 mL 。实验室温度在±2℃内变动, 其体积的变化为2.1×10-4×2×1.45=6.09×10-4mL, 按均匀分布计算, 标准不确定为0.00035mL。

滴定消耗HCL体积V引入的的不确定度:

其相对不确定:

3.4 水样体积引入的不确定度 (urel (4) )

水样用50.00m L移液管量取, 证书给出, 50.00mL移液管的允许差为±0.05mL, 使用三角形分布, 其校准不确定度为其标准不确定度为0.020mL。实验室温度在±2℃内变动, 其体积的变化为2.1×10-4×2×1.45=6.09×10-4mL, 按均匀分布计算, 标准不确定为0.00035mL。

水样体积V引入的的不确定度:

其相对不确定度:urel ( 4 ) = 0.020/50.00= 4.0×10-4

滴定终点判断、指示剂误差、取样体积等变动性, 已经包括在样品重复性测量引入的不确定度评定中, 这里不作计算了。

3.5合成不确定度的计算

上表中各分量不相关, 则

X=9.3 0 mg/L, 合成标准不确定度urel (c) =0.10mg/L;

3.6 扩展不确定度的评定Urel (X)

包含因子k = 2, 置信区间约9 5 %时, 扩展不确定度为:

3.7 测量不确定度的报告

加工用水中总碱度:9.30±0.20mg/L, (P = 95%)

生活饮用水总碱度:116.67±1.14mg/L, (P=95%) (计算过程略) 。

通过净水器进行加工前用水净化水处理, 实时监测净化后水质总碱度, 将碱度控制在10 mg / L以内, 有效确保了食品的品质。

结论

由上图显示, 在相对不确定的4个分量中, 所占比重从大到小依次为重复性测量引入的不确定度、在滴定过程中消耗体积引入的不确定度、HCL标准滴定液配制引入的不确定度、取水样体积引入的不确定度, 其中重复性测量引入的不确定度分量和滴定过程中消耗HCL体积引入的不确定度分量占了主要因素, 相对而言, 取样体积的不确定分量则占了极少部分。在实际测量过程中, 占主要因素的不确定度分量的容易引起误差, 占极少部分的不确定度分量不容易产生误差。

摘要：为了对食品加工用水中总碱度测量不确定度的来源进行分析, 本文在总碱度测定过程中样品重复性测量、标准滴定溶液的稀释配制、滴定终点消耗盐酸溶液的体积、取样量等因素对水中总碱度测量不确定度的影响。通过计算得到加工日式生鲜面食品用水总碱度为9.30mg/L时, 扩展不确定度为0.20mg/L, 最终得出在总碱度的测量过程中, 样品重复性测量和滴定终点消耗盐酸溶液的体积的准确度是影响加工食品用水总碱度测量不确定度的主要因素。

关键词：不确定度,总碱度,酸碱滴定,食品加工用水

参考文献

[1]、蔡丽丽, 陆启玉, 张国印.水质对面条品质的影响.河南工业大学学报 (自然科学版) .2006, 6 (27) :51-53.

[2] 、GB/T8538—2008饮用天然矿泉水检验方法.

[3] 、CSM01010101-2006滴定法测量结果不确定度评定规范.

不确定加工时间篇5

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)为例,给出所求最好解的各条路径。