← 返回刚才阅读的位置

知识卡片

普通读书笔记卡 · 3760.a.1

置换流水车间共享工件顺序

理解等级:中级

置换流水车间调度(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

只换一下顺序,两个指标都变了,所以排列本身就是优化对象。它比一般流水车间多了“各机器顺序一致”的约束,编码和评价都须保持这一顺序。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《智能算法导论》第 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)最小。