知识卡片
有限缓冲容量决定工件阻塞
工件 i 在机器 j(非最后一台)完工后,去向取决于下一台是否空闲以及中间缓冲有多大:
- 无限缓冲(置换流水常见假设):缓冲按先进先出暂存;下一台空闲再继续加工。
- 零缓冲(阻塞型):下一台空闲则立刻过去,否则留在机器 j 上,造成阻塞。
- 有限缓冲:下一台空闲则直接过去;下一台忙且缓冲还有空位则进入缓冲;缓冲已满则留在机器 j 上阻塞。
阻塞会反向占用上游机器,调度评价必须计入跨机器等待。
补充教学示例(非书中数据)。机器 1、容量为 1 的缓冲、机器 2。工件 A 在机器 1 完工时机器 2 正忙、缓冲空,A 进入缓冲;工件 B 再完工时缓冲已满且机器 2 仍忙,B 留在机器 1,机器 1 暂时不能接下一个工件。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 1 0 . 4 . 2 基 于 差 分 进 化 算 法 的 有 限 缓 冲 区 调 度 · 查看原书依据
(1)在置换流水车间调度问题中,假设相邻机器间的缓冲区为无限大,工件在缓冲区内遵循先进先出的原则,当机器j+1空闲时,工件i可直接在机器j+1继续进行加工,否则暂存在缓冲区; (2)在阻塞类型的调度问题中,当机器j+1空闲时,工件i可直接在机器j+1继续进行加工,否则将会停留在机器j上,造成阻塞; (3)当缓冲区有限时,若缓冲区存储已满,工件i停留在机器j上,会造成阻塞;若机器j+1正在执行其他加工,缓冲区还有空间,则工件i进入缓冲区;若机器j+1处于空闲状态,则直接在机器j+1上继续加工。
参考来源
- 位置:《智能算法导论》第 10 章《10.4.2 基于差分进化算法的有限缓冲区调度》(源文件:`_epub-src/EPUB/xhtml/chapter10_0012.xhtml`;式 10-16 至 10-20)
- 结论依据:本节分别给出无限 FIFO 缓冲、无缓冲阻塞,以及有限容量下空闲直达、有空暂存、满载留在上游三种去向。两工件示意为依据该规则补充的教学示例,非书中数据。
- 原始内容:若缓冲区存储已满,工件 i 停留在机器 j 上,会造成阻塞;若机器 j+1正在执行其他加工,缓冲区还有空间,则工件 i 进入缓冲区。