Rust 的优先级网络分析

优先级网络

优先级网络（或优先级图法）是一种构建有向图中指定依赖关系的连通活动的方法。通过指定每个任务的最低、期望和最高持续时间，可以分析网络以找到位于关键路径上的活动，并且必须按时完成以避免延迟整个网络。

用法

给定以下优先级网络

                       ┌──────────┐
     ┌────────────────►│Document:4├─────────────────┐
     │                 └──────────┘                 │
     │                                              ▼
┌────┴───┐       ┌─────────┐     ┌──────┐      ┌────────┐
│Design:5├──────►│Develop:6├────►│Test:4├─────►│Deploy:1│
└────────┘       └──────┬──┘     └──────┘      └────────┘
                        │                           ▲
                        │         ┌───────┐         │
                        └────────►│Train:3├─────────┘
                                  └───────┘

使用 precedence-net，我们可以用以下代码建模它

use precedence_net::{Network, Result};

fn main() -> Result<()> {
  let mut network_builder = Network::builder();

  network_builder.add_activity("Design", 5.0)?;
  network_builder.add_activity("Develop", 6.0)?;
  network_builder.add_activity("Document", 4.0)?;
  network_builder.add_activity("Deploy", 1.0)?;
  network_builder.add_activity("Train", 3.0)?;
  network_builder.add_activity("Test", 4.0)?;

  network_builder.connect("Design", "Develop")?;
  network_builder.connect("Design", "Document")?;
  network_builder.connect("Develop", "Test")?;
  network_builder.connect("Develop", "Train")?;
  network_builder.connect("Test", "Deploy")?;
  network_builder.connect("Train", "Deploy")?;
  network_builder.connect("Document", "Deploy")?;

  let network = Network::try_from(network_builder)?;

  println!("Activity | Earliest Start | Earliest Finish | Latest Start | Latest Finish | Total Float | Free Float | Critical Path");
  println!("---------------------------------------------------------------------------------------------------------------------");
  for activity in network.activities()? {
    println!(
      "{:^8} | {:>14} | {:>15} | {:>12} | {:>13} | {:>11} | {:>10} | {:^14}",
      activity,
      network.earliest_start(activity)?,
      network.earliest_finish(activity)?,
      network.latest_start(activity)?,
      network.latest_finish(activity)?,
      network.total_float(activity)?,
      network.free_float(activity)?,
      network.on_critical_path(activity)?,
    );
  }
  Ok(())
}

将生成以下输出

Activity | Earliest Start | Earliest Finish | Latest Start | Latest Finish | Total Float | Free Float | Critical Path
---------------------------------------------------------------------------------------------------------------------
 Design  |              0 |               5 |            0 |             5 |           0 |          0 |      true
Develop  |              5 |              11 |            5 |            11 |           0 |          0 |      true
Document |              5 |               9 |           11 |            15 |           6 |          6 |     false
  Test   |             11 |              15 |           11 |            15 |           0 |          0 |      true
 Train   |             11 |              14 |           12 |            15 |           1 |          1 |     false
 Deploy  |             15 |              16 |           15 |            16 |           0 |          0 |      true

性能

使用 Criterion.rs，以下活动在一个包含 62,500 个活动的优先级网络上进行了基准测试，在拥有 16GB RAM 的 Intel Core i7 上。

• 向网络添加活动：78ms
• 从网络构建器创建网络：239ms
• 从网络创建网络构建器：44ms
• 检索关键路径：1.1ms

待实现

• 循环路由检查
• 序列化和反序列化
• 更新活动

许可证

版权所有 2022 Farrel Lifson

在 MIT 许可证下发布。有关详细信息，请参阅 LICENSE-MIT。