数据流图（DFD）

数据流图是在逻辑上描述系统的功能、输入、输出和数据存储等。

数据流图中的基本图形元素包括：

基本元素 图形表示
数据流 数据流
加工 加工
数据存储 数据存储
外部实体 外部实体

软件系统内部的数据处理模型，使用数据流、加工和数据存储构建。

  • 数据流（Data Flow）：由一组固定成分的数据组成，表示数据的流向。

    数据流

    在DFD种，数据流的流向由以下几种：

    • 从加工流向另一个加工；
    • 从加工流向数据存储（写）；
    • 从数据存储流向加工（读）；
    • 从外部实体流向加工（输入）；
    • 从加工流向外部实体（输出）。

    即数据流的起点或终点必须至少有一个是加工。

    除了与数据存储有关的数据流（流向数据存储或从数据存储流出），DFD中的每个数据流都必须用一个定义明确的名字表示。

  • 加工（Process）：加工描述了输入数据流到输出数据流之间的变换，也就是输入数据流经过什么处理后变成了输出数据流。

    加工

    每个加工都有一个名字和编号。

    一个加工可以有多个输入数据流和多个输出数据流，但至少有一个输入数据流和一个输出数据流。

    数据流图中常见的3种错误如下所示：

    • 黑洞：加工只有输入，没有输出。

      如下图加工1。

    • 白洞：加工只有输出但没有输入。

      如下图加工2。

    • 灰洞：加工中输入数据不足以产生输出数据。

      有几种可能的原因：

      • 一个错误的命名过程；
      • 错误命名的输入或输出；
      • 不完全的事实。

      如下图加工3。

    数据流图中常见错误

  • 数据存储（Data Store）：存储和提供数据。

    数据存储

    每个数据存储都有一个定义明确的名字标识。

    数据存储可以：

    • 存储加工的输出数据：数据流流入数据存储，表示数据的写入操作；
    • 提供加工的输入数据：数据流从数据存储流出，表示数据的读操作。
    • 双向箭头的数据流指向数据存储，表示对数据的修改。

    DFD中的数据存储在具体实现时可以用以下方式实现：

    • 文件系统实现；
    • 数据库系统实现。

    数据存储的存储介质可以是：

    • 磁盘、
    • 磁带、
    • 其他存储介质。

  • 外部实体（External Agent，外部主体）：指存在于软件系统之外的人员、组织、物体或外部系统，它指出系统所需数据的发源地（源）和系统所产生的数据的归宿地（宿）。

    外部实体

    例如：

    • 人员：学生、老师、员工、主观、医生、客户……
    • 组织：供应商、采购部门……
    • 物体：传感器、控制器、单车、车辆……
    • 外部系统：支付系统、车辆交易系统、库存管理系统、道闸控制系统……

    在许多系统中，某个源和某个宿可以是同一个人员、组织、物体或外部系统，此时，在DFD中可以用同一个符号表示：

    • 当数据流从该符号流出时，表示它是源；
    • 当数据流流向该符号时，表示它是宿；
    • 当两者皆有时，表示它既是源又是宿。

    外部实体表示存在于系统之外的对象，用来帮助用户理解系统数据的来源和去向。

数据流图必须确保：

  • 数据流的起点或终点必须至少有一个是加工。
  • 加工至少有一个输入数据流和一个输出数据流。

分层数据流图：

  1. 顶层图：描述系统的输入和输出。

    即描述系统从哪些外部实体接受数据流，以及系统发送数据流到哪些外部实体。

    • 顶层图只有一个加工，即待开发的软件系统。
    • 顶层图中的数据流就是系统的输入/输出信息。
    • 顶层图中通常没有数据存储。

  2. 0层图：分解顶层图的加工。

  3. 再分解：将DFD中某些比较复杂的加工再次分解成一张DFD子图。

实体联系图（E-R 图，ERD）

E-R图有以下几个成分（包含扩充的E-R模型成分）：

