约束满足

2024-09-06

约束满足（精选3篇）

约束满足篇1

0 引言

产品的拆卸序列规划 (disassembly sequence planning, DSP) 在其数学本质上是一个非确定性多项式 (non-deterministic polynomial hard, NP-hard) 求解的问题。一般而言, 随着产品中零件数量的增加, 产品拆卸方案的求解空间会迅速变得复杂起来, 从而使得采用人工判断的方法难以对其进行有效处理。近年来, 随着人工智能的发展, 越来越多的学者应用启发式算法来解决这一问题, 如Petri网法[1,2]、蚁群算法[3,4]、遗传算法[5,6]以及粒子群算法[7]等。然而, 上述人工智能算法存在陷入局部极值点的问题, 使规划结果不一定为近优解或最优解。约束满足问题 (constraint satisfaction problems, CSP) 作为人工智能领域中一个重要分支, 不存在陷入局部极值点的缺陷, 能较快地找到所有可行解, 通过对可行解进行评价, 即可得到最优的解, 故本文将CSP引入拆卸序列规划中, 通过混合图的指导给出了一种基于CSP的产品拆卸序列规划方法。

1 拆卸序列规划与CSP

拆卸序列规划是指根据产品结构和装配关系等信息, 生成满足一定约束条件的零件拆卸序列的过程[7]。

CSP是一个三元组P={X, D, C}:给定一组有限个变量X={x1, x2, …, xn}, 通过函数变换将每个变量xi一一映射到其对应的有限值域D (xi) ={d1, d2, …, dn}, C为一个有限的约束集合, CSP的解就是在满足所有约束的条件下, 从变量的值域中给每个变量赋值, 使得所有的约束得以满足[8,9,10]。

拆卸序列规划可转化为一类CSP, 拆卸序列规划每一步拆卸的零件可以映射为CSP中的变量X, xi对应拆卸序列中每一步拆卸下来的零件, 拆卸序列规划中每步待拆卸零件可以映射为变量X对应的值域, 零件间拆卸约束关系可映射为CSP中的约束集合C。拆卸序列规划得到的可行序列对应CSP的解。图1给出了产品的拆卸序列规划和CSP的对应关系。

2 基于CSP的拆卸序列规划

2.1 基于CSP的拆卸序列建模

2.1.1 CSP的变量与值域

CSP的解即一个有效的拆卸序列可表示为X={x1, x2, …, xn}, xi为拆卸序列中第i步拆卸的零件。xi的值域di是一个动态变化的域。设A为所有待拆的零件集合, Bi为从第1步到第i步拆卸过程中已拆卸的零件集合, 则第i+1步待拆卸零件xi+1的值域di+1可用下式表示:

$d_{i + 1} = A - B_{i} = \bar{B_{i}} B_{i} \subset A$ (1)

式中, $\bar{B_{i}}$ 为Bi的补集。

2.1.2 CSP的约束

记录产品拆卸信息常用的方法之一是拆卸约束图 (disassembly constraint graph, DCG) [11]。DCG是一个混合图, 可表示为G={V, E, DE} (图2) 。

其中, G表示拆卸约束图;V为节点, 即零件;E为无向边, 表示两个零件间存在连接关系的约束;DE为有向边, 表示两个零件间存在空间干涉, 箭尾零件在空间上阻挡了箭头所指零件的拆卸, 零件的拆卸就是在图中将其对应的节点及与其相关的边删除掉。G可分解为零件间的连接约束图 (混合图中无向边与节点组成的无向图) GE={V, E}和空间干涉图 (混合图中有向边与节点组成的有向图) GDE={V, DE}。设G中节点个数为n, 则图GE和图GDE的邻接矩阵NE和NDE分别为

$Ν_{E} = [\begin{matrix} a_{1, 1}^{(E)} & a_{1, 2}^{(E)} & \dots & a_{1, n}^{(E)} \\ a_{2, 1}^{(E)} & a_{2, 2}^{(E)} & \dots & a_{2, n}^{(E)} \\ ⋮ & ⋮ & ⋮ \\ a_{n, 1}^{(E)} & a_{n, 2}^{(E)} & \dots & a_{n, n}^{(E)} \end{matrix}]$

