知识卡片
资源与时序约束最小工期
资源受限项目调度问题(RCPSP)在项目活动的先后关系之外,还给可用资源设上限;目标是在两类约束都满足时安排任务,使项目工期尽可能短。只满足活动先后顺序仍可能超用资源,只满足资源上限也可能违反依赖关系。
示例(补充演示,非书中数据):工人上限 3 人;A、B 各需 2 人、3 天;C 需 1 人、2 天,且必须在 A 完成后开始。
| 方案 | A | B | C | 工期 | 是否可行 |
|---|---|---|---|---|---|
| 忽略资源上限 | 第 0–3 天 | 第 0–3 天 | 第 3–5 天 | 5 天 | 否:前 3 天需 4 人 |
| 两类约束都满足 | 第 0–3 天 | 第 3–6 天 | 第 3–5 天 | 6 天 | 是:任何时刻 ≤3 人 |
建模、解码和验收都应分别检查资源可行性、时序可行性与工期目标。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 9 . 4 . 2 基 于 分 布 估 计 算 法 的 资 源 受 限 项 目 调 度 · 查看原书依据
9.4.2 基于分布估计算法的资源受限项目调度 9.4.2 基于分布估计算法的资源受限项目调度 资源受限项目调度问题(Resource-Constrained Project Scheduling Problems,RCPSP)是调度问题的一个重要分支,在项目调度的基础上,规定了资源上限作为约束条件。另外,由于技术上或其他因素导致的任务之间的时序约束也是该问题的约束条件之一。RCPSP的优化目标是在满足资源上限约束和任务之间时序约束的条件下,调度各个任务,得到最短工期的调度方案。
参考来源
- 位置:《智能算法导论》第 9 章《9.4.2 基于分布估计算法的资源受限项目调度》(源文件:`_epub-src/EPUB/xhtml/chapter9_0008.xhtml`)
- 结论依据:原文将资源上限和任务时序关系都列为约束,并把满足二者时的最短工期作为优化目标。A、B、C 三任务的排程表为依据 RCPSP 定义补充的教学示例,非书中数据。
- 原始内容:在项目调度的基础上,规定了资源上限作为约束条件。另外,由于技术上或其他因素导致的任务之间的时序约束也是该问题的约束条件之一。