E-R图中的主要构件

  • 实体：用矩形表示。

    • 弱实体：使用双线矩形框表示。将需要依赖其他实体存在的实体。

      实体间的所有（Ownership，拥有）关系代表一个实体对另一些实体具有很强的依赖关系，即一个实体的存在必须以另一个实体为前提。

      例如职工与家属的联系，家属总是属于某职工的（在关系模式中需要依赖职工而存在），所以家属是弱实体。

    • 特殊化：将一个实体集按照某些特性区分为几个子实体。这种从普遍到特殊的过程即为特殊化。

      子实体的图形表示如下：

      子实体

      子实体由称为子类，它会有一个超类，并且能继承超类的属性，超类的属性是实体集中所有子实体的相同属性。

  • 联系：用棱形表示，并用无向边分别与有关实体连接起来，同时在无向边标注联系的类型。

    联系的类型有两种：

    • 两个实体间的联系：

      • $1 : 1$：一对一联系；
      • $1 : n$：一对多联系；
      • $m : n$：多对多联系。

    • 两个以上实体间的联系：

      例如3个实体间的联系有：

      • $1 : 1 : 1$
      • $1 : 1 : n$
      • $1 : m : n$
      • $r : m : n$

  • 属性：用椭圆形表示，并用无向边将其与相应的实体连接起来

    E-R模型中的属性有以下分类：

    • 简单属性：是原子的、不可再分的。
    • 复合属性：可以细分为更小的部分。
    • 单值属性：一个属性对应一个值。
    • 多值属性：一个属性对应一组值。
    • NULL属性：实体在某个属性上没有值或属性值未知时，使用NULL值表示。
    • 派生属性：派生属性可以从其他属性得来（通过运算等方式求出）。

概念结构模型（合并分 E-R 图）

建立概念结构模型的步骤如下：

  1. 选择局部应用：选择适当层次的数据流图，让这一层的每一部分对应一个局部应用，实现某一项功能。

  2. 逐一设计分E-R图。

  3. E-R图合并：

    合并时需要考虑各分E-R图之间的冲突：

    • 属性冲突：同一属性在不同的分E-R图上的属性类型、取值范围和数据单位等可能会不一致。
    • 命名冲突：相同意义的属性在不同的分E-R图上可能会有不同的命名。
    • 结构冲突：同一实体在不同的分E-R图中可能会有不同的属性；同一对象在某一分E-R图中被抽象为实体，而在另一分E-R图中又可能被抽象为属性，反之亦然。

转换关系模式

  1. 实体向关系模式的转换：

    将E-R图中的实体逐一转换成为一个关系模式：

    • 实体名：对应关系模式的名称；
    • 实体的属性：转换成关系模式的属性；
    • 实体标识符：关系的码（键）。

    超类和子类的转换：超类和子类定义为两个关系模式，将超类的主键加到子类中。

  2. 联系向关系模式的转换：

    • 一对一联系的转换：

      有两种方式：

      • 方式1：将联系转换成一个独立的关系模式，关系模式的名称取联系的名称，关系模式的属性包括该联系所关联的两个实体的码及联系的属性，关系的码取自任一方实体的码。

        那么一个一对一联系需要转换成三个关系模式。

      • 方式2（一般使用该方式）：将联系归并到关联的两个实体的任一方，给待归并的一方实体属性集中增加另一方实体的码和该联系的属性即可，归并后的实体码保持不变。

        一个一对一联系仅需转换成两个关系模式。

      例如：

      联系向关系模式的转换示例

      • 方式1：

        厂长（姓名，性别，年龄）

        工厂（厂号，厂名，地点）

        管理（（厂长）姓名，厂号，任期）

        粗体代表该关系模式的码。管理的码可以为姓名或厂号。

      • 方式2：

        厂长（姓名，性别，年龄）

        工厂（厂号，厂名，地点，（厂长）姓名，任期）

    • 一对多联系的转换：

      两种方式：

      • 方式1：将联系转换成一个独立的关系模式，关系模式的名称取联系的名称，关系模式的属性取该联系所关联的两个实体的码及联系的属性，关系的码是多方实体的码；
      • 方式2（一般使用该方式）：将联系归并到关联的两个实体的多方，给待归并的多方实体属性集中增加一方实体的码和该联系的属性即可，归并后的多方实体码保持不变。

      例如：

      一对多联系转换的例子

      • 方式1:

        仓库（仓库号，地点，面积）

        商品（货号，商品名，价格）

        仓储（货号，仓库号，数量）

      • 方式2：

        仓库（仓库号，地点，面积）

        商品（货号，商品名，价格，仓库号，数量）

    • 多对多联系的转换：

      多对多联系只能转换成一个独立的关系模式，关系模式的名称取联系的名称，关系模式的属性取该联系所关联的两个多方实体的码及联系的属性，关系的码是多方实体的码构成的属性组。

      例如：

      多对多联系转换的示例

      转换成：

      学生（学号，姓名，性别，年龄）

      课程（课程号，课程名，学时）

      选修（（学号，课程号），成绩）

