·480· 北京科技大学学报 2002年第4期 定义3变迁(transition)是资源消耗、使用和 真.若c的后继丛为c',则c'=(c-e)ne. 产生的一种变化.用符号T表示变迁 定义8考虑集合F=RU{-o,+o},其中，R 定义4三元组N=(S,T,F)称为网(net)的充分 为实数集合.对于Ha,bEF,区间[a,b]表示变量x 必要条件是： 的取值区间x)={x∈Fa≤x≤b}.记I(F为数集F SnT=☑ (1) 上的所有区间，n个IF)区间的Cartesian乘积称 SUT+O (2) 作区间套，记作 FCSxTUTXS (3) B=1×2…ln I,∈F dom(F)Ucod(F)=SUT (4) 与设计活动相关的变量集合设为X,设计变 其中，S为网N的库所集，T为网N的变迁集，F是 量x∈X,x的取值区间为x).若x的取值区间待 网N的流关系，SUT是网N的元素集，F的定义域 定，则a=-o,b=+o.在以上定义的基础上，有 为dom(F)={x3y:(x,y)∈F},F的值域为cod(F)= 如下的冲突检测模型. 3x:(xy)EF). 定义9并行设计中的冲突检测模型为四元 1.2冲突检测模型 组∑=(B,E,F,c).设计变量x对应的库所，设计约 采用约束网络进行冲突检测过程中，设计 束关系y对应的变迁t,∈E.F二BxEUE×B,用于表 变量的取值范围在约束关系的作用下发生变 示设计变量与相关约束关系之间的联系.cm为 化，通过判断设计变量是否存在共同的取值区 初始条件集.当8，≠⑦时，有s∈c. 间，得到设计变量的一致性区间；若无法得到满 定理1上述并行设计模型中不存在冲突的 足约束关系的一致性区间，则设计约束之间存 充要条件为设计过程中托肯总数保持不变， 在着冲突关系，需要采用相应的冲突解决算法 证明为方便，首先定义num(c)表示c中的 加以消除.为了更好地利用Petri网工具分析并 托肯总数，e表示模型中不再有变迁发生时的状 行设计过程中的冲突检测问题，可以采用下列 态集合，其中c,ecB 的对应关系将Petri网的术语与并行设计中的 (1)必要性.设计过程可以视为参与设计的 名词建立对应关系 变量在约束作用下，变量取值逐步确定的过程， 表1并行设计名词的对应关系 与设计活动相关的变量集合设为X,设计变量x Table 1 Corresponding term to the concurrent design ∈X,M表示集合X中的变量数目.若并行设计工 并行设计 Petri网 程中不发生冲突，即在设计过程结束时，与该设 设计变量 库所 计活动相关的设计变量均有确定的取值，x)≠ 约束关系 变迁 ☑，则num(c)=M=num(e),必要性得证 一致性 库所非空 (2)充分性.由∑的定义知，在设计的开始， 完备性 可达 所有与设计活动有关的变量均已采用相应的库 为了建立冲突检测的Petri网模型，下面进 所加以描述，所以变迁过程中的任一状态下的 一步给出与之有关的一些定义，包括条件及事 托肯数目不会多于初始状态，从而有num(e)≤ 件、F区间等 num(c).若num(e<num(c),则3x∈X,fx儿.=☑， 定义5基本网系统的状态元素称为条件 发生冲突.充分性得证 (condition),变迁元素称为事件.条件只有有托 13一致性算法 肯(token)和无托肯的2种状态 为了加速检测算法的速度，有必要确定相 定义6由条件和事件组成的有向网表示为 关变迁的外延，从而形成局部的独立系统 三元组(B,E:,F),其中B为条件集，E为事件集. 定义10设u∈E为(B,E,F)的一个事件集合， 定义7设为网(B,E,F)的一个条件集， 则，(I)谓词Ind(的定义为：nd(w)等价于如果对 (1)c称为网(B,E,F)的一个条件丛 于寸e,e∈u,e≠e2,则有(eUe)n(eUe)=☑. (2)事件e∈E在丛c有发生权的充分必要条 若nd(w)为真，称w为独立事件集.(2)若csB为 件是esc∧enc=☑，记作ce>. (B,E,F)的条件丛，则u中事件在c有一步发生权 (3)若e在c有发生权，即c[e>,则e可以发生， 的条件是：Ind(u)Au≤cAu∩c=☑，u在c有一步 其结果是e中的条件不再成真，e中的条件则成 发生权的事实记为c[>.一 北 京 科 技 大 学 学 报 年 第 期 定 义 变迁 是资源 消耗 、 使用 和 产生 的一 种变化 用 符号 丁表示 变迁 定 义 三元组 ， 月称为 网 的充分 必 要 条件是 羊 任 旧 刃 其 中 ， 为 网 的库所集 声为网 的变迁集 ，尸是 网 的流 关系 ， 是 网 的元素集 ， 的定义域 为 旧 〕 少 ， 的值域 为 旧 侧 日 加任 冲突检测模型 采用 约束网络进行 冲突检测 过程 中 ， 设计 变 量 的取值 范 围在 约 束关 系 的作 用 下 发 生 变 化 ， 通 过 判断设计变量是否存在共 同 的取值 区 间 ， 得到设计变量 的一致性 区 间 若无法得到满 足约束关系 的一致性 区 间 ， 则设计约束之 间存 在着 冲突关系 ， 需 要采用 相应 的冲突解决算法 加 以消除 为 了更好地利用 网工具分析并 行设计过程 中的冲突检测 问题 ， 可 以采用 下列 的对应关系将 网 的术语与并行设计 中的 名词 建立对应关系 表 并行设计名词 的对应关 系 卜 并行设计 网 设计变量 库所 约束关系 变迁 一致性 库所非空 完备性 可达 为 了建立 冲突检测 的 网模型 ， 下 面进 一 步给 出与之有关 的一 些定义 ， 包括条件及事 件 、 区 间等 定 义 基本 网系 统 的状态元素称 为条件 ， 变迁元素称为事件 条件 只 有有托 肯 和无托肯的 种状态 定 义 由条件和事件组成 的有 向网表示为 三元组 万月 ， 其 中 为条件集 ， 为事件集 定 义 设为 网 ，凡月 的一个条件集 ， 称 为 网 ，月 的一个条件丛 事件 任 在丛 有发生权 的充分必要条 件是 二 。 八已 ， 记作 若 在 有发生 权 ， 即 ， 则 可 以发生 ， 其结果 是 中的条件不再成真 ， ‘ 中的条件则成 真 若。 的后 继丛为。 ’ ， 则。 ‘ 一 定义 考虑集合 一 二 ， 二 ， 其中 ， 为实数集合 对于 ， 尸 ， 区 间【， 表示 变量 的取值区 间外 任川 ‘ ‘ 记双月为数集 上 的所有 区 间 ， 个双月 区 间的 乘积称 作 区 间套 ， 记作 二 五 几…人 五任双月 与设计活动相关的变量集合设为 ， 设计变 量 ， 的取值 区 间为阶 若 的取值 区 间待 定 ， 则 一 ， ， 二 在 以上定义 的基础 上 ， 有 如下 的 冲突检测 模型 定 义 并行设计中的冲突检测模型 为 四元 组 艺 万， 设计变量 对应 的库所 ， 设计约 束关系 对应 的变迁振 期 ， 用 于表 示 设计变量 与相 关约 束关系之 间 的联 系 ， 为 初 始条件集 当 羊 。 时 ， 有 定理 上述并行设计模型 中不存在冲突的 充要条件为设计过程 中托肯总数保持不 变 证 明 为方便 ， 首先定义 表示 中的 托肯总数 ， 表示模型 中不再有变迁发生 时的状 态集合 ， 其 中，“ 必要性 设计过程可 以 视为参与设计的 变量在约束作用下 ， 变量取值逐步确定 的过程 ， 与设计活动相关 的变量集合设为 ， 设计变量 任万 ， 因表示集合尤中的变量数 目 若并行设计工 程 中不发生 冲突 ， 即在设计过程结束时 ， 与该设 计活动相关的设计变量均有确定的取值 ， 外 续 ， 则 二 因一 ， 必要性得证 充分性 由艺的定 义知 ， 在设计的开 始 ， 所有与设计活动有关的变量均 已采用相应的库 所加 以描述 ， 所 以变迁过程 中的任一状态下 的 托肯数 目不会多于初始状态 ， 从而 有 ‘ 若 ， 则 日 任 ， 阶 。 二 ， 发生 冲突 充分性得证 一致性算法 为 了加速检测算法 的速度 ， 有必要 确定相 关变迁 的外 延 ， 从而形成局 部 的独 立 系统 定 义 设“ 三 为 万 月 的一个事件集合 ， 则 ， 谓词 的定义为 等价于如果对 于 ， 任 ， 声 ， 则 有 ， 负〕 若 为真 ， 称 为独立 事件集 若 。 二 为 万 月 的条件丛 ， 则 中事件在 有 一步发生权 的条 件是 二 二 ， 在 有 一 步 发生权 的事 实记为