车间生产作业排序(ppt38)-生产运作(编辑修改稿)

车间生产作业排序(ppt38)-生产运作(编辑修改稿)内容摘要：

Pi最长的工件 ， 将之作为关键工件 C。 • 对其余工件 ， 若 Pi1≤ Pim ， 则按 Pi1由小到大排成序列 SA。 若 Pi1 Pim ， 则按 Pim由大到小排成序列 SB。 • 顺序 （ SA， C， SB） 即为近优解。 华中科技大学管理学院 四、一般 n/m/P/ Fmax问题的启发式算法 用关键工件法求解i 1 2 3 4P i1 1 2 6 3P i2 8 4 2 9P i3 4 5 8 2p i 1 3 1 1 1 6 1 4得到的加工顺序为 (1， 2， 3， 4) 华中科技大学管理学院 四、一般 n/m/P/ Fmax问题的启发式算法 CDS法 ： • CDS法 是 Johnson算法 的扩展方法，从 M1个排序中找出近优解。 加工顺序 A 加工时间 B 加工时间1 t1tm2 t1+t2tm 1+tm3 t1+t2+t3tm 2+tm1+tm„ „„ „„m1 t1+t2+ „+tm 1t2+ „ +tm1+tm华中科技大学管理学院 四、一般 n/m/P/ Fmax问题的启发式算法 • L＝ 1，按 Johnson算法得到加工顺序 (1， 2， 3， 4)， Fmax＝ 28 • L＝ 2，按 Johnson算法得到加工顺序 (2， 3， 1， 4)， Fmax＝ 29 • 取顺序 (1， 2， 3， 4）为最优顺序。 用 CDS 法求解i 1 2 3 4P i1 1 2 6 3L = 1P i3 4 5 8 2P i1 +p i2 9 6 8 12L = 2P i2 +p i3 12 9 10 11华中科技大学管理学院 五、单件车间排序问题（ n/m/G/Fmax） 问题描述 • (i， j， k)：表示工件 i的第 j道工序是在机器 k上进行。 • 加工描述矩阵 D：每一行描述一个工件的加工，每一列的工序序号相同。 D= 1,1,1 1,2,3 1,3,2 2,1,3 2,2,1 2,3,2 华中科技大学管理学院 五、单件车间排序问题（ n/m/G/Fmax） • 加工时间矩阵 T：与 D相对应。 D= 1,1,1 1,2,3 1,3,2 2,1,3 2,2,1 2,3,2 T= 4 6 3 5 7 4 华中科技大学管理学院 五、单件车间排序问题（ n/m/G/Fmax） • 加工顺序矩阵 S：每一行与机器相对应，每一列与工件相对应。 D= 1,1,1 1,2,3 1,3,2 2,1,3 2,2,1 2,3,2 S= 1,1,1 2,2,1 1,3,2 2,3,2 2,1。