UML

UML（Unified Modeling Language，统一建模语言）是面向对象软件的标准化建模语言。

UML中包含3种基本构造块：

  • 事物；
  • 关系；
  • 图。

事物

UML中有4种事物：

  • 结构事物（Structural Thing）：模型的静态部分。

    结构事物的图形表示

  • 行为事物（Behavior Thing）：模型的动态部分。

    行为事物的图形表示

  • 分组事物（Grouping Thing）：模型的组织部分。

  • 注释事物（Annotational Thing）：模型的解释部分。

关系

UML中有4种关系，这4种关系是UML模型中可以包含的基本关系事物：

  • 依赖（Dependency）：是两个事物间的语义关系，其中一个事物（独立事物）发生变化会影响另一个事物（依赖事物）的语义。

    在图形上，把一个依赖画成一条可能有方向的虚线，如图：

    依赖的图形表示

    依赖有偶然性和临时性，即需要的时候依赖，不需要的时候不依赖。

  • 关联（Association）：是一种结构关系，它描述了一组链，链是对象之间的连接。

    关联使用实线表示，在关联上可以标注重复度（Multiplicity）和角色（Role）。

    描述了整体和部分间的结构关系的特殊类型的关联：

    • 聚集（Aggregation，聚合）：部分和整体的生命周期不一致，整体消失了，部分仍然存在，部分可以脱离整体存在。

      使用一端带空心菱形的实线表示。

    • 组合：部分和整体的生命周期一致，整体消失了，部分也消失了，部分不可以脱离整体而存在。

      使用一端带实心菱形的实线表示。

    关联和聚集的图形化表示

    聚合和组合中，带菱形的一端指向整体，另一端指向部分。

    关联的关系强度比依赖的关系强度要强一点。

    • 单向关联：用带箭头实线表示。

    • 多重度：

      进行面向对象设计时，类图中可以展现类之间的关联关系，还可以在类图中图示关联中的数量关系，即多重度。表示数量关系时，用多重度说明数量或数量范围，表示有多少个实例（对象）能被连接起来，即一个类的实例能够与另一个类的多少个实例相关联。

    • 关联类：

      当两个类之间的关联的重复度是多对多时，需要借助额外的属性来帮助表达它们之间的关系，而这个属性就需要定义在一个新的关联类中。关联类记录了这两个类之间的关联信息。关联中这些额外的属性用一条垂直于关联的实线表示，实线的一段连接接到关联的实线上，另一端指向这些属性。

  • 泛化（Generalization）：是一种特殊/一般关系，特殊元素（子元素）的对象可替代一般元素（父元素）的对象。用这种方法，子元素共享了父元素的结构和行为。

    在图形上，把一个泛化关系画成一条带有空心箭头的实线，它指向父元素：

    泛化的图形表示

  • 实现（Realization）：是类元之间的语义关系，其中一个类元指定了由另一个类元保证执行的契约。

    在图形上，把一个实现关系画成一条带有空心箭头的虚线，箭头指向模板类，另一端于实现类连接。

    实现的图形化表示

UML图

类图

类图（Class Diagram）展现了一组对象、接口、协作和它们之间的关系。在面向对象系统的建模中最常见的图就是类图。类图给出系统的静态设计视图。

类图中通常包括下述内容：

  • 类：

    类的图形表示

    类中的方法和属性前面有以下三种修饰符：

    修饰符 含义
    + public 公有的
    - private 私有的
    # protected 受保护的
    ~ package 包的

    例如：

    Student

    - id   : int
    + name : String
    + age  : int

    + getId() : int

  • 接口：

    接口的图形表示

  • 协作：

    协作的图形表示

  • 关系：

    依赖的图形表示

    关联图形化表示

    泛化的图形表示