$\begin{array}{l} Ν_{D E} = [\begin{matrix} a_{1, 1}^{(D E)} & a_{1, 2}^{(D E)} & \dots & a_{1, n}^{(D E)} \\ a_{2, 1}^{(D E)} & a_{2, 2}^{(D E)} & \dots & a_{2, n}^{(D E)} \\ ⋮ & ⋮ & ⋮ \\ a_{n, 1}^{(D E)} & a_{n, 2}^{(D E)} & \dots & a_{n, n}^{(D E)} \end{matrix}] \\ a_{i, j}^{(E)} = {\begin{cases} 0 i 和 j 之间无连接 \\ 1 i 和 j 之间有连接 \end{cases} \end{array}$

且a (E) i, j=a (E) j, i, 当i=j时, a (E) i, j=a (E) j, i=0。

$a_{i, j}^{(D E)} = {\begin{cases} 0 j 在空间上不阻挡 i 的拆卸 \\ 1 j 在空间上阻挡 i 的拆卸 \end{cases}$

且当i=j时, a (DE) i, j=a (DE) j, i=0。

拆卸是一个互相作用的过程, 拆离A、B两个零件, 既可以认为是将零件A从零件B上拆除, 也可以认为是将零件B从A零件上拆除, 故在拆卸序列规划时, 首先需要确定基准件, 认为所有零件均从基准件或基准件所在装配体中拆除, 即拆卸到最后一步产品所剩的零件。同一个装配体在不同的基准件下生成的拆卸混合图极有可能是不同的, 如图3所示。基准件的选取可参照以下原则进行:①在装配体中与其余零件连接关系最多;②体积大, 易保证在拆卸过程中装配体的稳定性;③基准件是拆卸到最后一步所剩的零件, 故其在空间上不能干涉其他零件的拆卸;④方便在拆卸过程中工具和夹具的使用。如在图3所示的装配体中, 以3作为基准件是较为合适的。

一个合理的拆卸序列应保证在操作过程中每一步的零件拆卸不受其他零件干涉, 且零件拆卸后不会影响零件拆卸后剩下的子装配体结构的稳定, 导致拆卸的不确定性, 故在基于CSP的拆卸序列规划中, 约束C可分为两类:连接约束CE和空间干涉约束CDE。

(1) 连接约束CE。

零件拆卸后如剩余子装配体中所有零件均由一定的连接关系组成一个整体, 则认为子装配体是稳定的, 即满足连接约束CE。连接约束CE主要针对图GE进行判断, 当GE去除节点及与其相关的无向边后, 剩余节点及无向边所组成的子图应该是一个连通图, 连接约束CE的逻辑表达如图4所示。

CE的数学表达如下:

if M $_{i i}^{(E)}$ 存在全为零的行

CE不满足

else

CE满足

其中, i为拆卸的零件标识;M $_{i i}^{(E)}$ 为图GE的邻接矩阵NE中元素a (E) i, i (拆卸的零件) 的余子式。若

$Ν_{E} = [\begin{matrix} a_{1, 1}^{(E)} & \dots & a_{1, i - 1}^{(E)} & a_{1, i}^{(E)} & a_{1, i + 1}^{(E)} & \dots & a_{1, n}^{(E)} \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ \\ a_{i - 1, 1}^{(E)} & \dots & a_{i - 1, i - 1}^{(E)} & a_{i - 1, i}^{(E)} & a_{i - 1, i + 1}^{(E)} & \dots & a_{i - 1, n}^{(E)} \\ a_{i, 1}^{(E)} & \dots & a_{i, i - 1}^{(E)} & a_{i, i}^{(E)} & a_{i, i + 1}^{(E)} & \dots & a_{i, n}^{(E)} \\ a_{i + 1, 1}^{(E)} & \dots & a_{i + 1, i - 1}^{(E)} & a_{i + 1, i}^{(E)} & a_{i + 1, i + 1}^{(E)} & \dots & a_{i + 1, n}^{(E)} \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ \\ a_{n, 1}^{(E)} & \dots & a_{n, i - 1}^{(E)} & a_{n, i}^{(E)} & a_{n, i + 1}^{(E)} & \dots & a_{n, n}^{(E)} \end{matrix}]$

则

$Μ_{i i}^{(E)} = [\begin{matrix} a_{1, 1}^{(E)} & \dots & a_{1, i - 1}^{(E)} & a_{1, i + 1}^{(E)} & \dots & a_{1, n}^{(E)} \\ ⋮ & ⋮ & ⋮ & ⋮ \\ a_{i - 1, 1}^{(E)} & \dots & a_{i - 1, i - 1}^{(E)} & a_{i - 1, i + 1}^{(E)} & \dots & a_{i - 1, n}^{(E)} \\ a_{i + 1, 1}^{(E)} & \dots & a_{i + 1, i - 1}^{(E)} & a_{i + 1, i + 1}^{(E)} & \dots & a_{i + 1, n}^{(E)} \\ ⋮ & ⋮ & ⋮ & ⋮ \\ a_{n, 1}^{(E)} & \dots & a_{n, i - 1}^{(E)} & a_{n, i + 1}^{(E)} & \dots & a_{n, n}^{(E)} \end{matrix}]$

(2) 空间干涉约束CDE。

零件拆卸时, 只有在空间上没有其他零件的阻拦, 才能进行零件的拆卸, 即满足空间干涉约束CDE。空间干涉约束CDE主要针对图GDE进行判断。为满足空间干涉约束CDE, GDE中指向待拆卸零件所表示的节点xi的箭头个数应等于0, 即入度ID (xi) =0。空间干涉约束CDE的逻辑表达如图5所示。

CDE的数学表达如下:

if ID (xi) =0

CDE满足

else

CDE不满足

当某一零件拆卸完成后, 它对子装配体的拆卸约束也随之消失, 因此, 基于CSP的产品拆卸序列规划中约束C是一个动态变化的过程。设xi为第i步拆卸的零件, 则第i+1步待拆零件xi+1的连接约束C $_{E}^{(i + 1)}$ 针对的图G $_{E}^{(i + 1)}$ 的邻接矩阵N $_{E}^{(i + 1)}$ 等于N (i) E中元素a (i) i, i (拆卸的零件) 的余子式M $_{i i}^{(E)}$ ;空间干涉约束C $_{D E}^{(i + 1)}$ 针对的图G $_{D E}^{(i + 1)}$ 的邻接矩阵N $_{D E}^{(i + 1)}$ 等于N $_{D E}^{(i)}$ 中元素a (DE) i, i的余子式M $_{i i}^{(D E)}$ 。

2.2 基于CSP的拆卸序列求解

在确定基准件后, 根据文献[12,13]介绍的方法, 即可通过CAD系统生成拆卸混合图及其相关邻接矩阵, 之后便可采用CSP相关算法进行求解。在众多CSP求解算法中, 回溯算法 (backtracking, BT) 为最常用的算法。该算法通过给部分变量进行复制赋值, 并在赋值过程中对部分赋值的变量进行约束检测, 提前发现不满足约束的变量集合, 显著地提高了搜索效率[14,15], 故本文采用回溯算法针对拆卸序列规划进行求解。由拆卸的顺序性可知, 当拆卸到装配体只剩两个零件A、B (B为基准件) 时, 其序列只能为A→B。因此, 为减小运算量, 在求解拆卸序列时, 首先对基准件赋值, 再使用回溯算法对拆卸的第一个零件到倒数第三个零件的序列进行求解, 拆卸序列中倒数第二个零件则在回溯算法求解后自动得到。当得到可行拆卸序列后, 设计人员即可根据具体要求对可行拆卸序列进行评价, 得到最符合要求的拆卸序列。由于评价得到的结果是从所有可行解中得到的, 容易证明, 得到的拆卸序列应是全局最优解。以拆卸时间最小为例, 则对拆卸序列的评价函数为

$\min X = \sum_{i = 1}^{n} Τ_{Ρ} (x_{i}) + \sum_{i = 1}^{n} Τ_{D} (x_{i}) + \sum_{i = 1}^{m} Τ_{C} (i) (2)$

式中, TP (xi) 为拆卸零件xi之前的准备时间, 主要包括更换拆卸工具消耗的时间以及将拆卸工具放置到拆卸位置的时间;TC (i) 为拆卸零件过程中每次对装配体旋转、移动以便进行拆卸所消耗的时间;m为拆卸过程中对装配体旋转、移动的次数;TD (xi) 为拆卸零件xi的工作时间。

基于CSP的拆卸序列求解的流程如图6所示。

基于回溯算法的产品拆卸序列求解是一个递归算法, 即

3 应用实例

以一个简化的洗碗机门体作为应用实例, 如图7所示 (为减小运算量, 部分细小零件以及螺钉等连接件已经移除) 。产品采用手工拆卸的方式, 目标为拆卸时间最短。根据基准件选取原则, 采用“4-内门板”为基准件, 生成的洗碗机门体拆卸混合图见图8。洗碗机门体零件拆卸信息如表1所示。由图8得到洗碗机门体连接约束图GE的邻接矩阵为

$Ν_{E} = [\begin{matrix} 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 1 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \end{matrix}]$

空间干涉图GDE的邻接矩阵为

$Ν_{D E} = [\begin{matrix} 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 \end{matrix}]$

1.控制面板组件 2.锁扣夹板 3.门锁扣 4.内门板 5.分配器组件 6.旋钮 7.门铰链组件 8.门保护条 9.外门板

注:零件1、9虽然拆卸方向为+X, 但由于其螺钉连接固定在-X方向, 故其拆卸应先从-X将固定的螺钉去除, 然后再从+X取走零件, 零件5的情况与零件1、9正好相反。

选择一次运算情况对算法进行说明。首先对基准件进行定义, 确定x9=4。根据本文所述算法进行第一次递归调用, 运行函数BT (1) , 令x1=1, 对C (1) E以及C (1) DE进行判断, 确定满足约束。之后进行第二次递归调用, 运行函数BT (2) , 令x2=2, 对C (2) E以及C (2) DE进行判断, 确定满足约束。如此进行至第四次递归, 运行函数BT (5) (此时x2=2, x3=3) , 令x4=5, 发现同时不满足约束C (4) E和C (4) DE, 则不再对剩余变量进行赋值, 开始回溯, 对x4重新赋值为6。发现此时满足约束, 进行第5步递归调用。最后一直运行到第7步递归调用, 得到一个解{x1, x2, x3, x4, x5, x6, x7}={1, 2, 3, 6, 7, 9, 5}。令x8为最后与基准件相连零件8, 最终得到一个可行拆卸序列X={x1, x2, x3, x4, x5, x6, x7, x8, x9}={1, 2, 3, 6, 7, 9, 5, 8, 4}。编程对问题进行求解, 即可得到洗碗机门体所有可行拆卸序列。

当确定所有可行拆卸序列后, 即可对可行拆卸序列进行评价, 得到最符合要求的拆卸序列。本例采用手工拆卸的方式对洗碗机门体进行拆卸, 拆卸过程中洗碗机门体平放在工作台上, 初始状况默认图7中+X方向向上。在拆卸过程中每次进行翻转的时间TC (i) 近似相同约为8s。由于洗碗机门体较小, 因此将拆卸工具放置到拆卸位置对拆卸影响也较小, 平均约为1s, 而更换拆卸工具的时间为4s, 故TP (xi) =1+4=5s。根据式 (2) , 对得到的所有可行解进行评价, 结果表明, 洗碗机门体所有可行拆卸序列在上述条件下拆卸耗时均近似相同, 表2给出了部分拆卸时间最小的序列。

4 结语

本文在拆卸混合图的基础上, 将拆卸序列规划转化为一类约束满足问题 (CSP) 进行求解, 给出了基于CSP的拆卸序列求解模型及相关算法, 并用实例进行了说明。相较基于蚁群算法、遗传算法以及粒子群算法等人工智能算法的拆卸序列规划而言, 基于CSP的拆卸序列规划不存在结果陷入局部极值点的缺陷。同时, 基于CSP的拆卸序列规划不对生成的序列进行评价、优选, 而是在得出所有可行序列后另行评价优选, 故当评价指标改变后, 只需对CSP的解重新进行评价优选, 而不必再次进行整体的搜索, 因而提高了效率和适应性。

约束满足篇2

不同类型产品或工件连续加工过程中,通常要考虑发生在机器上的换型或安装时间及成本,以及由此引起的机器、工装夹具、产品、工件的损失或损坏成本。在多品种小批量生产环境下,为减少因产品范围快速扩展而引起的大量换型或安装时间,企业普遍采用基于成组技术的混流生产方式,即将结构形状、工艺以及工装等相似的产品或工件组合为批量生产,由此产生的调度问题称为成组/工件组调度(group scheduling/family scheduling,GS/FS)问题[1,2]。成组调度问题一般包括以下三项任务:①将工件/零部件分配到某个加工批;②加工批内的工件排序;③加工批在机器设备上排序。

成组混流生产的本质在于对同一机器上具有相似制造特征的不同工件成组批量生产,以减少安装时间。相似工件的成批生产能够通过减少安装时间释放机器产能,但同时也将使延后加工的工件交期受到影响,因此成组调度需要平衡满足交期与安装时间减少之间的冲突关系[3]。相较于传统调度问题,成组调度问题不仅目标更多样化,而且处理的约束也更多。作为一类复杂的组合优化问题,成组调度问题的快速求解有赖于高效的调度方法。

按照机器的数量特征可以将成组调度问题分为单机、并行机与多机等类型[4,5],单机成组调度问题因大量的工业应用需求备受关注。Hitomi等[5]最早提出了运用分支定界法确定工件和工件组的排序;Ghosh[6]提出了运用后向动态规划算法实现工件的总加权完成时间最小化;Panwalkar等[7]提出了按照SPT与EDD规则实现单机成组调度问题总延迟时间最小化的PSK法;Liao等[8]提出了一种基于启发式算法的禁忌搜索方法求解存在主要与次要安装时间的成组调度问题;王秀利等[9]针对总流程时间最小化的单机成组作业优化调度问题,提出了基于优化性质的构造性启发算法;Mason[10]提出了一种使用SWPT(shortest weighted processing time)规则的遗传算法实现工件的加权完成时间最小化;聂黎等[11]针对最小化提前/拖期惩罚的单机调度问题,研究了运用基因表达式编程及其改进算法前序基因表达式编程的求解方法;Crauwels等[12]开发了模拟退火、禁忌搜索等多个邻域搜索启发式方法最小化工件的加权完成时间。

以上针对单机成组调度问题的研究在不同程度上为相关的后续研究提供了基础,但面对更为复杂的现实问题需要更为有效的建模方法和求解方法。本文针对单机成组调度问题工件组是否分批、安装时间与工件排序是否有关等复杂的约束特征,将其作为一类约束满足问题,构建了更接近于现实问题表达的单机成组调度约束模型,以最小化加权流程时间与加权拖期为目标,设计了启发式搜索与约束传播相结合的求解方法,实现了不同类型问题的快速建模和求解。

1 单机成组调度问题描述

起源于人工智能领域的约束满足技术通过分离问题的建模与求解算法,以更加接近于现实世界的方式描述问题及其复杂的约束,利用变量之间的约束关系传播与一致性检验等方法进行模型求解,在有效解决复杂问题,特别是在组合优化问题方面具有非常明显的优势。此外,约束满足方法还允许用户在不改变算法的情况下,通过增减约束动态地修改模型,为其他问题所重用,因此利用约束满足方法进行生产调度问题建模和求解得到了广泛的关注和研究。目前的约束满足计划调度问题研究主要限于传统的车间作业调度,如Beck等[13]提出了基于资源依赖度和争用度等动态问题结构信息的启发式搜索技术求解车间调度问题,Watson等[14]研究了混合约束规划与局部搜索方法求解车间调度问题。在运用约束满足的方法解决成组调度问题方面,尽管Malapert等[15]提出了研究对象为批处理时间下的成批以及排序问题,但迄今文献中尚未出现运用约束满足方法的工件可用性条件下的单机成组调度问题研究。

单机成组调度是指将多个属于不同工件组的工件加工任务根据相似性分派到制造资源的过程,如图1所示,其目的是综合考虑制造资源能力、工件成组特性、工件交期等约束,合理安排工件批和工件的生产活动以同时满足约束和优化目标。因此,单机成组调度问题是一类有限域约束满足问题或约束优化问题(COPs),且大多数都是NP难题。

单机成组调度问题假设有n个工件要在一台机器上加工,机器一次只能加工一个工件,且工件不可中断,所有工件同时到达。n个工件分别属于f个工件组,第i工件组包含ni(n1+n2+…+nf=n)个工件,Jik表示第i工件组的第k个工件,Ji={Ji1,Ji2,…,Ji k,…,Ji ni}表示第i工件组的工件集合。该问题的参数变量与值域如表1所示。

对于成组调度问题,一般假设:每一种工件组的加工都需要精确的安装时间,而且此安装时间远远大于工件的加工时间,该假设被称为成组假设。如果成组假设成立,则同一工件组内的工件在机器上连续加工,每一工件组的处理时间等于该工件组中所有工件的处理时间总和;否则,同一工件组内的工件可分割加工。通常将连续加工的一系列工件集合称为一个加工批,如果加工批中的所有工件加工完成之后通过托盘、箱子或拖车等容器运输到下一工序进行加工,则称为批可用性;否则称为工件可用性。本文的研究对象为工件可用性条件下的单机成组调度问题。

对于工件组不可分割加工的单机成组调度,通常将工件组i整体作为一个复合工件,处理时间 $p_{i} = \sum_{k = 1}^{n_{i}} p_{i k}$ ,权重 $w_{i} = \sum_{k = 1}^{n_{i}} w_{i k}$ 。调度的本质在于合理排列工件组以及工件组内工件的加工顺序,从而优化目标,如图2所示。将工件组作为一个整体连续加工时,容易造成工件组中个别工件拖期过长,因此需要将同一工件组中的工件分割成若干个加工批加工。这样得到的成组调度方案用一系列的运行r(run)来表示,一个运行r是指两类加工批的设置(setups)之间处理的工件组合,一个运行中的工件属于同一工件组,如图3所示。与工件组工件不可分割的问题相比较,这类问题相对比较复杂,需要在确定每个加工批的工件组合基础上,确定各加工批以及加工批中各工件的处理顺序,如图4所示。运行r的数量用η表示,η≥f。运行r中的工件数量用βr表示,其中r∈{1,2,…,η}。

对于单机成组调度问题,如果工件组i或运行r(下文统称为工件组)的安装时间与之前处理的工件组无关,则认为工件组的安装时间独立于工件组排序;如果安装时间依赖于之前处理的工件组,则认为工件组的安装时间依赖于工件组排序(sequence-dependent setup times,SDST)。

根据工件可用性条件下的单机成组调度问题的加工特征,可将其分为4种子问题:①工件组安装时间独立于工件组排序且不可分割加工问题;②工件组安装时间独立于工件组排序可分割加工问题;③工件组安装时间依赖工件组排序不可分割加工问题;④工件组安装时间依赖工件组排序可分割加工问题。

2 问题的约束满足模型

2.1 单机成组调度问题的决策变量

成组调度问题旨在为每一个工件组及工件安排一个合理的制造期间,保证优化目标实现。影响成组调度目标实现的决策变量主要是序变量,包括工件组排序与工件组内工件排序,O(i)表示排在第i位置的工件组序号,O(i)∈{1,2,…,f};O(i,k)表示排在工件组i中第k位置的工件序号,O(i,k)∈{1,2,…,ni}。

根据决策变量,事先给定的参数变量值将更新,如工件组JO(i)的开始加工时间为stO(i),工件JO(i,k)的开始加工时间为stO(i,k),工件组JO(i)的加工时间为pO(i),工件JO(i,k)的加工时间为pO(i,k),其他依此类推。为了用决策变量描述工件组之间的安装时间,假设用F={1,2,…,f}表示工件组集合,引入虚拟工件组0,生成F0={0,1,…,f}。对工件组排序,得到序变量集合OF={O(0),O(1),…,O(f)},则排在第i位置的工件组的安装时间为sO(i-1)O(i),如果工件组的安装时间与排序无关,则为sO(i)。对于增加的虚拟工件组0,有O(0)=0,p0=0,d0=0,w0=0。

2.2 单机成组调度问题的约束

对于以上给出的4种单机成组调度问题,运用约束满足方法建模,主要包括如下约束。

(1)工件成组特性约束。

①工件j只能属于一个工件组i,即

$\sum_{i = 1}^{f} α_{i j} = 1, j \in {1, 2, \dots, n}, i \in {1, 2, \dots, f}$ (1)

②属于工件组i的工件数量总和为ni,即

$\sum_{j = 1}^{n} α_{i j} = n_{i}, j \in {1, 2, \dots, n}, i \in {1, 2, \dots, f}$ (2)

③所有工件组的工件数量ni之和为总工件数量n,即

$\sum_{i = 1}^{f} n_{i} = n, i \in {1, 2, \dots, f}$ (3)

④所有运行r的工件数量βr之和为总工件数量n,即

$\sum_{r = 1}^{η} β_{r} = n, r \in {1, 2, \dots, η}$ (4)

⑤工件组i或运行r的权重为

$ω_{i} = \sum_{k = 1}^{n_{i}} ω_{i k}$ 或 $ω_{r} = \sum_{k = 1}^{β_{r}} ω_{r k}$ (5)

(2)工件组的处理时间约束。

①工件组不可分割加工,将工件组i整体作为一个复合工件,其处理时间为

$p_{i} = \sum_{k = 1}^{n_{i}} p_{i k}, i \in {1, 2, \dots, f}, k \in {1, 2, \dots, n_{i}}$ (6)

②工件组可分割加工,用βr表示分割之后运行r中的工件数量,则运行r的处理时间为

$p_{r} = \sum_{k = 1}^{β_{r}} p_{r k}, r \in {1, 2, \dots, η}, k \in {1, 2, \dots, β_{r}}$ (7)

(3)工件组的加工时间满足以下析取约束:

stO(i)+pO(i)+sO(i)O(i+1)≤stO(i+1) (8)

i,i+1∈{1,2,…,f}

(4)工件的加工时间约束。

①工件JO(i,ni)与工件JO(i+1,1)的加工时间满足以下析取约束:

②工件JO(i,k)与工件JO(i,k+1)满足以下条件:

(5)工件JO(i,k)的完成时间约束。

(6)工件JO(i,k)的拖期约束。

2.3 单机成组调度问题的目标

成组调度通过将相似工件成组加工以减少安装时间,可能会导致工件拖期。在精益生产方式盛行的今天,准时是企业获得市场竞争的关键要素,对于多品种小批量生产,在进行批量成组生产时,既要节约安装时间,也要保证产品交期。因此,本文以最小化加权流程时间与加权拖期为目标,即

$\min Τ = \sum_{i = 1}^{f} \sum_{k = 1}^{n_{i}} w_{Ο (i, k)} c_{Ο (i, k)} + \sum_{i = 1}^{f} \sum_{k = 1}^{n_{i}} w_{Ο (i, k)} t_{Ο (i, k)}$

3 基于约束满足的问题求解方法

针对成组调度问题的多目标优化,目前文献中一般通过为各个目标设置权重等方法将多目标优化转化为单目标优化,具有一定的主观性,且求解的复杂性高。因此,本文将最小化加权流程时间与加权拖期目标的优化分为两个阶段完成。第一阶段,以最小化加权流程时间为目标,对工件组进行排序或将工件组分割成运行,确定运行的排序;第二阶段,以确定的排序作为初始解,其对应的加权流程时间作为约束,优化工件组或运行排序,最小化加权拖期。算法主流程如图5所示,图中①～④分别对应单机成组调度问题的4种子问题。

3.1 工件组分割条件

同一工件组的工件是否分割与工件的数量、工件的处理时间、工件批的安装时间、工件组内工件的交期等诸多因素有关。对于需要调度的工件任务,一般可从以下3个方面确定工件组是否需要分割:①工件组安装时间与工件加工时间比较,若满足成组假设,则工件组不必分割;②同一工件组内工件数量上限设定阈值,若小于阈值就不需要分割;③同一工件组内工件交期差异设定阈值,如当min(di1,di2,…,dini)与max(di1,di2,…,dini)的比值小于某阈值,则需要分割。

3.2 最小化加权流程时间的变量排序启发式搜索算法

根据Webster[2]的研究结果,对于以加权流程时间为目标的单机成组调度问题,其最优调度满足:①对于工件组i中的2个不同工件Ji m与Jik,如果 $\frac{p_{i m}}{w_{i m}} \leq \frac{p_{i k}}{w_{i k}}$ ,那么工件Jim排在工件Jik之前;②所有运行r均按照SWPT规则排序,即满足 $\frac{s_{Ο (1)} + p_{Ο (1)}}{w_{Ο (1)}} \leq \frac{s_{Ο (2)} + p_{Ο (2)}}{w_{Ο (2)}} \leq \dots \leq \frac{s_{Ο (η)} + p_{Ο (η)}}{w_{Ο (η)}}$ 条件。本文以此原则为基础,考虑与工件组排序相关的安装时间影响,设计了按照最短加权有效处理时间(shortest weighted effective processing time,SWEPT)规则搜索变量、最小化加权流程时间的工件组排序算法。该算法框架适用于本文界定的4种子问题类型,这里仅仅给出了工件组可分割加工,且安装时间依赖工件组排序问题的求解算法步骤,工件组不可分割加工、安装时间不依赖工件排序问题的求解与此类似。具体如下。

(1)工作组内工件排序初始化。对于工件组Ji中的工件Ji k按照SWPT规则排序,如果此值相同,按照加权最早交期(weighted earliest due-date,WEDD)规则排序,得到工件组Ji的排序集合

Si={JO(i,1),JO(i,2),…,JO(i,n1)}

令β=Ø,η=1,进入步骤(2)。

(2)变量选择启发式方法。按照有效加权处理时间 $\frac{s_{0 i} - p_{Ο (i, 1)}}{w_{Ο (i, 1)}}$ 的非降顺序对工件组Ji排序,如果此值相同,按照工件组Ji的WEDD规则排序,工件组Ji交期的定义见后面说明。对于已经排序的工件组,按照 $\frac{s_{0 i} + p_{Ο (i, 1)}}{w_{Ο (i, 1)}} = \min {\frac{s_{0 g} + p_{Ο (g, 1)}}{w_{Ο (g, 1)}} | g = 0, 1, 2, \dots, f}$ 选择一个作业JO(i,1),将该作业从Si中删除,放入β的第1个位置上,令O(η)=i,h=i,η←η+1。根据已经确定的工件组Jh,更新工件组的加权处理时间sh i={sh i+pO(i,k)|JO(i,k)是Si中的第1个作业,i≠h}。进入步骤(3)。

(3)若S0∪S1∪S2∪ …∪Sf=Ø,则进入步骤(4),否则按下述规则执行算法:①若Sh中的工件数量大于等于1,当 $\frac{p_{Ο (h, m)}}{w_{Ο (h, m)}} \leq (\frac{s_{h i} + p_{Ο (i, k)}}{w_{Ο (i, k)}}, i \neq h),$ 将作业JO(h,m)从Sh中删除并放入β的最后位置,作业JO(h,m)是Sh中处在第1个位置的作业;否则,从Si中根据 $\frac{s_{h i} + p_{Ο (i, k)}}{w_{Ο (i, k)}} = \min {\frac{s_{h g} + p_{Ο (g, m)}}{w_{Ο (g, m)}} | J_{o (g, m)}$ 是Sg中的第1个作业,且g≠h}选择作业JO(i,k),将该作业从Si中删除并放入β的最后位置,并令O(η)=i,h=i,η←η+1。再次执行步骤(3)。②若Sh为空集,则根据 $\frac{s_{h i} + p_{Ο (i, k)}}{w_{Ο (i, k)}} = \min {\frac{s_{h g} + p_{Ο (g, m)}}{w_{Ο (g, m)}} | J_{o (g, m)}$ 是Sg中的第1个作业,且g≠h}选择作业JO(i,k),将该作业从Si中去掉并放入β的最后位置,并令O(η)=i,h=i,η←η+1。再次执行步骤(3)。

(4)运行排序,得到加权流程时间最小的初始方案。将i从1到η变化并以此计算运行的有效加权处理时间,按照 $\frac{s_{Ο (i - 1) Ο (i)} + p_{Ο (i)}}{w_{Ο (i)}} = \min {\frac{s_{Ο (g - 1) Ο (g)} + p_{Ο (g)}}{w_{Ο (g)}} | g = 0, 1, 2, \dots, η}$ 选择运行r,赋予序变量值,根据确定的工件组排序更新安装时间,得到可行排序S。将该排序作为近似最优解,计算对应的加权流程时间作为第二阶段约束。

对于成组调度,组内工件的排序运用WEDD规则是可行的,但是工件组中任意一个工件都可能产生最大拖期,因此需要对工件组的交期进行调整。假设工件组i内的工件已经按照WEDD规则排序,且工件组从stO(i)开始加工,则工件组i中k位置的工件JO(i,k)的拖期时间为

式(13)中,qO(i,k)=pi-(pO(i,1)+pO(i,2)+…+pO(i,k)),表示工件JO(i,k)完成之后的工件组剩余处理时间。如果定义工件JO(i,k)的工件组调整交期d′O(i,k)=dO(i,k)+qO(i,k),则工件组中工件的最大拖期是maxk(cO(i,k)-dO(i,k))=stO(i)+pO(i)-mink(d′O(i,k))。因此,定义工件组的交期dO(i)=mink(d′O(i,k))。一旦工件组中工件按照WEDD规则排序,此值很容易确定,且不依赖于工件组的开始处理时间。

3.3 最小化加权拖期的变量排序启发式搜索与前向约束传播混合方法

以第一阶段获得排序S为初始可行解,按照“如果对于所有工件组i,g,q,安装时间满足siq≤sig+sgq,即三角不等式,则最优解中工件组的排序依然满足交期按照非降顺序排列[2]”规则,设计了以工件组排序变量启发式搜索与前向约束传播混合的算法(与3.2节类似,这里给出的算法适用于安装时间依赖工件组排序的问题)。

(1)工件组内工件排序。以第一阶段获得的排序S为初始解,按照WEDD规则对工件组Ji中的工件Jik排序,如果WEDD相同,则按照WSPT排序,得到工件组Ji的排序集合Si={JO(i,1),JO(i,2),…,JO(i,ni)}。令β=Ø,η=1,进入步骤(2)。

(2)工件组排序变量搜索启发式。按照WEDD规则对工件组Ji排序,得到工件组排序集合Sf。从已经排序的工件组中按照 $d_{i} / w_{i} = \min {d_{k} / w_{k} | k = 0, 1, 2, \dots, η}$ 选择工件组Ji放入β,令O(η)=i,η←η+1,并将其从工件组排序集合Sf中删除。

(3)若Sf=Ø,则进入步骤(4),否则按照深度优先搜索新的工件组序变量,由于依赖排序的安装时间的成组调度问题,不同工件组排序会引起安装时间的变化,影响工件组的完成时间。在搜索过程中,后续工件组q是否能作为可行解的一部分,需要考察该工件组排序之后生成的部分解是否比之前的解更好。如果否,则将工件组q从值域中删除,缩减搜索域。具体说明如下:假设三元工件组i,q,g形成的部分调度Sp={A,i,q,g,B},交换工件组q与工件组g得到调度S′p={A,i,g,q,B},其中A与B表示未确定的部分调度排序,可以是空集。两种调度方案的示意图如图6所示。深度优先搜索域缩减规则如表2所示。显然,如果tSp′≥tSp就表示调度Sp优于调度S′p,那么在搜索过程中如果已经确定工件组i与q的排序,则不需要继续搜索工件组g,即从值域中将工件组g删除。调度Sp优于调度S′p 的优先规则见表2。在深度优先搜索过程中当部分排序以工件组(i,q)结束,通过前向约束传播考察需要考虑的工件组g,若满足表2所示的条件,则将该工件组从值域中删除,实现域缩减。对于生成的部分调度,计算加权流程时间,若大于给定的加权流程时间,则需要回溯,重新选择工件组变量,再次执行步骤(3)。

(4)按照已经排序的工件组变量生成调度方案。

5 实例验证

运用以上建模与求解方法对某企业的成组生产调度问题进行了实例验证。该企业针对多品种小批量需求,采用成组生产组织形式,某生产期间有工件加工任务14项,各项任务的处理时间、交货时间、权重以及成组信息如表3所示。

机器上的安装时间分为两种,一种是安装时间,一种是依赖于工件组排序的安装时间,具体数据如表4所示。其中第一行和第一列中工作组f1～f5分别表示安装时间的计算起点和终点。

min

4.1 工件组不可分割加工结果

对于表3所示的14项工件任务,当工件组不可分割加工时,则在排序时将工件组整体作为一个复合工件,按照前面提出的方法,计算各个复合工件的加工时间、权重和调整交期,结果如表5所示。

运用本文提出的方法进行求解,分别得到工件组安装时间与排序有关、工件组安装时间与排序无关两种情况下的结果,两种结果的比较如表6所示。

由表6可以看出,安装时间与工件组排序无关、安装时间与工件组排序有关两种情况下的最优排序方案不同,安装时间、目标值也存在较大差异。在安装时间与工件组排序有关情况下,通过合理安排工件组的先后顺序,调整了工件组f4与工件组f3的顺序,将安装时间从75min缩减为45min,从而缩减了工件组的加权流程时间。

4.2 工件组可以分割加工结果

当工件组可以分割加工时,需要通过以SWPT为准则的工件组内排序变量赋值,SWEPT为准则的工件组排序变量赋值,首先对工件组进行分割。运行算法发现,当工件组安装时间与排序无关时,工件组未进行分割,结果与工件组不可分割加工情况下相同。分析产生这种结果的原因在于工件组安装时间为固定值,且大于等于工件的加工时间,也就是符合前面提出的成组假设,在这种情况下,工件组通常是不分割加工的。

当工件组的安装时间依赖工件组排序时,对5个工件组进行分割,得到7个运行,R={r1,r2,r3,r4,r5,r6,r7}={(J11,J13,J12),(J51),(J31,J33,J32),(J21,J23),(J52),(J42,J41,J43),(J22)}。对这7个运行进行排序,得到最优的排序方案为:S={(J42,J41,J43),(J31,J33,J32),(J11,J13,J12),(J51),(J52),(J21,J23),(J22)}。对应的加权流程时间为4693min,加权拖期为1002min,目标值为5695min。可以看出,在最优排序方案中,属于同一工件组的运行r2={J51}和运行r5={J52},运行r4={J21,J23}和运行r7={J22},由于安装时间的缘故,按照先后紧接的顺序生产。

5 结语

本文针对单机成组调度问题,首先根据工件可用性条件下安装时间是否与工件排序相关、工件组能否分割加工等加工特征,对单机成组调度问题进行了类型分析;其次,考虑工件成组特性、工件组交期、处理时间等多种制约条件,借鉴约束满足的理论和方法,以工件组和工件的排序变量为决策变量,构建了约束满足模型;再次,采用两阶段优化方法,设计了以问题结构和优化特征为指导的启发式搜索与约束传播混合的求解方法;最后,运用提出的建模和求解方法对某企业的成组生产调度问题进行了实例验证。本文提出的方法允许通过添加或改变少量约束方便地改变问题模型,在不改变算法的情况下动态地修改模型,快速地解决单机成组调度问题的4种子问题。

约束满足篇3

在电力市场环境下,可用输电能力ATC(Available Transfer Capability)是指在保证系统安全可靠运行的条件下,区域间或点与点间可能增加输送的最大功率[1],是反映输电设备可用于能量交易的剩余容量的重要指标。在线ATC的应用无论对电力系统的安全性还是电力市场下市场主体的商业行为都具有重要意义。

在计算ATC时,一般会考虑线路热稳定约束、母线电压约束、电压稳定约束以及其他稳定性约束。如果违反了线路热稳定约束或者母线电压约束,系统仍然能运行一段时间,然而违反稳定性约束将直接导致系统的崩溃。因此相对于前2种约束,电压稳定约束显得更加重要。近年来,世界范围内多次发生电压失稳而导致电力系统崩溃的大事故,电压稳定性问题再次引起电力学者的关注和重视[2,3,4,5,6]。很多专家认为电压稳定性是制约输电能力的关键因素之一。

为保证ATC计算结果的有效性和可用性,本文在ATC的计算过程中考虑“N-1”准则。由于同时考虑“N-1”预想事故和电压稳定约束,ATC的计算量将大幅增加。为了缩短计算时间,必须开发相对快速的算法进行求解。文献[7]提出了一种基于直流潮流的灵敏度ATC计算方法,该方法具有较快的计算速度,但未考虑各变化因素与ATC之间的非线性关系,因此计算精度较低。文献[8]提出了一种基于连续潮流的线性迭代法计算输电网ATC的数学模型,较前一种方法提高了计算精度。最优潮流能够方便地处理多种系统约束,将ATC的计算转化为纯粹的数学规划问题,可以采用内点法[9]、人工神经网络[10]、粒子群[11]、差分进化[12]等多种优化算法求解,也是一种广泛采用的ATC计算方法。

本文以交流模型为基础,提出了“N-1”预想事故下满足静态电压稳定约束的快速ATC算法。算法在连续潮流法CPF(Continuation Power Flow)的基础上,应用灵敏度信息和曲线拟合技术寻找“N-1”预想事故下近似的“鼻点”,并进行事故排序,该方法计算速度快,有较好的实用性。

1 ATC计算中对静态电压稳定约束的考虑

在电压稳定性研究方面,CPF有其独特的优越性[13,14]。CPF是一种求解非线性代数方程的数值方法,广泛应用于计算静态电压稳定的P-U曲线中的极限功率点(即鼻点)。传统的牛顿法在求解P-U曲线时,在电压稳定极限点附近雅可比矩阵奇异,引起潮流不收敛;而CPF法可从当前潮流解出发,逐步增加指定送端母线功率,通过迭代求解,沿P-U曲线准确得到鼻点相应的发电功率,因而可以方便地用来计算静态电压稳定约束下的ATC。

一般地,在潮流计算中,当系统负荷水平及发电机输出功率确定时,常规系统潮流方程可用式(1)表示:

用U和θ分别表示系统电压幅值向量与相角向量,则式(1)可以用下述矩阵形式描述:

其中,P和Q分别为由式(1)等号左端Pi和Qi构成的节点有功和无功向量;P(x)和Q(x)分别为与式(1)等号右端对应的向量。

当系统中发电机功率或负荷发生缓慢变化时,如果用P0和Q0表示对应于系统当前状态下的节点有功和无功向量,则可将系统方程参数化为如下形式:

其中,λ为基态下的鼻点值。

CPF法不对式(3)单独求解,而是求解下述扩展方程:

其中,P(x,λ)=0为参数化方程,是一维方程式。参数方程需要满足的重要条件为:能够保证最终形成的扩展方程的雅可比矩阵方程(2)在潮流方程的鞍型分叉点非奇异。

2 曲线拟合法

2.1 原理

为了快速计算出“N-1”预想事故下满足电压稳定约束的ATC值,可以用曲线拟合法计算出每一种预想事故下的近似P-U曲线。这是因为在电力系统潮流方程中,通过鼻点的潮流解在局部为二次曲线[15,16]。

从图1可以看出,曲线拟合法只需要取P-U曲线上的2个点进行拟合,虽然需要额外计算P2点处电压相对于λ的导数d U/dλ,但是如果CPF的计算基于牛顿潮流法,这个量将很容易得到。

将式(5)改写为

将式(7)在(x0,λ0)处线性展开,得:

曲线拟合法采用下式来计算鼻点的值:

解方程(11)得到ai、bi、ci值,然后可以根据式(12)来求取拟合出的鼻点值,得到鼻点及其对应的(xi*,λi*)值:

2.2 拟合点的求取

如果2个拟合点离实际鼻点较远,拟合出来的曲线将与实际曲线有较大的差别,估计出的鼻点将不够准确。

第1个拟合点可以选择基态运行方式在“N-1”情况下的潮流解。

由于第2个拟合点及其切线同时决定了二次曲线的形状,其位置的选取对拟合结果有决定性的影响,因此它必须尽量靠近实际的鼻点。然而,如果第1个拟合点离鼻点过远,即使第2个点选择恰当,也会使结果过于乐观,如图2所示。

为了使第2个拟合点尽量靠近鼻点,本文使用了一种基于灵敏度的方法来预测鼻点的位置,从而得到第2个拟合点。对于每一种预想事故,方法都预测出近似鼻点λi,并用CPF法计算λi对应的潮流解。如果计算结果收敛,就将结果作为第2个拟合点;反之,用式(13)来得到新的λi预测值,重新计算λi对应的潮流解,直到CPF法能够收敛。

其中,0.5<α<1。

2.3 用基于灵敏度的方法预测鼻点

2.3.1 灵敏度方法的原理[17]

将电力系统潮流方程(3)(4)表示为

其中,p为发生变化的参数。

在鞍点分叉处,雅可比矩阵fx x=x*产生奇异,此时有左特征向量w(x*,λ*,p*),使:

假设(fxfλ)*非奇异,有(以下类同),即满秩,根据隐函数定理知道在鞍点附近存在光滑函数X(p)和λ(p),满足X(p)=x*,λ(p)=λ*,于是(x*,λ*,p*)也是方程(16)的解。

将式(16)对p全微分,得:

在鞍点处左乘w(x*,λ*,p*),得:

因此有

2.3.2 用基于灵敏度的方法预测第2个拟合点的位置

基于灵敏度的方法利用了潮流方程的一阶灵敏度信息,计算速度很快,并且能粗略获得“N-1”预想事故下鼻点的变化量。

a.线路i发生断线故障时,其鼻点相对于基态下鼻点的变化为

其中,Gi、Bi、B0 i分别为线路i的电导、电纳以及接地电纳,分别为λ相对于线路i参数的灵敏度值,可以用式(19)计算。

当得到dλi之后,就可以计算出线路i断线情况下λi的估计值:

其中,λi为线路i断线情况下的鼻点值。

b.发电机停运时,其鼻点相对于基态下鼻点的变化为

其中,Pg i、Qg i分别为发电机i发出的有功和无功值,分别为λ相对于发电机i相关参数的灵敏鄣Pgi鄣Qgi度值,可以用式(19)计算。

当得到dλi之后,就可以根据式(21)计算出发电机i停运情况下λi的估计值。

2.4 检验拟合点位置的合理性

由于λ的计算实质上是一个非线性问题,用一阶灵敏度进行估计有时会产生较大的误差,因此必须检验拟合点位置的合理性。如果第2点离预测出的鼻点比较近,则估计值在误差范围内是合适的。否则,把第2个潮流解看作第1个潮流解,用上述方法继续计算出新的潮流解,作为第2个拟合点,然后用曲线拟合法拟合出新的鼻点值。这一过程将不断重复,直到拟合点离鼻点足够接近为止。

当第2个拟合点λi(2)满足式(23),可以认为拟合结果满足要求:

其中,λ*为拟合出的鼻点值;ε为要求达到的精度,可以预先设定。

2.5 程序流程图

程序的流程图如图3所示。

3 算例分析

本文以IEEE 30节点测试系统为算例,其系统图如图4所示,各区域的负荷贡献因子、负荷汲取因子分别如表1和表2所示,系统节点数据、支路数据分别如表3和表4所示,功率传输方向为区域1到区域2。由于区域间交换的功率是基于区域的,不是基于节点的,因此此处引入节点功率参与因子将区域间传输的功率分解到物理节点,以便进行潮流计算。节点功率参与因子表示各节点承担功率的比例,分为2类:对于送电区域要指定送电节点群,这些节点共同承担该区域在区域间传输功率的供电量,各节点承担的比例称为发电贡献因子;对于受电区域要指定受电节点群,各节点的受电比例称为负荷汲取因子[18]。

算例计算了电压稳定约束下最严重的单一断线事故和单发电机停运事故下的ATC值。

a.电压稳定约束下最严重的单一断线事故。算例计算了依次开断所有线路时,满足电压稳定约束的ATC值。表3列出了5种最严重单一断线事故下的ATC值,以CPF法计算出的ATC值为准确值。当线路10-20开断时,系统的ATC值最小,为123.40 MW。当区域1到区域2的功率传输量小于该值时,任意一条线路开断都不会导致系统静态电压失稳。

本例中,当ε=0.1时,鼻点预测值和实际值的误差小于5%;当ε=0.2时,虽然减少了迭代次数,但是增加了计算误差。因此,在精度要求较高的情况下,可以选择较小的ε值;在时间要求较高的情况下,可以选择较大的ε值。ε的具体值应根据实际情况来灵活选择。

b.电压稳定约束下最严重的单一发电机停运事故。算例计算了依次开断所有发电机时,满足电压稳定约束的ATC值。表4列出了3种最严重单一发电机停运事故下的ATC值。当发电机22停运时,系统的ATC值最小,为228.58 MW。

综合表3和表4的结果,满足所有“N-1”故障情况下不发生静态电压失稳的ATC值为123.40 MW。

4 结论

【约束满足】推荐阅读：

工作满足06-27

社会满足08-26

满足试验要求08-21

可满足性问题07-05

满足群众文化需求07-03

满足需要与激发需要07-12

一发展生产满足消费05-17