知识卡片

普通读书笔记卡 · 3758.b

时间窗与稀疏解码安排任务

理解等级:高级

RCPSP-TW 为各任务增加允许开始的时间窗,以表达劳动力短缺等现实限制;有效解要同时满足资源、任务时序和时间窗三类约束。其稀疏解码(SD)先构造松散基准调度,再为任务附加时间窗,将任务列表转成满足时间窗的稀疏调度。

示例(补充教学示例,非书中数据):任务 A 工期 2,时间窗要求开始时刻落在 [3,5]。若无时间窗,A 可在时刻 0 开工;加上窗口后最早也只能从 3 开始,安排在时间轴上被“撑开”,这就是相对更稀疏的调度。

原书报告时间窗宽度会明显影响解质,且其测试中较窄时间窗得到较优解;这是特定模型和数据集上的报告,不能泛化为“约束越严越好”。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 9 . 4 . 2 基 于 分 布 估 计 算 法 的 资 源 受 限 项 目 调 度 · 查看原书依据

      在实际生产生活中,存在人力匮乏、资源短缺等因素的影响,项目调度中的每项任务开始时间也许只能在某段时间窗内,因此RCPSP-TW模型比理想的RCPSP更贴近于现实情况。在设计RCPSP-TW过程中,首先建立一个松散的基准调度方案,然后向该方案的每个任务添加时间窗,产生时间窗约束。RCPSP-TW模型的有效解必须满足以下3个约束:资源约束、时序约束以及时间窗约束。

    参考来源

    - 位置:《智能算法导论》第 9 章《9.4.2 基于分布估计算法的资源受限项目调度》(源文件:`_epub-src/EPUB/xhtml/chapter9_0008.xhtml`) - 结论依据:原文指出任务开始时间可能受时间窗限制,明确列出资源、时序、时间窗三项约束,并把 SD 描述为由任务列表生成稀疏调度;关于窗宽的方向限定为该节所述实验。任务 A 的 [3,5] 窗口为依据时间窗与稀疏安排含义补充的教学示例,非书中数据。 - 原始内容:RCPSP-TW模型比理想的RCPSP更贴近于现实情况。在设计RCPSP-TW过程中,首先建立一个松散的基准调度方案,然后向该方案的每个任务添加时间窗,产生时间窗约束。