类图示例

对象图

对象图（Object Diagram）展现了某一时刻一组对象以及它们之间的关系，描述了在类图中所建立的事物的实例的静态快照。

对象图一般包括对象和链，如图：

对象图示例

对象：对象图中的对象包含了类名、对象名和属性。

其图形化如下：

对象名 : 类名

属性1 = 值1
属性2 = 值2
......

匿名对象（没有对象名）：

: 类名

属性1 = 值1
属性2 = 值2
......

和类图一样，对象图给出系统的静态设计视图或静态进程视图，但它们是从真实的或原型实例的角度建立的。

用例图

用例图（Use Case Diagram）通常包括以下内容：

  • 用例：是从用户角度描述系统的行为，它将系统的一个功能描述成一系列的事件，这些事件最终对操作者产生有价值的观测结果。

    用例是一个类，它代表一类功能而不是使用该功能的某一具体实例。

    用例的图形表示

  • 参与者：是与系统交互的外部实体。

    参与者用一个人形图标表示。

  • 关系：

    • 用例之间的关系：

      • 包含关系：用带<<include>>的虚线箭头表示，如：

        包含关系

      • 扩展关系：用带<<extend>>的虚线箭头表示，如：

        扩展关系

        扩展用例是指，一个用例中，符合某些特定情况才会触发的另一个用例。

        即一个用例执行的时候，可能会发生一些特殊情况或可选情况，这种情况就是这个用例的扩展用例。

    • 参与者和用例之间的关联关系。

    • 用例与用例以及参与者与参与者之间的泛化关系。

用例图示例

序列图

序列图（Sequence Diagram，顺序图）描述了以时间顺序组织的对象之间的交互活动，强调消息时间顺序。

序列图的组成：

  1. 把参加交互的对象放在图的上方，沿水平方向排列。

    通常把发起交互的对象放在左边，下级对象依次放在右边。

  2. 把这些对象发送和接收的消息，沿垂直方向，按时间顺序从上到下放置。

序列图示例

序列图的组成部分：

  • 对象：用方框框起来的对象名:类名，没有属性和方法等成分。

  • 对象生命线：表示一个对象存在的时间段。

    如上图中对象下方垂直的虚线。

    • 对象可以在交互过程中创建：生命线从接收到构造型create消息开始；
    • 也可以在交互过程中撤销：生命线从接收到构造型destroy消息结束，并且给出一个大$\times$的标记表明生命线的结束。

  • 控制焦点：控制焦点表示一个对象执行一个动作所经历的时间段。

    如上图中对象下方的空表矩形条框。

  • 消息：

    普通的消息用带箭头的实线表示。所有消息的箭头都是指向接收对象。

    • 返回消息：用带箭头的虚线表示。
    • 同步消息（调用消息）：指消息发送给接收对象后，需要等待接收对象返回后才可进行下一步操作。
    • 异步消息：指消息发送给接收对象后，无需等待接收对象返回即可进行下一步操作。

序列图有两个不同于通信图的特性：

  • 序列图有对象生命线；
  • 序列图有控制焦点。

通信图

通信图（Communication Diagram，协作图）强调收发消息的对象的结构组织。通信图强调参加交互的对象的组织。

通信图的组成：

  1. 将参加交互的对象作为图的顶点；
  2. 把连接这些对象的链表示为图的弧；
  3. 用对象发送和接收的消息来修饰这些链。

通信图

通信图有以下成分：

  • 对象：与序列图一样，是用一个方框框起来的对象名:类名。

  • 路径（链接）：用实线表示，可以在链的末端附上一个路径构造型。

    通常仅需显式地表示以下几种链的路径：

    构造型 含义
    <<local>> 局部
    <<parameter>> 参数
    <<global>> 全局
    <<self>> 自身

    不必表示association（关联）。

  • 序号：用来表示消息的时间顺序。是消息前的一个数字前缀，可使用带小数点的号码表示嵌套消息，嵌套可为任意深度。

    如2表示第2个消息，2.1表示嵌套在消息2中的第1个消息。

  • 消息：沿同一个链可以显示许多消息（可能发自不同方向），并且每个消息都有唯一的序号。

