华中科技大学--制造业生产作业计划(编辑修改稿)

华中科技大学--制造业生产作业计划(编辑修改稿)内容摘要：

② 将所有 ai＞ bi的零件按 bi值不增的顺序排成一个序列 B。  ③ 将 A放到 B之前，就构成了最优加工顺序  序列 A为 (2， 5， 6， 1)，序列 B为 (4， 3)，构成最优顺序为 (2， 5， 6， 1， 4， 3)，与Johnson算法结果一致。 表11 4 改进算法 i 1 2 3 4 5 6 ai 5 1 8 5 3 4 bi 7 2 2 4 7 4 i 2 5 6 1 4 3 ai 1 3 4 5 5 8 bi 2 7 4 7 4 2  Johnson法则只是一个充分条件 ， 不是必要条件。 不符合这个法则的加工顺序 ，也可能是最优顺序。 如对例 112顺序 (2， 5， 6， 4， 1， 3)不符合 Johnson法则 ，但它也是一个最优顺序  对于 3台机器的流水车间排序问题 ， 只有几种特殊类型的问题找到了有效算法。  对于一般的流水车间排列排序问题 ， 可以用分支定界法。 求一般 n/m/P/ Fmax问题近优解 (Near optimal solution)的启发式算法  关键零件法  CDS法  关键零件法求近优解举例 表 11 5 加工时间矩阵 i 1 2 3 4 P i1 1 2 6 3 P i2 8 4 2 9 P i3 4 5 8 2 表 11 － 6 用关键零件法求解 i 1 2 3 4 P i1 1 2 6 3 P i2 8 4 2 9 P i3 4 5 8 2 p i 13 11 16 14 CDS法  CampbellDudekSmith 三人提出了一个启发式算法 ,简称 CDS法。 他们把Johnson算法用于一般的 n/m/P/Fmax问题，得到 (ｍ－ 1)个加工顺序，取其中优者  当ｌ＝ 1时，按 Johnson算法得到加工顺序 (1，2， 3， 4)； 当ｌ＝ 2时，得到加工顺序 (2， 3， 1， 4)。 对于顺序 (2， 3， 1， 4)，相应的Fmax＝ 29。 所以，取顺序 (1， 2， 3， 4)。 我们已经知道，这就是最优顺序。 表11－7 用CDS法求解。