1、第9章制造作业计划与控制 第一节第一节 排序问题的基本概念排序问题的基本概念 第二节第二节 流水作业排序问题流水作业排序问题 第三节第三节 单件作业排序问题单件作业排序问题 第四节第四节 生产作业控制生产作业控制 根据排序规则对每一个根据排序规则对每一个到到 达的工件安排作业顺序达的工件安排作业顺序 工作地工作地 工件排工件排 队等待队等待 加工加工 来自上游来自上游 工作地的工作地的 工件工件 加工完毕的加工完毕的 工件流向下工件流向下 一工作地一工作地 排序的概念 排序的概念 名词术语(略) 排序问题的分类 参数表示法: 参数表示法: 第二节 流水作业排序问题 一、最长流程时间Fmax的计
2、算 表1加工时间矩阵 - i 1 2 3 4 5 6 P i1 4 2 3 1 4 2 P i2 4 5 6 7 4 5 P i3 5 8 7 5 5 5 P i4 4 2 4 3 3 1 表2顺序S下的加工时间矩阵 i 6 1 5 2 4 3 i1P 2 2 4 6 4 10 2 12 1 13 3 16 i2P 5 7 411 4 15 520 727 633 Pi3 5 12 517 522 830 5 35 742 Pi4 1 13 421 325 232 338 4 46 Pi1P 一、最长流程时间Fmax的计算 表表3 3顺序顺序S S下的加工时间矩阵下的加工时间矩阵 i 1 2
3、3 4 5 6 i1P 3 3 3 6 4 10 212 113 3 16 i2P 2 5 511 4 15 318 725 631 Pi3 5 10 415 5 20 7 27 5 32 436 Pi4 1 11 217 323 229 335 137 Pi1P 课堂作业：求课堂作业：求Fmax. 二、n/2/F/Fmax问题的最优算法 将零件2排第1位 2 将零件3排第6位2 3 将零件5排第2位2 5 3 将零件6排第3位2 5 6 3 将零件4排第5位2 5 6 4 3 将零件1排第4位2 5 61 4 3 最优加工顺序为S=（2，5，6，1，4，3）。 最优顺序下的 F max=28
4、 表表11-3加工时间矩阵加工时间矩阵 i 1 2 3 4 5 6 b i 7 2 2 4 7 4 5 1 8 5 3 4a i （二）算法步骤的改进 表11 -4 改进算法 改进算法 i 1 2 3 4 5 6 ai 5 1 8 5 3 4 bi 7 2 2 4 7 4 i 1 3 ai 5 8 bi 2 1 2 5 3 7 6 4 4 7 2 4 4 5 4 三、求一般n/m/P/ Fmax问题近优解 (Near optimal solution)的启发式算法 1、Palmer法 m 1k iki P2/ ) 1m(k 例：有一个4/3/P/ Fmax 问题，其加工时间如下 表所示，用Pa
5、lmer法求解。 表11 -5 加工时间矩阵 i 1 2 3 4 Pi1 1 2 6 3 Pi2 8 4 2 9 Pi3 4 5 8 2 =(1-2) Pi1+(2-2) Pi2+(3-2) Pi3 =- P i1 + P i3 解解 K = 1 ) , 3 ,2, 1( ,2/)1( 1 kPmk m k iki m k iki Pk 1 2/ ) 13( m k iki Pk 1 2 1 = - P 11 + P 13= -1+4 = 3 2 = -P21 + P23= -2 + 5= 3 3 =- P31 + P33 = -6 + 8 = 2 4 =-P 41+P43 = -3 + 2
6、= -1 按i不增的顺序排列，得到加工顺序 （1，2，3，4）和（2，1，3，4）， 两者均为最优顺序，Fmax=28。 i =- P i1 + P i3 1 2.5 m iik k kP 课堂作业：用课堂作业：用Palmer法求解表中法求解表中4/4/P/Fmax问题的最优解。问题的最优解。 i =- 1.5P i1 -0.5 P i2+ 0.5P i3+1.5P i4 解： 1= - 1.51 -0.5 5+ 0.54 +1.5 6=7 2= - 1.59 -0.5 7+ 0.56 +1.5 2=-11 3= - 1.55 -0.5 6+ 0.53 +1.5 3=-4.5 4= - 1.5
7、4 -0.5 3+ 0.55+1.5 7=5.5 按按i不增排列，不增排列，1,4,3,2 Fmax=34。 m 1k iki P2/)1m(k 表11 -5 加工时间矩阵 i 1 2 3 4 5 Pi1 1 2 6 3 4 Pi2 8 4 2 9 3 Pi3 4 5 8 2 3 表11-6用关键零件法求解 i2 P i3 p i i 1 2 3 4 5 P i1 1 2 6 3 4 P 8 4 2 9 3 4 5 8 2 3 13 11 16 14 10 1、找出最长时间 2、 1，235 ，4 1、找出关键零件：是2号，时间为24 2、 流程时间：38 3、CDS法（自学） L k ik
8、p 1 m Lmk ik p 1 L表示多少个加工工序. 表示前面L个工序的 时间和， m Lmk ik p 1 表示后面L个工序的时间和。 L k ik p 1 CDS法可以总结为：法可以总结为： L=1时，求第时，求第1道和最后一道工序的加工时间矩阵道和最后一道工序的加工时间矩阵 L=2时，求前时，求前2道和后道和后2道工序的加工时间和的矩阵道工序的加工时间和的矩阵 L=3时，求前时，求前3道和后道和后3道工序的加工时间和的矩阵道工序的加工时间和的矩阵 L=4时，求前时，求前4道和后道和后4道工序的加工时间和的矩阵道工序的加工时间和的矩阵 L=m-1，求前，求前m-1道和后道和后m-1道工
9、序的加工时间和道工序的加工时间和 的矩阵的矩阵 如：用CDS求机器数M为3时的加工顺序。 首先，计算L=1时的加工时间， 和 即Pi1和Pi3 L kk ikik pp 1 1 1 3 31 3 113k ik m Lmkk ikik ppp 再计算L=2时的加工时间， 和21 1 2 1 ii L kk ikik pppp 32 3 21 3 213 ii k ik m Lmkk ikik ppppp 表表11-7用用CDS法求解法求解 i 1 2 3 4 Pi1 1 2 6 3 L=1 Pi3 4 5 8 2 Pi1+Pi2 9 6 8 12 L=2 Pi2+Pi3 12 9 10 11
10、四、四、相同相同零件、不同移动方式下加工零件、不同移动方式下加工 周期的计算周期的计算 零件在加工过程中可以采用三种典型的零件在加工过程中可以采用三种典型的 移动方式：移动方式： 顺序移动顺序移动 平行移动平行移动 平行顺序移动平行顺序移动 n = n加工批量；加工批量； m工序数目；工序数目； ti工件在第工件在第i工序的单工序的单 件工时；件工时； 四、相同零件、不同移动方式下加工 周期的计算 一批零件在上道工序全部加工完毕后,才整批转移 到下道工序加工。 n加工批量；加工批量； m工序数目；工序数目； ti工件在第工件在第i工序的单件工时；工序的单件工时； 工序工序 M1 M2 M3 M
11、4 T顺序 顺序 t2 t1 t3 t4 时间时间 1、顺序移动方式: 工序数。批量；其中 一般式： 分钟）（ 代入例中数字： mn tnT T tnntntntntT m i i i i : (16010155104 1 4 14321 每个零件在前道工序加工完毕后，立即转移到后 道工序去继续加工，形成前后工序交叉作业。 L m i i tntT)1( 1 平行 工序工序 T平行 平行 时间时间 M1 M2 M3 M4 2、平行移动方式 t1 t2 t3 t4 最长者。所有工序中，单件时间 一般式： 分钟）（ 代入例中数字： 周期计算：平行移动方式下的加工 长 长 : ) 1( )(8515
12、31015510 ) 1( 1 3 4 14321 t tntT T tnttntttT m i i i i 要求每道工序连续进行，但又要求各道工序尽可能 平行地加工。 1 11 ) 1( m i is m i i tntnT平顺 工序工序 M1 M2 M3 M4 T平顺 平顺 t2 t1 t3 t4 时间时间 3、平行顺序移动方式、平行顺序移动方式 工序工序 M1 M2 M3 M4 T平顺 平顺 t2 t1 t3 t4 时间时间 第第1种情况：种情况：ti ti+1 考虑平行性，实现交叉作业考虑平行性，实现交叉作业 按平行移动方式的原则加工，即工件加工完成后立刻转移到下一个工序，此处，按平行
13、移动方式的原则加工，即工件加工完成后立刻转移到下一个工序，此处， 第第2个工序的第个工序的第1个工件加工完成后立刻转移到第个工件加工完成后立刻转移到第3个工序进行加工。个工序进行加工。 3、平行顺序移动方式、平行顺序移动方式 工序工序 M1 M2 M3 M4 T平顺 平顺 t2 t1 t3 时间时间 t 4 第第2种情况：种情况：ti ti+1 考虑设备加工的连续性考虑设备加工的连续性 第第1个工序的所有工件加工完成的时刻为基准，向前推（个工序的所有工件加工完成的时刻为基准，向前推（n-1）个）个t2时间，作为时间，作为 第第2个工序的开始时间。即从红线开始向前推个工序的开始时间。即从红线开始
14、向前推3个作为第个作为第2个工序的开始时间。个工序的开始时间。 3、平行顺序移动方式、平行顺序移动方式 x T=nt1+t2+x+t4 X=nt3-(n-1)t2 ),min() 1( 1 1 11 j m i j m i i ttntnT平顺 Min(tj,tj+1)前后相邻两工序中前后相邻两工序中 单件工时之较小者单件工时之较小者 T=4(10+5+15+10)-(4-1) (5+5+10)=100分钟 ),min() 1( 1 1 11 j m i j m i i ttntnT平顺 工序工序 M1 M2 M3 M4 M5 T平顺 平顺 t2 t1 t3 时间时间 t4 加工周期的计算加工
15、周期的计算 Min(tj,tj+1)前后相邻两前后相邻两 工序中单件工时之工序中单件工时之 较小者较小者 3、平行顺序移动方式、平行顺序移动方式 零件三种移动方式的比较 第三节第三节 单件作业计划问题单件作业计划问题 max /FGmn 一、任务分配：匈牙利算法流程一、任务分配：匈牙利算法流程 例题 1、每行所有元素减去该 行最小元素。 2、每列所有元素减去该 列最小元素。 3、划出能覆盖尽可能多的0元素 的直线，如果线条数等于矩阵列 数，则找到最优解。否则继续。 4、没被线条穿过的元素减 去这些元素中的最小数。 并将这个最小数加到直线交 叉的元素上。然后重复3、4 5、从仅有一个0元素的行
16、或列开始，最后使每行和 每列都有一个0元素。 0元素对应的就是最优分 配方案。 结果 用（i，j，k）表示工件i 的第j道工序在机器k上进行。 i表示工件代号 j表示工序号 k表示完成任务的机器代号。如加工描述矩阵D。 232122312 231321111 ， ， D 三、优先派工法则 四、一般n/m/G/Fmax问题的算法 作业计划构成分类 2、能动作业计划的构成步骤: 例题： 232122312 231321111 ， ， D 543 142 T 232122312 231321111 ， ， D 543 142 T 试构成一个能动作业计划。 2,3,2M2131382,3,26 1,3
17、,2M288 12 7 7 1,3,2 2,3,2 5 2,2,1M1 78 7 7 3 1,3,2 2,2,1 4 1,2,3M3 M1 77 7 3 3 1,2,3 2,2,1 3 2,1,3M336 3 2 0 1,2,3 2,1,3 2 1,1,1M122 3 0 0 1,1,1 2.1.3 1 QjM*T*TkTkQtt 解：解：Tk最早开工时间；最早开工时间；Tk=最早完成时间；最早完成时间；T*=最早完工时间中的最小者最早完工时间中的最小者 1,1,1 1,2,3 1,3,2 D 2,1,3 2,2,1 2,3,2 2 4 1 T 3 4 5 最优作业计划为：最优作业计划为： 1
18、,1,1 2,1,3 1,2,3 2,2,1 1,3,2 2,3,2 机 器 M1 M2 M3 0时间 1,1,12,2,1 2 3 7 2,3,2 1,3,2 7 8 13 2,1,3 1,2,3 3 7 3、无延迟作业计划的构成步骤: 1,3,2M21213121,3,26 2,3,2 M2 M2 7 7 8 12 7 7 1,3,2 2,3,2 5 2,2,1M13 8 7 7 3 1,3,2 2,2,1 4 1,2,3M3 M1 3 3 7 7 3 3 1,2,3 2,2,1 3 2,1,3M30 6 3 2 0 1,2,3 2,1,3 2 1,1,1M1 M3 0 0 2 3 0 0
19、 1,1,1 2.1.3 1 QjM*T*TkTkQtt 解：解：Tk最早开工时间；最早开工时间；Tk=最早完成时间；最早完成时间；T*=最早开工时间中的最小者最早开工时间中的最小者 最优作业计划为：最优作业计划为： 1,1,1 2,1,3 1,2,3 2,2,1 2,3,2 1,3,2 2,3,2 1,3,2 7 12 13 机 器 M1 M2 M3 0时间 1,1,12,2,1 2 3 7 2,1,3 1,2,3 3 7 三类启发式算法 2、用Palmer法求解表中4/4/P/Fmax问题的最优解。 i1234 Pi1 Pi2 Pi3 Pi4 1 5 4 6 9 7 6 2 5 6 3 3 4 3 5 7 3、用关键零件法求表中5/4/P/Fmax问题的最优解。 i12345 Pi1 Pi2 Pi3 Pi4 1 5 4 6 9 7 6 2 5 6 3 3 4 3 5 7 6 2 6 2