通信图有两个不同于序列图的特性：

  • 通信图有路径；
  • 通信图有序号。

状态图

状态图（State Diagram，状态转换图）关注系统的动态视图，强调对象行为的事件顺序。

状态图由以下组成：

  • 状态：指对象的生命周期中某个条件或者状态，是任何可以被观察到的系统行为模式，一个状态代表系统的一种行为模式。

    状态规定了系统内对事件的响应方式。

    系统对事件的响应：

    • 可以是做一个（或一系列）动作；
    • 可以是仅仅改变系统本身的状态；
    • 可以是即改变状态，又做动作。

    状态转换图中定义的状态主要有：

    • 初态（初始状态）：用一个实心圆点表示。一张状态图只能有一个初态。
    • 终态（最终状态）：用一个实心圆点外加一个圆圈表示。一张状态图可以没有终态，也可以有多个。
    • 中间状态。

    状态图中的状态用一个圆角矩形表示，可以用两条水平横线将其分为上中下3个部分：

    1. 上面部分（必须）：状态的名称；
    2. 中间部分（可选）：状态变量的名称和值；
    3. 下面部分（可选）：活动表。

    状态还可分为：

    • 简单状态。

    • 组合状态：含有子状态的状态，这个状态也称为其子状态的超状态。

      子状态：嵌套在另外一个状态中的状态。

  • 转换（迁移）：是两个状态之间的一种关系，表示对象将在源状态中执行一定的动作，并在某个特定事件发生，而且某个特定的警界（监护）条件满足时进入目标状态。

    状态转换用一条带箭头的实线表示。

  • 事件：是在某个特定时刻发生的事情，它是对引起系统做动作或（和）从一个状态转换到另个状态的外界事件的抽象。

    • 事件触发状态转换：状态变迁通常是由事件触发的。状态之间带箭头实线上的事件发生时，状态转换开始（还可称之为状态“点火”或状态被“触发”）。

      这种情况下应在表达状态转换的箭头线上标出触发转换的事件表达式：

      事件说明 [守卫条件] / 动作表达式

      事件说明的语法为：

      事件名 (参数表)

      守卫条件（监护条件）：一个布尔表达式。

      • 当且仅当事件发生且守卫条件为真时，状态转换才发生；
      • 只有守卫条件没有事件说明时，只要守卫条件为真，状态转换就发生。

      动作表达式是一个过程表达式，当状态转换（事件）开始时执行。

    • 自动触发状态转换：如果箭头线上未标明事件，则表示在源状态的内部活动执行完之后自动触发转换。

    状态图中的事件和转换

  • 活动：指状态中的活动表中的活动。

    语法如下：

    事件名 (参数表) /动作表达式

    事件名：可以是任何事件的名称。

    在活动表中经常使用以下3中标准事件：

    事件名 含义
    entry 入口动作，指定进入该状态的动作，立即执行
    exit 出口动作，指定退出该状态的动作，立即执行
    do 内部活动，指定在该状态下的动作，占有有限时间，并可中断地工作

    活动（动作）可以在状态内执行，也可以在状态转换（迁移）时执行。

状态图示例

当状态图对系统、类或用例的动态方面建模时，通常是对反应型对象建模。

活动图

活动图（Activity Diagram）是一种特殊的状态图，它展现了在系统内从一个活动到另一个活动的流程。活动图专注于系统的动态视图，强调对象间的控制流程。

活动图示例

活动图一般包括：

  • 状态：

    活动图的状态也包含初态和终态。其余的状态还可分为：

    • 动作状态：不能被分解，动作不能被中断。
    • 活动状态：能够被进一步分解，可以被中断，其活动由其它的活动图来表示。

  • 流（转换）。

  • 对象。

活动图可以表示：

  • 分支（判断）：分支的流上用[]标记的是监护表达式；
  • （并发）分岔：将一个流分为多个可并发执行的流；
  • （并发）汇合：将分岔出去的多个流合并为同一个流。

当对一个系统的动态方面建模时，有以下几种使用活动图的方式：

  • 对工作流建模；
  • 对操作建模；
  • 对业务的复杂流程建模。

构件图

