第２３卷第１０期 ２Ｏ１１年１Ｏ月 计算机辅助设计与图形学学报 Ｃｏｍｐｕｔｅｒ—Ａｉｄｅｄ Ｄｅｓｉｇｎ＆Ｃｏｍｐｕｔｅｒ Ｇｒａｐｈｉｃｓ ＶｏＩ．２３ Ｎｏ．１０ Ｏｃｔ．２０ｌ１ 基于ＴＣＰＮ的协同设计过程资源约束可调度性分析 郭银章，曾建潮 （太原科技大学复杂系统与计算智能实验室 太原（ｇｕｏｙｉｎｚｈａｎｇ＠２６３．ｎｅｔ） ０３００２４） 摘 要：设计资源的有限性和设计活动的并发性会导致产品协同设计过程中的资源冲突．针对具有时间属性的产品 协同设计过程资源约束的可调度性问题，采用时间约束Ｐｅｔｒｉ网理论提出一种产品协同设计过程资源约束网模型， 定义了具有单一资源库所输入和多个资源库所输入的设计活动变迁的可调度性概念及其判定规则．把协同设计的 资源约束可调度性划分为弱可调度和强可调度２类，通过引人变迁序列的ｔｏｋｅｎ到达资源库所时间上下界的概念， 给 了产品协同设计过程资源约束的可调度性规则及算法．最后通过一个链式输送机传动系统的协同设计资源约 束模型，验证了文中方法的有效性． 关键词：时间约束Ｐｅｔｒｉ网；协同设计；设计资源约束；可调度性规则；可调度性算法 中图法分类号：ＴＰ３９１ Ｓｃｈｅｄｕｌａｂｉｌｉｔｙ Ａｎａｌｙｓｉｓ ｏｆ Ｒｅｓｏｕｒｃｅ Ｃｏｎｓｔｒａｉｎｔｓ ｆｏｒ Ｃｏｌｌａｂｏｒａｔｉｖｅ Ｐｒｏｄｕｃｔ Ｄｅｓｉｇｎ Ｐｒｏｃｅｓｓ Ｂａｓｅｄ ｏｎ Ｔｉｍｅ－Ｃｏｎｓｔｒａｉｎｅｄ Ｐｅｔｒｉ Ｎｅｔｓ Ｇｕｏ Ｙｉｎｚｈａｎｇ ａｎｄ Ｚｅｎｇ Ｊ ｉａｎｃｈａｏ （（７ｏｍｐｌｅ．ｚ Ｓｙｓｔｅｍ ａｎｄ Ｃ０ ｐ“ｆｎｆ ｆＪ “￡Ｉｎｔｅｌｌｉｇｅｎｃｅ Ｌａｂｏｒａｔｏｒｙ，Ｔａｉｙｕａｎ Ｕｎｉｖｅｒｓｉｔｙ ｏＪ Ｓｃｉｅｎｃｅ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ，Ｔａｉｙｕａｎ ０３００２４） Ａｂｓｔｒａｃｔ：Ｔｈｅ ｌｉｍｉｔａｔｉｏｎ ｏｆ ｄｅｓｉｇｎ ｒｅｓｏｕｒｃｅｓ ａｎｄ ｔｈｅ ｐａｒａｌｌｅｌｉｓｍ ｏｆ ｄｅｓｉｇｎ ａｃｔｉｖｉｔｉｅｓ ｌｅａｄ ｔｏ ｒｅｓｏｕｒｃｅ ｃｏｎｆｌｉｃｔｓ ｉｎ ｃｏｌｌａｂｏｒａｔｉｖｅ ｐｒｏｄｕｃｔ ｄｅｓｉｇｎ ｐｒｏｃｅｓｓ．Ｉｎ ｏｒｄｅｒ ｔｏ ｓｏｌｖｅ ｔｈｉｓ ｐｒｏｂｌｅｍ，ａ ｒｅｓｏｕｒｃｅ ｃｏｎｓｔｒａｉｎｔ ｎｅｔ ｍｏｄｅｌ ｂａｓｅｄ ｏｎ ｔｉｍｅ—ｃｏｎｓｔｒａｉｎｅｄ Ｐｅｔｒｉ ｎｅｔｓ ｆｏｒ ｃｏｌｌａｂｏｒａｔｉｖｅ ｄｅｓｉｇｎ ｐｒｏｃｅｓｓ ｉｓ ｐｒｏｐｏｓｅｄ ｉｎ ｔｈｉｓ ｐａｐｅｒ．Ｆｉｒｓｔｌｙ，ｄｅｆｉｎｉｔｉｏｎｓ ｏｆ ｓｃｈｅｄｕｌａｂｉｌｉｔｙ ｆｏｒ ｄｅｓｉｇｎ ａｃｔｉｖｉｔｙ ｔｒａｎｓｉｔｉｏｎ ｗｉｔｈ ｂｏｔｈ ｓｉｎｇｌｅ ｉｎｐｕｔ ａｎｄ ｍｕｌｔｉ—ｉｎｐｕｔｓ，ａｎｄ ｊ ｕｄｇｍｅｎｔ ｒｕｌｅｓ ｆｏｒ ｔｈｅ ｓｃｈｅｄｕｌａｂｉｌｉｔｙ ａｒｅ ｄｅｎｏｔｅｄ．Ｔｈｅｎ ｔｈｅ ｓｃｈｅｄｕｌａｂｉｌｉｔｙ ｏｆ ｒｅｓｏｕｒｃｅ ｃｏｎｓｔｒａｉｎｔｓ ｆｏｒ ｃｏｌｌａｂｏｒａｔｉｖｅ ｄｅｓｉｇｎ ｉｓ ｄｉｖｉｄｅｄ ｉｎｔｏ ｗｅａｋ ｓｃｈｅｄｕｌｉｎｇ ａｎｄ ｓｔｒｏｎｇ ｓｃｈｅｄｕｌｉｎｇ．Ｂｙ ｉｎｔｒｏｄｕｃｉｎｇ ｔｈｅ ｃｏｎｃｅｐｔｓ ｏｆ ｔｈｅ ｕｐｐｅｒ ａｎｄ ｌｏｗｅｒ ｔｉｍｅ ｂｏｒｄｅｒ ｆｏｒ ｔｏｋｅｎ ｏｆ ｔｒａｎｓｉｔｉｏｎ ｓｅｑｕｅｎｃｅ ｔｏ ｒｅａｃｈ ｒｅｓｏｕｒｃｅ ｐｌａｃｅ，ｔｈｅ ｒｕｌｅｓ ａｎｄ ａｌｇｏｒｉｔｈｍ ｏｆ ｒｅｓｏｕｒｃｅ ｃｏｎｓｔｒａｉｎｔ ｓｃｈｅｄｕｌａｂｉｌｉｔｙ ｆｏｒ ｃｏｌｌａｂｏｒａｔｉｖｅ ｄｅｓｉｇｎ ｐｒｏｃｅｓｓ ａｒｅ ｐｒｏｐｏｓｅｄ． Ｆｉｎａｌｌｙ ａ ｃｏｌｌａｂｏｒａｔｉｖｅ ｄｅｓｉｇｎ ｒｅｓｏｕｒｃｅ ｃｏｎｓｔｒａｉｎｔ ｍｏｄｅｌ ｆｏｒ ａ ｃｈａｉｎ— ｔｒａｎｓｐｏｒｔａｔｉｏｎ ｄｒｉｖｉｎｇ ｓｙｓｔｅｍ ｉｓ ｔｅｓｔｅｄ ｔｏ ｖａｌｉｄａｔｅ ｔｈｅ ｆｅａｓｉｂｉｌｉｔｙ ｏｆ ｔｈｅ ａｐｐｒｏａｃｈ． Ｋｅｙ ｗｏｒｄｓ：ｔｉｍｅ ｃｏｎｓｔｒａｉｎｅｄ Ｐｅｔｒｉ ｎｅｔｓ；ｃｏｌｌａｂｏｒａｔｉｖｅ ｄｅｓｉｇｎ；ｄｅｓｉｇｎ ｒｅｓｏｕｒｃｅ ｃｏｎｓｔｒａｉｎｔｓ；ｓｃｈｅｄｕｌｉｎｇ ｒｕｌｅｓ；ｓｃｈｅｄｕｌｉｎｇ ａｌｇｏｒｉｔｈｍ 产品协同设计过程就是多设计主体在分布网络 协同设计过程中，由于设计资源的有限性和设计活 环境下，以特定产品设计资源和约束为背景，针对产 品设计目标进行设计问题协同求解的过程Ⅲ．产品 动的并发性，在执行设计任务的过程中可能出现多 个设计单元同时竞争某类共享资源的情况，并且因 收稿日期：２０１０ １１ ２５；修回日期：２０１卜０６ ２７．郭银章（１９６８），男，博士研究生，副教授，ＣＣＦ高级会员，主要研究方向为网络化产品协 同设计、分布式对象网络计算；曾建潮（１９６３），男，博士，教授，博士生导师，主要研究方向为复杂系统建模与仿真、智能计算、产品协同设计与 优化． 第１０期 郭银章，等：基于ＴＣＰＮ的协同设计过程资源约束可调度性分析 资源需求总量超出资源最大容量而发生资源冲突 ｊ． 协同设计过程资源约束的可调度性分析就是针对资 源冲突与控制问题进行研究．在协同设计过程中，设 计活动需要对设计资源进行申请、占有和释放控制， 其资源约束具有明显的时间属性，所以产品协同设 计过程中的资源约束问题，其本质就是一个设计活 动资源请求时间、资源服务时间的约束问题．研究基 于资源约束的协同设计过程模型及其可调度性成为 实现产品协同设计过程管理与控制的主要问题之一． 目前，关于资源约束的优化调度问题在生产计 划与车间作业调度、网络控制系统、项目计戈Ｕ管理和 工作流管理等领域得到广泛的研究，其中对于生产 计划与车间作业调度和项目计划管理领域的资源约 束可调性问题都取得了较多的成果．这些领域的资 源约束与网络化产品协同设计资源约束的分布性特 点有所不同，网络化产品协同设计全过程建模与控 制，是在分布式网络环境下设计资源、制造资源、智 力资源和市场资源等约束条件下的问题求解过程， 具有多主体并发执行和设计过程的动态不确定性的 特点．与其相近的问题领域是工作流管理和网络控 制系统的资源约束调度的研究．在工作流管理资源 约束可调度性方面，主要是针对工作流的时间性能 进行分析．杜彦华等＿＿３ 提出一种扩展的模糊时间工 作流网模型，通过对模型的性能等价约简实现不确 定时间下的资源调度；刘胜等 ］针对资源约束条件 下的工作流时间分析问题，通过实例在工作流模型 中的停留时间分布函数求得对业务处理过程的满意 度；潘炎等 提出一种模糊时态下的工作流网建模 与分析方法；杜栓柱等 建立了一个基于ＴＷＦ—ｎｅｔ 的扩展时间工作流网模型，并在实际应用中进行了 系统的时间性能分析．带宽资源的约束、优化与调度 是网络化控制系统的资源约束调度研究的核心．程 利新等 提出一种动态选择时钟周期的资源约束调 度算法，将资源约束的影响引入时钟周期的选择，以 保证资源约束条件下的数据通道延时最小；李祖欣 等＿８ ］应用通信序列的概念和混合逻辑动态的构架 提出一种集成控制和调度的资源约束系统模型，采 用线性矩阵不等式来描述离散周期系统的周期通信 序列和Ｈｏｏ控制的协同优化问题；谢林柏等［１。。研究 了网络化控制系统中信息的调度和稳定性问题； Ｒｅｈｂｉｎｄｅｒ等口 和Ｇｏｏｄｗｉｎ等口 均研究了关于网 络化控制系统的资源约束优化与调度问题．目前，针 对产品协同设计过程中资源约束可调度性研究的相 关报道较少，仅有文献［２，１３］从协同任务规划的角 度探讨了资源约束的可调度性问题． 在产品协同设计过程中，对于具有时间属性的 设计资源约束不仅需要考虑设计活动本身拥有资源 的时间约束，还要考虑设计活动资源提供者对资源 保持和获取的时间约束．而时间约束Ｐｅｔｒｉ网（ｔｉｍｅ ｃｏｎｓｔｒａｉｎｔ Ｐｅｔｒｉ ｎｅｔｓ，ＴＣＰＮ）是一种具有丰富的时 间语义，可对具有并发、冲突、动态特性的活动过程 进行建模的扩展时间Ｐｅｔｒｉ网络口 ，鉴于事件发生 的条件在一定状态下与时间约束有关，ＴＣＰＮ在其 库所和变迁上均有时间约束信息，而且ＴＣＰＮ具有 较完整的实时系统的可调度性分析方法．所以，本文 针对具有时间约束特性的产品协同设计过程的资源 约束可调度性问题进行研究，基于已有的ＴＣＰＮ理 论，提出了产品协同设计过程资源约束的ＴＣＰＮ模 型．通过对具有资源约束的协同设计ＴＣＰＮ的４种 基本结构分析，将其设计活动变迁划分为具有单一 资源库所输入变迁和具有多个资源库所输入变迁２ 类，并给出其强可调度和弱可调度的定义和判定规 则．通过计算２类不同变迁的最早／最晚触发时间、 与资源拥有的保持时间比较来判断资源约束的可调 度性．同时对适合于协同设计全过程资源约束的可 调度性规则、可调度性算法以及对不可调度资源约 束的时间修正算法进行了研究．最后通过实例分析 说明了本文方法的有效性． １基于ＴＣＰＮ的资源约束协同设计过程模型 产品的协同设计过程就是基于现有的设计理论 和方法对设计问题进行求解的过程，是指在不确定 性状态下设计人员所进行的一种实现自己或客观主 体目标的设计活动和决策过程．协同设计的过程模 型主要描述产品设计活动中设计任务执行的进程状 态，是对产品设计目标的实现过程活动的建模与控 制管理．产品协同设计过程模型如图１所示． 产品协同设计的过程模型可用一个四元组描述 为ＣＳＣＤ－ＰＭ一（Ｐ，Ｔ，Ａ，Ｃ）．其中，Ｐ为协同设计 项目集，由其分解的许多子项目构成Ｐ一｛Ｐ ， Ｐｚ，…，Ｐ ｝，Ｐ 为项目Ｐ的子项目，它描述了项目 功能目标、目标经济指标、目标时间、分解的任务集 以及其拥有的管理资源集和其他子项目之间的关 系；Ｔ为协同设计任务集，可用一个六元组表示为 Ｔ一（ＴＤ，ＴＲ，了、Ａ，丁ＸＴ。 ，丁ＸＴ０ ，ＴＸＴ ），它描述 了当前设计任务完成期限、执行角色集、设计活动 计算机辅助设计与图形学学报 第２３卷 集、输入／输出设计文档以及与该任务设计阶段同类 产品的设计参考文档；Ａ为协同设计活动集，可用一 个五元组表示为Ａ一（ＡＵ，ＡＴ，ＡＯ，ＡＳ，ＡＣ），它描 型、设计活动的操作集、设计活动的状态集以及设计 活动的行为约束集；Ｃ为设计活动约束集，可定义为 一个四元组Ｃ一（Ｃ ，Ｃ ，Ｃ ，Ｃ ），它描述了协同设计 述了协同设计过程的抽象活动单元、设计活动的类 过程的时间约束、知识约束、数据约束和资源约束． 图１ 产品协同设计过程模型 １．１ 基于ＴＣＰＮ的资源约束模型定义 果输出，设计任务问存在着有限资源的约束调度问 产品协同设计活动基于产品的设计目标，在设 计资源的约束下，采用设计者拥有的设计知识与理 论进行的一种创新活动．产品协同设计过程是指在 当前设计规则与创新知识的作用下，基于已有的设 计资源（信息资源、软件资源、硬件资源、设计资源 等）约束，经过变换或操作转化为当前设计阶段的结 题．完成设计任务的设计活动需要对设计资源进行 申请、占有和释放控制．面向资源约束的设计活动具 有资源共享、并发和重用３种资源约束依赖关 系ｌｌ ．一个泛化的具有资源约束的协同设计过程 Ｐｅｔｒｉ网如图２所示． 请求资源 占有资源 开始任务 完成任务 释放资源 图２ 一个泛化的资源约束协同设计过程Ｐｅｔｒｉ网模型 产品协同设计过程的资源约束，本质上就是一 个任务的设计活动对设计资源的请求、占有和释放 时问的限制和调度问题，而ＴＣＰＮ是一种具有丰富 的时间语义，可对具有并发、冲突、动态特性的活动 过程进行建模的扩展时间Ｐｅｔｒｉ网络ｌ３］．本文基于 源库所集合（这里不考虑任务库所）；ＡＴ＝＝＝｛ａｔ ， ｎ ，…，ａｔ ｝表示协同设计过程的设计活动变迁；Ｆ： ＲＰ×ＡＴＵＡＴ×ＲＰ表示协同设计资源库所与设计 活动变迁之间的有限弧集合；Ｍ为描述协同设计过 程资源状态的”维向量集合，其中Ｍ（ｒｐ）表示资源 库所ｒ声中的ｔｏｋｅｎ数，Ｍ。表示系统的初始状态标 识；Ｄ为协同设计变迁执行时间延迟ｔ （。￡）的集合， ｔ （ａｔ ）表示第ｉ个设计变迁的执行延迟时间；ＴＣ为 设计资源库所和设计活动变迁的时间约束区间 ＥＴＣ ，ＴＣ ］，时间约束区间可分为２类：［Ｔ℃ （ｒ ）， ＴＣ…（ｒｐ）］表示资源库所ｒ户的局部时间约束， ＴＣＰＮ提出一种具有资源约束的协同设计过程模型 （ｒｅｓｏｕｒｃｅ ｃｏｎｓｔｒａｉｎｔ ｃｏｌｌａｂｏｒａｔｉｖｅ ｄｅｓｉｇｎ ＴＣＰＮ， ＲＣＣＤ—ＴＣＰＮ）．其形式化定义如下： 定义１．基于ＴＣＰＮ的资源约束协同设计过程 模型可用一个六元组表示为 ＲＣＣＤ—ＴＣ尸Ｎ一（ＲＰ，ＡＴ，Ｆ，ＴＣ，Ｄ，Ｍ）． 其中，ＲＰ一｛ｒ ，ｒ ，…，ｒ ｝是协同设计过程的资 ｒＴｃ…（＆￡），ＴＣ…（ａｔ）］表示设计活动变迁ａｔ的局 第１Ｏ期 郭银章，等：基于ＴＣＰＮ的协同设计过程资源约束可调度性分析 部时间约束． 库所ｒ 获得资源的最长保留时间．设计活动变迁ａｔ 协同设计的资源约束是各类设计约束管理的主 要问题之一．ＲＣＣＤ—ＴＣＰＮ模型在对协同设计的设 的最早／最迟使能时间用ＡＴ （ａｔ）／ＡＴ。 （口￡）表示． ２）设计活动变迁的最早／最迟触发时间 计任务、设计活动及其关系描述的基础上，将信息资 源约束、软硬件资源约束和设计资源约束抽取为协 同设计过程中对各类资源的时间占有问题，用占有 设计资源的某一协同设计活动变迁的执行时间、最 设计活动变迁ａｔ的最早／最迟触发时间表示ａｔ 使能后，自身确定的开始／结束触发的最大／最小经 过的时间区间，可由［ＴＣ （ａ ），ＴＣ…（口￡）］／ （ａｔ） 表示．若变迁在Ｔ。时刻使能，则它可以在［Ｔ０＋ ＴＣ…（ｎ￡），Ｔｏ＋ＴＣ…（口 ）］区间内触发，ｔｄ（口￡）表示 ａｔ的执行时间．变迁的触发由变迁时间和变迁输入 库所集上的时间共同约束．设计活动变迁ａｔ的最 早／最迟触发时间用ＡＴ （ａｔ）／ＡＴ （口 ）表示． ３）设计活动变迁的执行开始／结束时间 设计活动变迁ａｔ的执行开始／结束时问是指 ａｔ被触发后，完成设计任务的开始时间和结束时 间，用ＡＴＥＢ（ａｔ）／ＡＴＩ ｏ（ｎ ）表示，其中ＡＴＩＪ（）（ａｔ）一 ＡＴ （口￡）一ｔ （ｎ￡）．设计活动变迁ａｔ的最早／最迟使 能时间、触发时间和开始／结束时间之间的关系如 图３所示． Ａ７＇Ｌ０（ ）Ａ Ｆ（ Ａ Ｅ（ 早／最迟使能时间、最早／最迟触发时间和执行开始／ 结束时间来表达资源约束的问题，并以此在协同环 境下进行资源约束的可调度性分析． １．２ 时间约束参数的语义描述 １）设计活动变迁的最早／最迟使能时间 设计活动变迁ａｔ的最早／最迟使能时间由其输 入资源库所集中的［ＴＣ…（ｒ ），ＴＣ…（ｒ户）］决定．若 在Ｔ。时刻库所ｒ 获得一个资源ｔｏｋｅｎ，则变迁ａｔ 被激活的最早使能时间为Ｔ。＋ＴＣ…（ｒｐ），表示，．声 获得其设计变迁所需资源的最早时间．变迁ａｔ的最 迟使能时间为丁０＋ＴＣ…（ｒ ），它表示ａｔ触发前资源 Ａ Ｅ（ ＡＴＥＦ（￣ Ａ Ｂ（ ） ；ＴＣ ｉ （ ）ｉ Ｉ． ———．１ ＴＣｍａｘ（， ） ＴＣｍａｘ（ ） ｔｄ（ ） 图３ 设计活动变迁时间约束之间的关系 图３中的时间关系可表示为 ［ＡＴＥＢ（ａｔ ），ＡＴＬｏ（ａｔ ）］ ［ＡＴＥＦ（ａｔ ），ＡＴＬＦ（ａｔ ）］ ＥＡＴＥＥ（ ），ＡＴＬＥ（ａｔ ）］． 图４所不． 分析顺序结构、并发结构和冲突结构的情况可 知，对于顺序结构变迁只有一个输入库所；并发结构 由于只有一个输入库所和２个以上输出库所，所以 也可以将其分为２个以上的顺序结构；冲突结构可 以根据系统给定的条件属性进行分解，形成多个顺 序结构．所以顺序结构、并发结构和冲突结构的变迁 均属于只有一个输入库所的设计变迁．同步变迁具 有２个或２个以上的输入库所． ２ 基于ＴＣＰＮ协同设计过程资源约束模型 可调度性规则 ２．１ 设计活动变迁的可调度性定义 具有资源约束的协同设计过程ＴＣＰＮ模型一 般由顺序、冲突、同步和并发４种基本结构组成，如 Ｐ２ 死Ｐ３ Ｐ３ 顺序结构 同步结构 冲突结构 并发结构 图４ ＴＣＰＮ中常见的４种基本结构 计算机辅助设计与图形学学报 第２３卷 为了进行协同设计的资源约束可调度性分析， 本文将设计活动变迁分为２类：只有唯一一个输入 库所的变迁称为非同步变迁，具有２个或２个以上 输入库所的变迁称为同步变迁．非同步变迁采用弱 可调度规则判定其可调度性，同步变迁采用强可调 度规则判定其可调度性． 定义２．设计活动非同步变迁弱可调度．如果一 个设计活动变迁ａｔ 为非同步变迁，且不考虑ｔｏｋｅｎ 到达输入库所时间，那么设计活动变迁ａｔ 是弱可 调度，当且仅当ＡＴＩ Ｆ（ａｔ ）一ＡＴ （ａｔ ）≥ｔ （ａｔ ）成 立，其中， ＡＴＥＦ（ａｔ，）一ＡＴＥＥ（ａｔ ）＋ＴＣ…（ａｔ ）一 ｍａｘ｛７１２７…（ｒｐ ））＋ＴＣ…（ａｔ ） （１） ＡＴｌ＿Ｊ．（ａｔ ）一ＡＴｌ Ｅ（ａｔ ）一ｒａｉｎ（ｍｉｎｉＴＣ…（， ））， ｍａｘ｛ＴＣ…（ ））＋ＴＣ （ａｔ ）｝ （２） 定义３．设计活动同步变迁强可调度．如果一个 设计活动变迁ａｔ 为同步变迁，且考虑ｔｏｋｅｎ到达输 入库所ｒ 的时间Ｔｏｋｅｎ （ｒｐ ），那么设计活动变迁 ａｔ 是强可调度，当且仅当Ａ丁 Ｆ（ａｔ ）一ＡＴＥＦ（ａｔ ）≥ ｔ （ａｔ ）成立，其中， ＡＴＥＦ（ａｔ ）一ＡＴＥＥ（ａｔ ）＋ＴＣ…（ａｔ ）一 ｍａｘ｛ｍｉｎｉＴｏｋｅｎＡ（ｒｐ ）｝＋ＴＣ…（ｒｐ ）｝＋ＴＣ 。（ａｔ ） （３） Ａ７、Ｉ Ｆ（ａｔ ）一ＡＴＩ Ｅ（ａｔ ）一ｒａｉｎ｛ｒａｉｎ｛ｍａｘ｛ＴｏｋｅｎＡ（ｒｐ，）｝＋ ＴＣ…（ｒｐ ）），ｍａｘ｛ｍａｘ｛Ｔｏｋｅｎａ（ｒｐ ）｝＋ ＴＣ… （ ））＋ＴＣ…（ａｔ ）｝ （４） 定义４．Ｔｏｋｅｎ到达输入库所ｒｐ 的时间上下 界．对于Ｒ一｛ＭｏａｔｌＭｌ ａｔ２Ｍ２…ａｔ Ｍ …ａｔ Ｍ ｝状态 转换序列中，Ｈ女（Ｍ０一Ｍ ）一｛ａｔｌ ｒｐｌ，ａｔ２ｒｐ ２，…， ａｔ ｒｐ 一，ａｔ ｒｐ ｝表示从资源初始状态Ｍ。到ＭＪ 的第Ｋ条路径上的除第一个变迁之外的所有资源 库所和设计活动变迁的序列．那么 ｍｉｎｉＴｏｋｅｎ＾（ ））一ＡＴｉ＿（】（ａｔ１）＋ ｍ ｘ｛∑ＴＣ…（ａｔ ，ｋ ）＋∑￡ （ ÷ ）＋∑ＴＣ…（ ： ）｝ （５） ｍａｘ｛ＴｏｋｅｎＡ（ ）｝一ＡＴ１．（】（ａｔ１）＋ ｉｎ｛∑ＴＣ…（ ），∑ＴＣ…（ ：。）＋∑ＴＣ…（“￡ ）｝ （６） 其中ｎ ，ｒ ∈Ｈ （Ｍｏ—Ｍ ），资源库所ｒ户 是设计 活动变迁ｎ ： 的直接输入库所，Ｓ１一｛１，２，…，ｉ一１｝ 且 ≤ ，Ｓ２一｛１，２，…，ｉ一１｝且 ≤ ． ２．２设计活动变迁的可调度性规则 规则１．在基于ＴＣＰＮ的协同设计过程资源约 束网中，从资源初始状态Ｍｏ到达资源结束状态Ｍ 存在路径Ｒ一｛Ｍｏａｔ１ Ｍｌａｔ２Ｍ ・ａｔ Ｍ …ａｔ Ｍ ｝，如 果该路径所包含的变迁序列ＡＴ一｛ａｔ ａｔ。…ａｔ …ａｔ ｝ 是强可调度的，即ＡＴ必须满足条件ＡＴ （ａｔ ）一 ＡＴ （ａｔ ）≥ （ａｔ ），那么该ＴＣＰＮ协同设计资源约 束路径Ｒ是可调度的．如果所有从资源初始状态 Ｍｏ到达资源结束状态Ｍ 的资源约束路径都是可 调度的，那么该ＴＣＰＮ协同设计资源约束网是可调 度的． 规则２．变迁序列ＡＴ一｛ａｔ ａｔ：…ａｔ …ａｔ ｝是 强可调度，当且仅当ＡＴ中除初始变迁外所有同步 变迁是强可调度，所有非同步变迁是弱可调度． 由于非同步变迁的弱可调度也是强可调度 的 ］，所以也可以说一个基于ＴＣＰＮ的协同设计资 源约束是可调度的，当且仅当网中全部设计活动变 迁是强可调度的． ３ 基于ＴＣＰＮ协同设计过程资源约束模型 的可调度性算法 ３．１资源约束可调度性算法 资源约束可调度性算法的思想如下：将协同设 计过程的资源约束ＴＣＰＮ网从设计活动的开始状 态到结束状态划分成Ｓ条链路Ｒ＝＝＝｛Ｍｏａｔ Ｍ１ａｔ。 … ａｔ Ｍ …ａｔ Ｍ ｝，其划分原则是按照ＴＣＰＮ资源网 中的冲突结构决策条件进行分解．构建第Ｋ（Ｋ≤ｓ） 条链路中除第一个变迁之外的所有资源库所和设计 活动变迁的序列Ｈｋ（Ｍｏ一 ）一｛ａｔ ｒｐ１，ａｔ２ｒｐ２，…， ａｔ ｒｐ 一，ａｔ ｒｐ ｝，判断该路径所包含的变迁序列 ＡＴ＝｛ａｔ ａｔ２…ａｔ …ａｔ ｝中每个变迁ａｔ 是否为同步 变迁．若为同步变迁，则按照强可调度规则计算其最 早／最晚触发时间ＡＴ （ａｔ）／ＡＴ。 （ａｔ）；若为非同步 变迁，则按照弱可调度规则计算．若ＡＴＬＦ（ａｔ ）一 ＡＴＥ （ａｔ ）≥ｔ （ａｔ ），说明ａｔ 是强可调度的；否则， 说明变迁ａｔ 不能在时间约束范围内成功完成触 发，调用时间修正算法进行时间约束修正，再进行判 定．若ＡＴ一｛ａｔ ａｔ …ａｔ …ａｔ ｝所有的变迁均为强 可调度，则第Ｋ条资源约束链路是可调度的．这样， 如果ＴＣＰＮ的所有５条链路均强可调度，则整个 ＴＣＰＮ协同设计资源约束网是可调度的．该算法描 述如Ｆ： Ｓｔｅｐ１．根据ＲＣＣＤ—ＴＣＰＮ中所存在的冲突结构决策条 件，将ＲＣＣＤ—ＴＣＰＮ划分成Ｓ条状态链路 Ｒ，一｛ 以 ｎ￡ …ｎ Ｍ Ｍ：）， 其中１≤ ≤Ｓ，令Ｋ一１． 第１Ｏ期 郭银章，等：基于ＴＣＰＮ的协同设计过程资源约束可调度性分析 Ｓｔｅｐ２．构建第Ｋ条链路的Ｈ （ 一Ｍ ）一｛ａｔ｛ｒｐ｛， ａｔ ｒｐｌ，…，口 ｒ ，…，Ⅱ ｒｐ ｝，给所有ａｔ 赋值［ＴＣ…（ａｔ ）， 到目的，所以只有通过增大ＴＣ （ａｔ ）达到目的．具 体算法描述如下： Ｓｔｅｐ１．ＴＣ （ａｔ ）一ＴＣ （ａｔ ）一Ｐ，若ＴＣ…（ｎ ）＞Ｏ，贝０ 执行下一步；否则，转Ｓｔｅｐ３． Ｓｔｅｐ２．重新计算设计活动变迁ａｔ 的最早／最晚触发时 间，如果ＡＴＩ （口 ）一ＡＴＥＦ（ｎ ）≥ｔｄ（口 ），转Ｓｔｅｐ５；否则，转 Ｓｔｅｐ１． ＴＣ…（ａｔ ）］／ （ａｔ ），给所有ｒ 赋值［ＴＣ…（ｒｐ ）， ＴＣ…（ｒｐ ）］．令 一１，若Ｋ≤Ｓ，执行下一步；否则，程序结 束，输出结果． Ｓｔｅｐ３．记第Ｋ条链路的第一个变迁的结束时间为 ＡＴ （ｎ ），若 ≤ ，读取第Ｋ条链路的第ｉ个变迁ａｔ ；否 则，Ｋ—Ｋ＋１，转Ｓｔｅｐ２． Ｓｔｅｐ４．判断变迁ａｔ 是否为同步变迁．若是，执行下一 步；否则，转Ｓｔｅｐ６． Ｓｔｅｐ３．ＴＣ…（ｎ ）一丁Ｃ （ｎ ）＋Ｐ． ｓｔｅｐ４．重新计算设计活动变迁 的最早／最晚触发时 间，如果ＡＴ （口 ）一ＡＴｅｒ（ｎ ）≥ （ｎ ），则执行下一步；否 则，转Ｓｔｅｐ３． Ｓｔｅｐ５．程序结束． Ｓｔｅｐ５．确定第Ｋ条链路的第ｉ个变迁ａｔ 之前的所有 变迁序列ＡＴ 一｛ａｔ｛ａｔ …ａｔＬ ｝和输入库所序列ＲＰ 一 ｛ｒ ，ｒ ，…，ｒ夕 一ｔ｝．根据式（５）（６）计算ｔｏｋｅｎ到达的上下 界时间．根据式（３）（４）计算ａｔ 的最早／最晚触发时间 Ａ Ｆ（ａｔ ） Ｆ（ａｔ ），转Ｓｔｅｐ７． ４ 实 例 Ｓｔｅｐ６．根据式（１）（２）计算ａｔ 的最早／最晚触发时间 ＡＴＥＦ（ａｔ ）／ＡＴＩ Ｆ（ａｔ ），执行下一步． Ｓｔｅｐ７．若Ａ丁ｌ Ｆ（ａｔ ）一ＡＴＥＦ（ａｔ ）≥ｔ （ａｔ ），则ｉ—ｉ＋ １，转Ｓｔｅｐ３；否则，调用约束修正算法进行修正，ｉ—ｉ＋１，转 Ｓｔｅｐ３。 ４．１链式输送机传动系统协同设计过程建模 链式输送机的传动系统设计．根据用户设计任务 书，首先进行系统的规范性初步设计；其次进行方案 设计，包括变速装置、起停装置、换向装置、制动装置、 保护装置的功能结构分解、子功能设计和原理方案设 ３．２资源约束时间修正算法 当ＡＴＩ Ｆ（ａｔ ）一ＡＴＥＦ（ａｔ ）＜ｔｄ（ａｔ ）时，表明 计；第三步进行总体设计，包括分析拟定传动方案、电 动机动力型号选择、计算总传动比和分配各级传动 比、计算传动装置的运动和动力参数；第四步进行结 构设计，包括分析和选定传动装置的结构方案、轴和 轴承部件的结构设计、校核轴、键、联轴器的强度和进 行滚动轴承的寿命校核；第五步进行零部件图设计， ａｔ 的时间约束不满足可调度性要求．由于变迁ａｔ 之前的库所变迁序列｛ｎ ｒ ，ｎ ｒ ，…，ａｔｅ＿ ｒ ｝ 的可调度性已得到验证，所以仅修正变迁ａｔ 及其 输入库所的时间约束，不会影响｛ａｔ ｒｐ ，ａｔ！ｒｐｌ，…， ａ ｒ ｝的可调度性判断，其ｔｏｋｅｎ到达的时间上 下界也不会改变．具体的修正策略是减小ＴＣ…（ｒｐ ） 或ＴＣ （ａｔ ），或者增大ＴＣ （ｒｐ ）或ＴＣ…（ａｔ ）． 但是由式（１）～（４）分析可知，ｒｃ 。 （ｒｐ ）为输入资 源库所获得资源的最小时间，不能够减小，所以仅可 通过减小ＴＣ…（ａｔ ）来达到减小ＡＴ耶（ｎ ）的目的， 直到ＴＣ （ａｔ ）＝＝：０或者ＡＴＩＪ（ａｔ ）一ＡＴＥＦ（ｎ ）≥ （ａｔ ）成立．当ＴＣ ｉ （ａｔ ）一０时，需要通过增大 ＡＴ。 （ａｔ ）来修正．由于通过增大ＴＣ…（ｒｐ ）无法达 包括齿轮类、轴类、箱体机架类工作图的绘制；最后进 行设计优化．鉴于设计方案的复杂性，本文仅研究链 式输送机传动系统结构设计过程中资源约束可调度 性分析．基于ＴＣＰＮ的链式输送机传动系统协同设计 过程模型如图５所示． 整个链式输送机传动系统结构协同设计过程资 源约束ＴＣＰＮ的资源库所时间约束集如表１所示，设 计活动变迁的时间约束集如表２所示． ５７ ａｔ９ ５８ 图５链式输送机传动结构协同设计ＴＣＰＮ模型 １ ７８６ 计算机辅助设计与图形学学报 第２３卷 表２链式输送机传动结构设计活动变迁时间约束集 变迁 ａｔ ＆ ａｔ３ ““ ａｔｓ 设计活动 初步设计 方案设计 总体设计 设计方案优化 总装设计任务分派 ［ＴＣ…（Ⅱ ）／ＴＣ…（ｄｆ）］ ［幻（ｄ ）］ ［２，７］ ［３，１１］ ［２，９］ ［１，７］ ［１，５］ ［３］ ［７］ ［８］ Ｉｓ］ ［２］ 变迁 ａｔｍ ａｔ・ ａｔ ｚ ａｔｌ ｓ ａｔｌ４ 设计活动 总装设计图汇总 零部件设计任务分派 轴类零部件图设计 齿轮零部件图设计 箱体机架类图设计 ［ＴＣ…（ｎ￡）／７℃ （“ｆ）］ ［ （ｎ￡）］ ［１，３］ ［１，４］ ［３，１１］ ［３，ｌｚ］ ［３，ｌｏ］ ［２］ ［２］ ［７］ ［７］ ［７］ “ｒ６ ａｔ７ ａｔ８ ａｔ 拟定传动结构方案 轴、轴承部件结构设计 轴键、联轴器强度校核 滚动轴承寿命校核 ［２，６］ ［４，８］ ［２，８］ ［１，４］ ［３］ ［５３ ［４３ ［２］ ａｔｌ ５ ａｔｌ ６ （１ｔ１ ７ 零部件图汇总 施工图设计 文档整理提交 ［１，４］ ［２，５］ ［１，４］ ［２］ ［６］ ［２］ ４．２模型资源约束可调度性分析与修正 弱可调度验证过程如下： ＡＴＥＦ（ａｔ３）一ｍａｘ｛ＴＣ…（ｒｐ３）｝＋ＴＣ…（ａｔ３）一３＋２—５， １）变迁序列．ＡＴ１一｛ａｔ１，ａｔ２，ａｔ３，ａｔ。，ａｔ５｝， Ａ丁２一｛｛ａｔ６），｛ａｔ７｝｛ａｔ８）｛ａｔ。）｛ａｔ１１｝｛ａｔ１ ２｝｛ａｔ】。） ＡＴＩ Ｆ（ａｔ３ ）一ｒａｉｎ｛ｍｉｎ｛ＴＣ…（ｒｐ３）），ｍａｘ｛ＴＣ…（ｒｐ３）｝＋ ＴＣ （ａｔ３））一３＋９—１２， ＡＴＩ Ｆ（ａｔ３）ＡＴＥＦ（ａｔ３）一１２—５—７＜８一ｔｄ（ａｔ３）， ｛ａｔ ｝｝以及ＡＴ。一｛ａｔ ａｔ ｝中的设计活动变迁， 每个变迁仅有一个输入库所，均为非同步变迁，所以 采用弱可调度计算式（１）（２）进行可调度性验证．验 证ａｔ 的弱可调度过程如下： ＡｒＥｖ（ａｔ２）一ｍａｘ｛ＴＣ…（ｒｐ２）｝＋ＴＣ…（ａｔ２）一２＋３—５， 不满足可调度约束条件．说明ａｔ。不可调度，调用约束 修正算法进行修正，当［ＴＣ…（ａｔ。），ＴＣ…（ａｔ。）］一 ［１，９］时，满足可调度约束条件．说明ａｔ。弱可调度． 同理，按照弱可调度判定规则，设计活动变迁 ＡＴｌ Ｆ（ａｔ ２）一ｒａｉｎ｛ｍｉｎｉＴＣ…（ｒｐ２）），ｍａｘ｛ＴＣ （ｒｐ２）｝＋ ＴＣ… （ａｔ２））一２＋１１－二１３， ＡＴＩ Ｆ（ｎ ２） ＡＴＥＦ（ａｔ２）一１３—５—８＞７一ｔｄ（“ｆ２）， ａｔ 和ａｔ 。均不满足可调度约束条件，采用时间修正 算法进行修正，当［ＴＣ…（ａｔ ），ＴＣ…（ａｔ ）］一［２， ８］，［ＴＣ…（ａｔ ），ＴＣ…（ａｔ ）］一［０，６］时，ａｔ 和 ａｔ 满足可调度约束条件．部分变迁约束修订后如 表３所示． 满足可调度约束条件．说明ａｔ 弱可调度，即强可调 度．同理可以证明，变迁ａｔ１，ａｔ４，ａｔ５，ａｔ６，ａｔ８，ａｔ９， ａｔ ａｔ１ ２，ａｔｌ＝｛’ａｔ…ａｔ１ ７均弱可调度．对于变迁ａｔ３其 第１０期 郭银章，等：基于ＴＣＰＮ的协同设计过程资源约束可调度性分析 １７８７ ２）对于设计活动变迁ａｔ 。和ａｔ 均有多个输入 库所，属于同步变迁，采用强可调度方法进行可调度 性判定． 根据式（５）（６）求ａｔ 。的输入库所ｒ ｒ ｓ ， ｒ户 ，ｒ ５８的ｔｏｋｅｎ到达上下界，令变迁ａｔ 为初始变 迁，则 ｆｍｉｎ｛ＴｏｋｅｎＡ（ｒｐ ５２）｝一ＡＴＩ』（）（ａｔ１）＋４４ 【ｍａｘ｛ＴｏｋｅｎＡ（ｒｐ ５２）｝一ＡＴ“）（ａｔ１）＋４９ ｆｒｎｉｎ｛ＴｏｋｅｎＡ（ｒｐ ５４））一ＡＴｌ ｏ（ａｔ１）＋４６ ｌｍａｘ｛ＴｏｋｅｎＡ（ｒｐ ５４））一ＡＴＩ』（】（ａｔ１）＋５１ ｆｍｉｎ｛ＴｏｋｅｎＡ（ｒｐ ５６））一ＡＴＩ ｏ（ａｔ１）＋４５ 【ｍａｘ｛ＴｏｋｅｎＡ（ｒｐ ５６））一ＡＴｌＪ（】（ａｔ１）＋５１ ｆｍｉｎ｛ＴｏｋｅｎＡ（ｒｐ ５８）｝一ＡＴＩ ｏ（口￡１）＋４６ ｌｍａｘ｛ＴｏｋｅｎＡ（ｒｐ ５８））一ＡＴＩ』（）（ａｔ１）＋４７ 根据式（３）（４）求ａｔ 。的最早／最晚触发时间 ＡＴ ＥＦ（ａｔ１ｏ）一ｍａｘ｛ＡＴＩ ｏ（ａｔ１）＋４４＋３， ＡＴＩ （）（ａｔ１）＋４６＋１，盯Ｉ』（】（ａｔ１）＋４５＋２， ＡＴＩ ｏ（ａｔ１）＋４６＋１）＋１一ＡＴＩＪ （】（ａｔ１）４－４８， Ａ丁Ｉ Ｆ（ａｔ１ｏ）一ｍｉｎ｛ｍｉｎ｛ＡＴＩ ０（ａｔ１）＋４９＋１０， ＡＴＩｏ（ａｔ１）＋５１＋１０，ＡＴＩ ｏ（ａｔ１）＋５１＋１３， ，ＡＴＩ ｏ（ａｔ１）＋４７＋７｝，ｍａｘ｛Ａ丁【Ｊ【）（ａｔ１）＋ ４９＋３，ＡＴＩ，ｏ（ａｔ１）４－５１＋１，ＡＴＩ （】（ａｔ１）＋５１＋ ２，ＡＴＩＪ（）（ａｔ１）４－４７＋１）＋３＝ＡＴＩ』（）（ａｔ１）４－５４， 判定ＡＴＩ Ｆ（ａｔｌ０）一ＡＴＥＦ（ａｔ１０）一（ＡＴｌ （）（ａｔ１）＋ ５４）一（ＡＴ“）（ａｔ１）４－４８）一６＞２一ｔｄ（ａｔ】０）成立． 所以设计活动变迁ａｔ 。是强可调度的，同理可 证设计活动变迁ａｔ 也是强可调度的．至此，根据规 则１知，链式输送机传动系统结构协同设计过程资 源约束ＴＣＰＮ模型经局部约束修订后，整个网络是 可调度的． ５ 结束语 产品协同设计过程的资源约束，本质上就是一 个任务的设计活动对设计资源的请求、占有时间的 限制和调度问题．在产品协同设计过程中，由于设计 资源具有共享、并发和重用等依赖关系，所以协同设 计过程的资源约束可调度性研究就是探讨设计资源 冲突控制和消解的过程．本文基于ＴＣＰＮ建立了产 品协同设计过程的资源约束网模型，分析并定义了 设计活动变迁最早／最晚使能时间、最早／最晚触发 时间和开始／结束时间语义关系；提出了非同步变迁 的弱可调度定义和同步变迁的强可调度定义；并给 出其可调度性规则和算法．对于不可调度的约束提 出一种基于时间松弛的时间约束修正算法．最后基 于一个实例验证了本文算法的有效性．基于ＴＣＰＮ 的产品协同设计过程资源约束可调度性研究，为实 现协同设计过程的资源管理与控制提供了一种新的 方法． 参考文献（Ｒｅｆｅｒｅｎｃｅｓ）： ［１２ Ｓｈａｎ Ｈｏｎｇｂｏ．Ｓｕｒｖｅｙ ｏｆ ｃｕｒｒｅｎｔ ｒｅｓｅａｒｃｈ ｏｎ ｔｈｅ ｍｏｄｅｒｎ ｐｒｏｄｕｃｔ ｄｅｓｉｇｎ ｔｈｅｏｒｙ ａｎｄ ｍｅｔｈｏｄｏｌｏｇｙ［Ｊ］．Ｊｏｕｒｎａｌ ｏｆ Ｄｏｎｇｈｕａ Ｕｎｉｖｅｒｓｉｔｙ：Ｎａｔｕｒａｌ Ｓｃｉｅｎｃｅｓ Ｖｅｒｓｉｏｎ，２００６，３２（５）： １１８—１２４（ｉｎ Ｃｈｉｎｅｓｅ） （单鸿波．现代产品设计理论的相关研究现状综述ＥＪ］．东华 大学学报：自然科学版，２００６，３２（５）：１１８－１２４） ［２］Ｌｉ Ｙｕａｎ，Ｐｅｎｇ Ｈｕｉ，Ｓｈｅｎ Ｌｉｎｃｈｅｎｇ．Ｃｏｎｓｔｒａｉｎｔ ｓａｔｉｓｆａｃｔｉｏｎ ｂａｓｅｄ ｒｅｓｏｕｒｃｅ ｃｏｎｆｌｉｃｔｓ ｄｅｔｅｃｔｉｏｎ ａｎｄ ｒｅｓｏｌｕｔｉｏｎ ｉｎ ｃｏｌｌａｂｏｒａｔｉｖｅ ｍｉｓｓｉｏｎ ｐｌａｎｎｉｎｇ ＥＪ］．Ｓｙｓｔｅｍｓ Ｅｎｇｉｎｅｅｒｉｎｇ ａｎｄ Ｅｌｅｃｔｒｏｎｉｃｓ，２００９，３１（４）：８６８—８７３（ｉｎ Ｃｈｉｎｅｓｅ） （李远，彭辉，沈林成．协同任务规划中基于约束满足的 资源冲突检测与消解［Ｊ］．系统工程与电子技术，２００９，３ｌ （４）：８６８－８７３） ［３］Ｄｕ Ｙａｎｈｕａ，Ｆａｎ Ｙｕｓｈｕｎ． Ｍｏｄｅｌｉｎｇ ａｎｄ ａｎａｌｙｚｉｎｇ ｏｆ ｕｎｃｅｒｔａｉｎ ｔｉｍｅ ｆｏｒ ｍｕｌｔｉ—ｐｒｏｃｅｓｓ ｏｆ ｗｏｒｋｆｌｏｗｓ ｗｉｔｈ ｒｅｓｏｕｒｃｅ ｃｏｎｓｔｒａｉｎｔｓ［Ｊ］．Ｊｏｕｒｎａｌ ｏｆ Ｍｅｃｈａｎｉｃａｌ Ｅｎｇｉｎｅｅｒｉｎｇ，２０１０，４６ （４）：１６９－１７６（ｉｎ Ｃｈｉｎｅｓｅ） （杜彦华，范玉顺．资源约束下多过程的不确定时间建模与分 析口］．机械工程学报，２０１０，４６（４）：１６９—１７６） ［４］Ｌｉｕ Ｓｈｅｎｇ，Ｆａｎ Ｙｕｓｈｕｎ．Ｍｅｔｈｏｄ ｆｏｒ ａｎａｌｙｚｉｎｇ ｓｔａｙｉｎｇ—ｔｉｍｅ ｏｆ ｉｎｓｔａｎｃｅｓ ｉｎ ｗｏｒｋｆｌｏｗ ｍｏｄｅｌｓ ｗｉｔｈ ｒｅｓｏｕｒｃｅｓ ｃｏｎｓｔｒａｉｎｔｓ ［Ｊ２．Ａｃｔａ Ｅｌｅｃｔｒｏｎｉｃａ Ｓｉｎｉｃａ，２００５，３３（１０）：１８６７—１８７１（ｉｎ Ｃｈｉｎｅｓｅ） １７８８ 计算机辅助设计与图形学学报 第２３卷 （刘 胜，范玉顺．资源约束下实例在工作流中停留时间分析 方法ＥＪ］．电子学报，２００５，３３（１０）：１８６７—１８７１） 刚 Ｅｓ］ Ｐａｎ Ｙａｎ，Ｔａｎｇ Ｙｏｎｇ．Ｍｏｄｅｌｉｎｇ ｏｆ ｆｕｚｚｙ ｔｅｍｐｏｒａｌ ｗｏｒｋｆｌｏｗ ｎｅｔ ｓ ａｎｄ ｉｔｓ ｔｉｍｅ ｐｏｓｓｉｂｉｌｉｔｙ ａｎａｌｙｓｉｓ ＥＪ１．Ｃｏｍｐｕｔｅｒ Ｉｎｔｅｇｒａｔｅｄ Ｍａｎｕｆａｃｔｕｒｉｎｇ Ｓｙｓｔｅｍｓ， ２００６， １２（１１）： １７７９—１ ７８４（ｉｎ Ｃｈｉｎｅｓｅ） （潘 炎，汤 庸．模糊时态＿Ｔ作流网的建模和时间可能性分 析［Ｊ］．计算机集成制造系统，２００６，１２（１１）：１７７９—１ ７８４） Ｃ６３ Ｄｕ Ｓｈｕａｎｚｈｕ，Ｔａｎ Ｊｉａｎｒｏｎｇ，Ｌｕ Ｇｕｏｄｏｎｇ．Ａｎ ｅｘｔｅｎｄｅｄ ｔｉｍｅ ｗｏｒｋｆｌｏｗ ｍｏｄｅｌ ｂａｓｅｄ ｏｎ ＴｗＦ—ｎｅｔ ａｎｄ ｉｔｓ ａｐｐｌｉｃａｔｉｏｎ［Ｊ］． Ｊｏｕｒｎａｌ ｏｆ Ｃｏｍｐｕｔｅｒ Ｒｅｓｅａｒｃｈ ａｎｄ Ｄｅｖｅｌｏｐｍｅｎｔ，２００３，４０ （４）：５２４～５３０（ｉｎ Ｃｈｉｎｅｓｅ） （杜拴柱，谭建荣，陆国栋．一个基于ＴｗＦ—ｎｅｔ的扩展时间工 作流模型及其应用［Ｊ］．计算机研究与发展，２００３，４０（４）： ５２４－５３０） Ｃｈｅｎｇ Ｌｉｘｉｎ，Ｉ ｉｕ Ｙｕｎｙｕｎ． Ａｎ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｒｅｓｏｕｒｃｅ ｃｏｎｓｔｒａｉｎｅｄ ｓｃｈｅｄｕｌｉｎｇ ｗｉｔｈ ｃｌｏｃｋ ｓｅｌｅｃｔｉｏｎ［Ｊ］．Ｊｏｕｒｎａｌ ｏｆ Ｃｏｍｐｕｔｅｒ—Ａｉｄｅｄ Ｄｅｓｉｇｎ＆Ｃｏｍｐｕｔｅｒ Ｇｒａｐｈｉｃｓ，２０１０，２２（２）： ２４０—２４６（ｉｎ Ｃｈｉｎｅｓｅ） （程利新，刘云云．动态选择时钟的资源约束下调度算法［Ｊ］． 计算机辅助设计与图形学学报，２０１０，２２（２）：２４０—２４６） Ｉ ｉ Ｚｕｘｉｎ， Ｗａｎｇ Ｗａｎｌｉａｎｇ， Ｃｈｅｎｇ Ｘｉｎｍｉｎ． Ｍｅｓｓａｇｅ ｓｃｈｅｄｕｌｉｎｇ ａｎｄ ａｓｙｍｐｔｏｔｉｃ ｓｔａｂｉｌｉｔｙ ｏｆ ｓｙｓｔｅｍ ｗｉｔｈ ｒｅｓｏｕｒｃｅ ｃｏｎｓｔｒａｉｎｔｓ ＥＪ］．Ｉｎｆｏｒｍａｔｉｏｎ ａｎｄ Ｃｏｎｔｒｏｌ，２００８，３７（５）：５９３— ５９９（ｉｎ Ｃｈｉｎｅｓｅ） （李祖欣，王万良，成新民．资源约束系统的信息调度及其渐 近稳定性［Ｊ］．信息与控制，２００８，３７（５）：５９３—５９９） Ｌｉ Ｚｕｘｉｎ，Ｗａｎｇ Ｗａｎｌｉａｎｇ，Ｉ，ｅｉ Ｂｉｃｈｅｎｇ．Ｏｐｔｉｍａｌ ｃｏｎｔｒｏｌ ａｎｄ ｓｃｈｅｄｕｌｉｎｇ ｏｆ ｓｙｓｔｅｍ ｗｉｔｈ ｒｅｓｏｕｒｃｅ ｃｏｎｓｔｒａｉｎｔｓ［Ｊ］．Ｃｏｎｔｒｏｌ Ｔｈｅｏｒｙ＆．Ａｐｐｌｉｃａｔｉｏｎｓ，２００９，２６（１）：９７—１０３（ｉｎ Ｃｈｉｎｅｓｅ） （李祖欣，王万良，雷必成．资源约束系统的控制与调度协同 优化方法［Ｊ］．控制理论与应用，２００９，２６（１）：９７—１０３）嘲 ［１０３ Ｘｉｅ Ｌｉｎｂｏ， Ｆａｎｇ Ｈｕａｊｉｎｇ， Ｗａｎｇ Ｈｕａ． Ｉｎｆｏｒｍａｔｉｏｎ ｓｃｈｅｄｕｌｉｎｇ ａｎｄ ａｓｙｍｐｔｏｔｉｃａｌ ｓｔａｂｉｌｉｔｙ ｏｆ ｎｅｔｗｏｒｋｅｄ ｃｏｎｔｒｏｌ ｓｙｓｔｅｍｓ［Ｊ］．Ｃｏｎｔｒｏｌ ａｎｄ Ｄｅｃｉｓｉｏｎ，２００４，１９（５）：５８９－５９ｌ（ｉｎ Ｃｈｉｎｅｓｅ） （谢林柏，方华京，王华．网络化控制系统的信息调度与稳 定性研究ＥＪ］．控制与决策，２００４，１９（５）：５８９—５９１） ［１１］ Ｒｅｈｂｉｎｄｅｒ Ｈ， Ｓａｎｆｒｉｄｓｏｎ Ｍ． Ｓｃｈｅｄｕｌｉｎｇ ｏｆ ａ ｌｉｍｉｔｅｄ ｃｏｍｍｕｎｉｃａｔｉｏｎ ｃｈａｎｎｅｌ ｆｏｒ ｏｐｔｉｍａｌ ｃｏｎｔｒｏｌ［Ｊ］．Ａｕｔｏｍａｔｉｃａ， ２００４，４０（３）：４９１—５００ ［１２］ Ｇｏｏｄｗｉｎ Ｇ Ｃ，Ｈａｉｍｏｖｉｃｈ Ｈ，Ｑｕｅｖｅｄｏ Ｄ Ｅ，ｅｔ ａ１．Ａ ｍｏｖｉｎｇ ｈｏｒｉｚｏｎ ａｐｐｒｏａｃｈ ｔｏ ｎｅｔｗｏｒｋｅｄ ｃｏｎｔｒｏｌ ｓｙｓｔｅｍ ｄｅｓｉｇｎ ＥＪ］， ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｉｌ Ａｕｔｏｍａｔｉｃ Ｃｏｎｔｒｏｌ，２００４，４９（９）： ｌ４２７－１４４５ ［１ ３］ Ｌｕｏ Ｙａｂｏ，Ｘｉａｏ Ｔｉａｎｙｕａｎ．Ｃｏｒｒｅｌａｔｉｏｎ—ｂａｓｅｄ ｍｅｔｈｏｄｏｌｏｇｙ ｆｏｒ ｒｅｓｏｕｒｃｅ ｓｃｈｅｄｕｌｉｎｇ ｉｎ ｓｙｎｃｈｒｏｎａｌ ｃｏｏｐｅｒａｔｉｖｅ ｄｅｓｉｇｎ ｓｙｓｔｅｍ ＥＪ］．Ｃｏｍｐｕｔｅｒ Ｉｎｔｅｇｒａｔｅｄ Ｍａｎｕｆａｃｔｕｒｉｎｇ Ｓｙｓｔｅｍｓ， ２００４．１０（４）：３９９－４０４（ｉｎ Ｃｈｉｎｅｓｅ） （罗亚波，肖田元．同步协同设计中基于关联关系的资源调度 方法［Ｊ］．计算机集成制造系统，２００４，１０（４）：３９９－４０４） ［１４］ Ｔｓａｉ Ｊ Ｊ Ｐ，Ｙａｎｇ Ｓ Ｊ，Ｃｈａｎｇ Ｙ Ｈ．Ｔｉｍｉｎｇ ｃｏｎｓｔｒａｉｎｔ Ｐｅｔｒｉ ｎｅｔｓ ａｎｄ ｔｈｅｉｒ ａｐｐｌｉｃａｔｉｏｎ ｔｏ ｓｃｈｅｄｕｌａｂｉｌｉｔｙ ａｎａｌｙｓｉｓ ｏｆ ｒｅａｌ—ｔｉｍｅ ｓｙｓｔｅｍ ｓｐｅｃｉｆｉｃａｔｉｏｎｓ［Ｊ］．ＩＥＥＥ Ｆｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｓｏｆｔｗａｒｅ Ｅｎｇｉｎｅｅｒｉｎｇ，１９９５，２１（１）：３２—４９ ［１５］ Ｖｅｎｋａｔｅｓｈ Ｋ，Ｚｈｏｕ Ｍ．Ｏｂｊｅｃｔｅｄ ｏｒｉｅｎｔｅｄ ｄｅｓｉｇｎ ｏｆ ＦＭＳ ｃｏｎｔｒｏｌ ｓｏｆｔｗａｒｅ ｂａｓｅｄ ｏｎ ｏｂｊｅｃｔ ｍｏｄｅｌｉｎｇ ｔｅｃｈｎｉｑｕｅ ｄｉａｇｒａｍｓ ａｎｄ Ｐｅｔｒｉ ｎｅｔｓ ｌ＿Ｊ］．Ｊｏｕｒｎａｌ ｏｆ Ｍａｎｕｆａｃｔｕ ｒｉｎｇ Ｓｙｓｔｅｍｓ。１ ９９８， 】７（２）．１１８—１３６
