第十一章 第1、2、3、4节 制造业生产作业计划.ppt

三、一般n/m/P/Fmax问题的启发式算法 （一）Palmer 法 1965年，D.S.Palmer 提出按斜度指标排列工件的启发式算法。 工件的斜度指标： k=1, 2, …, m 式中： m—机器数； pik—工件i在Mk上的加工时间。 按照各工件λi不增的顺序排列工件，可得出令人满意的顺序。 例11.7 有一个4/3/F/Fmax问题，其加工时间如下表所示，试用Palmer 法求解。 i 1 2 3 4 pi1 1 2 6 3 pi2 8 4 2 9 pi3 4 5 8 2 解： k=1, 2, 3 λi = -pi1 + pi3 λ1 = -p11 + p13= -1+4=3 λ2 = -p21 + p23= -2+5=3 λ3 = -p31 + p33= -6+8=2 λ4 = -p41 + p43= -3+2=-1 按各工件λi不增的顺序排列工件,得到加工顺序（1,2,3,4）和(2,1,3,4)。 （二）关键工件法 陈荣秋1983年提出的一个启发式算法。步骤如下： （1）计算每个工件的总加工时间Pi=Σpij,找出加工时间最长的工件C, 将其作为关键工件； （2）对余下的工件，若pi1≤pim ,则按pi1不减的顺序排成一个序列Sa; 若pi1pim ,则按pim不增的顺序排成一个序列Sb; （3）顺序（ Sa ,C, Sb ）即为所求顺序。 例11.8 有一个5/3/F/Fmax问题，其加工时间如下表所示，试用关键工 件法求解。 i 1 2 3 4 5 pi1 1 2 6 3 4 pi2 8 4 2 9 8 pi3 4 5 8 2 3 pi 13 11 16 14 15 （1,2,3,5,4） （三）CDS法 Campbell,Dudek,Smith三人提出了一个启发式算法，简称CDS法。 例：对例11-7用CDS法求解。 i 1 2 3 4 l=1 pi1 1 2 6 3 pi3 4 5 8 2 l=2 pi1 + pi2 9 6 8 12 pi2 + pi3 12 9 10 11 当l=1时，按Johnson算法得到加工顺序（1,2,3,4）,相应的Fmax=28； 当l=2时，按Johnson算法得到加工顺序（2,3,1,4）,相应的Fmax=29； 最优顺序为（1,2,3,4）。 最长流程时间的计算 工件代号i 1 2 3 4 Pi1 1 2 6 3 Pi2 8 4 2 9 Pi3 4 5 8 2 1 3 9 12 9 13 15 24 13 18 26 28 （1）顺序移动方式 概念：指一批零件或产品在前道工序全部加工完成后， 整批转移到后道工序加工的移动方式 例: 加工批量n＝4，工序数m＝4，各道工序时间t1＝10min t2=5min t3=15min t4=10min 其顺序移动方式示意图如下： 10 5 15 工序4 工序3 工序2 工序1 t 20 40 60 80 100 120 140 160 10 （一）、零件在加工过程中的移动方式 二、生产过程的时间组织 生产周期计算公式： n——批量 m——工序数 ti ——i工序单件工时 T顺——顺序移动方式生产周期 例： T顺＝4×（10＋5＋15＋10）=160 (2) 平行移动方式 概念：指每个产品或零件在上道工序加工完后，立即 转到下道工序加工，使各个零件或产品在各道 工序上的加工平行地进行 生产周期计算公式： t长：工序时间最长的工序时间 例： T平 =（10＋5＋15＋10）＋（4－1）×15 ＝40＋45＝85 t 20 40