构件图（Component Diagram，组件图）展现了一组构件之间的组织和依赖。构件图专注于系统的静态实现视图，它与类图相关，通常把构件映射为一个或多个类、接口或协作。

构件图示例

构件图的成分有：

  • 构件：用矩形表示，在矩形右上方有一个小标记。
  • 供接口：用一个圆圈和连接到构件上的实线表示。构件提供接口给其它构件使用。
  • 需接口：用一个半圆和连接到构件上的实线表示。构件使用需接口表示需要调用其它构件提供接口。
  • 依赖：将供接口（圆圈）和虚接口（半圆）连接到一起，表示两个构件通过这个接口相依赖。

部署图

部署图（Deployment Diagram）是用来对面向对象系统的物理方面建模的方法，展现了运行时处理结点以及其中构件（制品）的配置。部署图对系统的静态部署视图进行建模，它与构件图相关。

部署图展现了系统的软件和硬件之间的关系，在实施阶段使用。

部署图示例

<<artifact>>表示制品。

总结

UML图分类：

UML图 静态建模 动态建模 物理建模
类图 $\checkmark$ $\times$ $\times$
对象图 $\checkmark$ $\times$ $\times$
用例图 $\checkmark$ $\times$ $\times$
构件图（组件图) $\checkmark$ $\times$ $\checkmark$
部署图 $\checkmark$ $\times$ $\checkmark$
序列图（顺序图，时序图） $\times$ $\checkmark$ $\times$
通信图（协作图） $\times$ $\checkmark$ $\times$
状态图 $\times$ $\checkmark$ $\times$
活动图 $\times$ $\checkmark$ $\times$

类图成分总结：

名称 图示
类 类图中的类的图形表示
接口 类图接口的图形表示
协作 协作的图形表示
依赖 依赖的图形表示
泛化 泛化的图形表示
关联 关联图形化表示

用例图成分总结：

名称 图示
用例 用例的图形表示
包含关系 用例之间的包含关系
扩展关系 用例之间的扩展关系
泛化关系 用例与用例以及参与者与参与者之间的泛化关系

交互图中，顺序图和通信图是同构的，它们之间可以相互转换。它们的差异如下：

差异
序列图
通信图
强调
消息时间顺序
收发消息的对象的结构组织
不同的特性
  • 有对象生命线：对象存在的时间段
  • 有控制焦点：对象执行动作所经历的时间段
  • 有路径：表示对象之间有交互
  • 有序号：表示消息的时间顺序，可嵌套表示

活动图是一种特殊的状态图，它们的差异如下：

  • 相同点：状态中都有初态和终态。
  • 主要差异：
    • 活动图的转换称为流；
    • 活动图有分支、并发分岔和并发汇合。

以下是UML图的总结：

  • 类图：展现一组对象（类）、接口、协作和它们之间的关系

    类图示例

  • 对象图：展现某一时刻的一组对象以及它们之间的关系，描述了在类图中所建立事物的实例的静态快照

    对象图示例

  • 用例图：展现了一组用例、参与者以及它们之间的关系（包含、扩展、关联和泛化）

    用例图示例

  • 序列图（顺序图，时序图）：描述了以时间顺序组织的对象之间的交互活动，强调消息时间顺序

    序列图示例

  • 通信图（协作图）：强调收发消息的对象的结构组织

    通信图

  • 状态图（状态转换图）：展现了一个状态机，强调对象行为的事件顺序

    状态图示例

  • 活动图：一种特殊的状态图，展现了在系统内从一个活动到另一个活动的流程，强调对象间的控制流程

    活动图示例

  • 构件图（组件图)：展现了一组构件之间的组织和依赖，将构件映射为类、接口或协作

    构件图示例

  • 部署图：对物理建模，展现了运行时处理结点以及其中构件（制品）的配置

    部署图示例

软件工程

沟通路径

沟通图是指项目中人员或部门之间的沟通用一条无向边连接起来，所构成图即为沟通图。沟通图中的路径称为沟通路径。

软件项目中沟通路径$m$的计算公式：

  • 沟通图中无主程序员时：

    $$ m = \sum_{i=1}^{n} i-1 = \cfrac{(n-1)n}{2} $$

  • 沟通图中有主程序员时：

    $$ m = n - 1 $$

Gantt图

