知识卡片
置换流水车间共享工件顺序
置换流水车间调度(PFSP)让 n 个工件依次经过 m 台机器,所有机器按同一个工件排列加工,每台机器同一时刻只加工一个工件。于是整个决策只剩“工件排成什么顺序”,解就是一个排列。
常用两个目标:
- 完工时间(makespan):最后一个工件在最后一台机器上完工的时刻,越小越好。
- 总流经时间:各工件完工时刻之和,越小越好。
示例(补充演算):2 个工件、2 台机器,J1 在 M1、M2 上各需 3、2 个时间单位,J2 各需 1、4。工件在 M2 上开工,要等它在 M1 上完工且 M2 空闲。
| 顺序 | M1 上完工 | M2 上完工 | 完工时间 | 总流经时间 |
|---|---|---|---|---|
| J1→J2 | J1=3,J2=4 | J1=5,J2=9 | 9 | 14 |
| J2→J1 | J2=1,J1=4 | J2=5,J1=7 | 7 | 12 |
只换一下顺序,两个指标都变了,所以排列本身就是优化对象。它比一般流水车间多了“各机器顺序一致”的约束,编码和评价都须保持这一顺序。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 1 0 . 4 . 1 基 于 差 分 进 化 算 法 的 置 换 流 水 线 调 度 · 查看原书依据
PFSP的优化目标是求出n个工件在每台机器上的加工顺序,使得某个性能指标达到最优,最常用的指标是完工时间(make span)最小,其次是总流经时间(total flow time)最小[39]。
参考来源
- 位置:《智能算法导论》第 10 章《10.4.1 基于差分进化算法的置换流水线调度》(源文件:`_epub-src/EPUB/xhtml/chapter10_0011.xhtml`;式 10-15,`_epub-src/EPUB/images/image_263.svg`)
- 结论依据:原文要求各机器加工顺序相同、每台机器一次只能加工一个工件,并把完工时间和总流经时间列为常用目标。2 工件 2 机器的演算为依据原书定义补充的教学示例,非书中数据。
- 原始内容:每台机器加工工件的顺序相同,n个工件在各机器上的加工顺序也相同,每台机器一次只能加工一个工件。
- 原始内容:最常用的指标是完工时间(make span)最小,其次是总流经时间(total flow time)最小。