Gantt图：一种简单的水平条形图，它以日历为基准描述项目任务。

  • 垂直轴：表示多个不同的任务，每个任务按照左侧任务名称垂直排列。

  • 水平轴：表示日历时间线（如时、天、周、月和年等）。

    每个水平条表示一个任务：

    • 每一水平条的起点：表示该任务的开始时间；
    • 每一水平条的终点：表示该任务的结束时间；
    • 每一水平条的长度：表示完成该任务的持续时间。

    当日历中同一时段存在多个水平条时，表示任务之间的并发。

如图：

Gantt图示例

  • Gantt图优点：

    能清晰地描述：

    • 每个任务的开始时间；
    • 每个任务的结束时间；
    • 任务的进展情况；
    • 各个任务之间的并行性。

  • Gantt图缺点：

    • 不能清晰地反映各任务之间的依赖关系；
    • 难以确定整个项目的关键所在，即不能清晰地确定影响进度的关键任务；
    • 不能反映计划中有潜力的部分。

PERT图

PERT图是一个有向图：

  • 弧：表示任务。

    任务包含以下成分：

    • 完成该任务所需的时间（任务持续时间）。

    • 松弛时间（Slack Time）：表示在不影响整个工期的前提下完成该任务有多少机动余地。

      即松弛时间指当前任务的工期可以推迟的时间。

    空任务：用虚线箭头表示，表示任务间的关系所添加。完成空任务的所需时间为0。

  • 结点：表示事件。

    事件是流入结点的任务的结束，或流出结点的任务的开始。事件表示某个时间点，本身不消耗时间和资源。

    事件包含以下成分：

    • 事件号。
    • 出现该事件的最早时刻：表示在此时刻之前从该事件出发的任务不可能开始。
    • 出现该事件的最迟时刻：表示从该事件出发的任务最迟在此时刻开始，否则整个工程就不能如期完成。

    只有当流入该结点的所有任务都结束时，结点所表示的事件才出现，流出结点的任务才可以开始。

    特殊的事件：

    • 开始事件：没有任何任务流向该事件；
    • 结束事件：没有任务任务从该事件流出。

    一个项目是从开始事件开始到结束事件结束。

PERT图示例

设：

  • $T(e)$：完成任务$e$的所需时间；
  • $T_s(e)$：完成任务$e$的松弛时间；
  • $T_e(v)$：事件$v$的最早时刻；
  • $T_l(v)$：事件$v$的最迟时刻。

PERT图各成分取值（不一定需要满足下面的关系，但是可以用下面的式子推出）：

  • 事件$V_{in}$的最早时刻$T_e(V_{in})$：

    • 只有一个任务流入时，设该任务的流出事件为$V_{out}$，则该任务为$<V_{out}, V_{in}>$：

      $$ T_e(V_{in}) = T_e(V_{out}) + T $$

      这里将$T(<V_{out}, V_{in}>)$简写为了$T$。

      即：该流入任务的流出事件的最早时刻 + 完成该流入任务的所需时间。

    • 多个任务流入时，设与每个任务相对应的流出事件为$V_{out}[ \ i \ ]$，则这些任务为$<V_{out}[ \ i \ ], V_{in}>$：

      $$ T_e(V_{in}) = Max(T_e(V_{out}[ \ i \ ]) + T_i) $$

      这里将$T(<V_{out}[ \ i \ ], V_{in}>)$简写为了$T_i$。

      即流入该事件的每个任务计算出的最早时刻的最大值。

    • 开始事件$V_{start}$：

      $$ T_e(V_{start}) = 0 $$

  • 事件$V_{out}$的最迟时刻$T_l(V_{out})$：

    • 只有一个任务流出时，设该任务的流入事件为$V_{in}$，则该任务为$<V_{out}, V_{in}>$：

      $$ T_l(V_{out}) = T_l(V_{in}) - (T + T_s) $$

      这里将$T_s(<V_{out}, V_{in}>)$简写为$T_s$。

      即：该流出任务的流入事件的最迟时刻 -（该流出任务的所需时间 + 松弛时间）。

      如果松弛时间未知或为0：

      $$ T_l(V_{out}) = T_l(V_{in}) - T $$

    • 多个任务流出时，设与每个任务相对应的流入事件为$V_{in}[ \ i \ ]$，则这些任务为$<V_{out}, V_{in}[ \ i \ ]>$：

      $$ T_l(V_{out}) = Min(T_l(V_{in}[ \ i \ ]) - (T_i + S_i)) $$

      这里把$T(<V_{out}, V_{in}[ \ i \ ]>)$简写为$T_i$，把$T_s(<V_{out}, V_{in}[ \ i \ ]>)$简写为$S_i$。

      即流出该事件的每个任务计算出的最晚时刻的最大值。

      如果松弛时间未知或为0：

      $$ T_l(V_{out}) = Min(T_l(V_{in}[ \ i \ ]) - T_i) $$

    • 结束事件$V_{end}$：

      $$ T_l(V_{end}) = T_e(V_{end}) $$

      即结束事件的最早时刻与最迟时刻相等。

  • 设某任务的流入事件为$V_{in}$，流出事件为$V_{out}$，则该任务$<V_{out}, V_{in}>$的松弛时间$T_s(<V_{out}, V_{in}>)$。

    $$ T_s = T_l(V_{in}) - T - T_e(V_{out}) $$

    即，该任务的流入事件的最迟时刻 - 该任务的所需时间 - 该任务的流出事件的最早时刻

PERT图公式参照图

PERT图的路径：从开始事件到结束事件的一条通路。

PERT图的关键路径：指所有的任务的松弛时间都为0的路径。

关键路径的长度：指结束事件的最早（或最晚）时刻。

PERT图的关键路径示例

关键路径的特点：

  • 所有任务的松弛时间都为0。

  • 每个事件的最早时刻和最迟时刻都是相等的。

  • 所有任务持续时间的和，是PERT图所有路径中最大的，并且与结束事件的最早时刻（或最晚时刻）相等。

    设关键路径中所有事件为$V_i$（$i = 1, 2, \cdots, n$），且该路径下的任务为$<V_j, V_{j+1}>$（$1 \le j \le n-1$）（表示$V_1$是开始事件，$V_2$是$V_1$往下的一个事件，以此类推，$V_n$是结束事件），那么该关键路径结束事件的最早时刻（或最晚时刻）为：

    $$ T_e(V_n) = \sum_{i = 1}^{n-1} T_i $$

    这里$T_i$代表$T(<V_i, V_{i+1}>)$。

最迟时刻的另一种求法（PERT图存在关键路径的情况下）：

已知某PERT图结束事件的最晚时刻（最早时刻），该PERT图中某一条路径（假设该路径没有分支）中所有事件为$V_j$（$j = 1, 2, \cdots, n$），且该路径下的任务为$<V_k, V_{k+1}>$（$1 \le k \le n-1$），该路径下任务的持续时间$T(<V_{k-1}, V_k>)$已知，（即$V_1$是开始事件，按照次序往下，$V_n$是结束事件），计算某一事件的最迟时刻$T_l(V_i)$（$1 \le i < n$）：

$$ T_l(V_i) = T_l(V_n) - \sum_{j = i}^{n - 1} T_j $$

这里$T_j$代表$T(<V_j, V_{j + 1}>)$。

即：结束事件的最晚时刻 - 该事件到结束事件之间所有的任务的持续时间总和。

注意：如果事件$V_i$到结束事件之间存在多条路径，应该选择那条任务持续时间总和最大的路径。

PERT图的优点：

  • 给出了每个任务的开始时间、结束时间和完成该任务所需的时间；
  • 给出了任务之间的关系（依赖关系）。即任务之间的执行顺序。

PERT图不能清晰地描述任务之间的并行情况。

项目活动图

项目活动图是一种有向图（与PERT图十分类似）：

  • 弧：表示活动。弧的权值表示活动的持续时间。

  • 顶点：表示项目里程碑。

    特殊的里程碑：

    • 开始里程碑：没有任何活动指向该里程碑；
    • 结束里程碑：没有任何活动从该里程碑指出。

项目活动图的关键路径：按照PERT图的方法求出松弛时间为0的、从开始里程碑到结束里程碑的路径。

关键路径的长度：为结束里程碑的最早时刻（或最晚时刻）。它可以用来表示项目完成的最少时间。