1、2022-11-26生产作业计划与控制生产作业计划与控制生产作业计划与控制2022-11-26生产作业计划与控制2022-11-26生产作业计划与控制单件作业排序问题单件作业排序问题4排序问题的基本概念排序问题的基本概念1单台设备的排序问题单台设备的排序问题235流水型作业排序问题流水型作业排序问题生产作业控制生产作业控制2022-11-26生产作业计划与控制1、排序的概念与作用排序的概念与作用u作业排序：生产作业排序就是指对于等候某个作业排序：生产作业排序就是指对于等候某个设备或工作中心加工的多个任务，确定这些任设备或工作中心加工的多个任务，确定这些任务加工的先后次序。务加工的先后次序。u生
2、产作业计划：不仅包括确定零件的加工顺序，生产作业计划：不仅包括确定零件的加工顺序，而且还包括确定设备加工每一个零件的开始时而且还包括确定设备加工每一个零件的开始时间和完工时间。间和完工时间。u作用：作用：提高设备或工作中心的效率提高设备或工作中心的效率 减少在制品占用量减少在制品占用量 缩短生产周期缩短生产周期 保证按期交货保证按期交货2022-11-26生产作业计划与控制单目标排序单目标排序多目标排序多目标排序2022-11-26生产作业计划与控制排序的目标函数排序的目标函数（1 1）流程时间：任务在车间）流程时间：任务在车间的停留时间的停留时间FiFi总流程时间：总流程时间：FiFi最大流
3、程时间：最大流程时间：Fmax=maxFmax=maxFiFi平均流程时间：平均流程时间：Fi/nFi/n（2 2）等待时间）等待时间总等待时间总等待时间平均等待时间平均等待时间（3 3）延期量：交货期拖延的）延期量：交货期拖延的时间（时间（D D）最大延期量最大延期量:Dmax=max:Dmax=maxDiDi总延期量：总延期量：DiDi（4 4）加工周期）加工周期已知条件已知条件u零件加工工艺过程零件加工工艺过程u作业时间作业时间ti ti u交货期交货期 CiCi 时间 J1 J2 J3 J4 C1 C2 C3 C4t1 t2 t3 t4F1F2F3F42022-11-26生产作业计划与
4、控制例：例：5个工件经过个工件经过4台设备加工，目标是使加工周台设备加工，目标是使加工周期最短的流水型作业排序可以表示为：期最短的流水型作业排序可以表示为：5/4/F/Fmax2022-11-26生产作业计划与控制第二节第二节 单台设备加工排序问题单台设备加工排序问题加工周期加工周期=4+8+2+5+9=28目标函数？目标函数？2022-11-26生产作业计划与控制排序：排序：一一一一一一一一一一一一 2、SPT法法（2022-11-26生产作业计划与控制解：列表如下解：列表如下 加工顺序加工顺序 1 2 3 4 5 6 零件号零件号 作业时间作业时间 2 3 4 5 8 9 流程时间流程时间
5、 2 5 9 14 22 31 等待时间等待时间 0 2 5 9 14 22 预定交货期预定交货期 8 13 24 6 23 32 交货延期交货延期 0 0 0 8 0 02022-11-26生产作业计划与控制 加工顺序加工顺序 1 2 3 4 5 6 零件号零件号 作业时间作业时间 2 3 4 5 8 9 流程时间流程时间 2 5 9 14 22 31 等待时间等待时间 0 2 5 9 14 22 预定交货期预定交货期 8 13 24 6 23 32 交货延期交货延期 0 0 0 8 0 02022-11-26生产作业计划与控制3、EDD法（法（最早交期最早交期(EDD)排队策略）排队策略）
6、排序：排序：一一一一 一一 一一 一一 例题例题1:已知条件如表所示已知条件如表所示,用用EDD法排序，并求平均法排序，并求平均流程时间流程时间,平均等待时间，最大交货延期平均等待时间，最大交货延期 2022-11-26生产作业计划与控制答：最大流程时间：答：最大流程时间：31 最大等待时间：最大等待时间：22 平均流程时间平均流程时间=(5+7+10+18+22+31)615.5 平均等待时间平均等待时间=(0+5+7+10+18+22)/6=10.33 最大交货延期：最大交货延期：0 总交货延期：总交货延期：(0+0+0+0+0+0)=0缺点：缺点：平均流程时间较长平均流程时间较长 优点：
7、优点：最大交货延期最小最大交货延期最小 加工顺序加工顺序 1 2 3 4 5 6 零件号零件号 作业时间作业时间 5 2 3 8 4 9 流程时间流程时间 5 7 10 18 22 31 等待时间等待时间 0 5 7 10 18 22 预定交货期预定交货期 6 8 13 23 24 32 交货延期交货延期 0 0 0 0 0 02022-11-26生产作业计划与控制课堂练习：课堂练习：用用SPT法和法和EDD法对下列问题排序，法对下列问题排序，并求最大并求最大 流程时间、平均流程时间、最大流程时间、平均流程时间、最大交货延期和总交货延期。交货延期和总交货延期。2022-11-26生产作业计划与
8、控制第三节第三节 流水型作业排序问题流水型作业排序问题问题的特点问题的特点:零件的加工路线相同零件的加工路线相同三台设备三台设备流水型排序问题流水型排序问题车床车床1 1到达系统工到达系统工件的集合件的集合离开系统离开系统（机器）（机器）J J1 1J J2 2J J3 3J Jn n铣床铣床2 2磨床磨床m m2022-11-26生产作业计划与控制设备设备 零件零件(1)车床车床 ti1681237(2)铣床铣床 ti21195341）问题：）问题：n个零件在两台设备上加工，它们的工艺顺序相同个零件在两台设备上加工，它们的工艺顺序相同2022-11-26生产作业计划与控制解：解：首先进行排序
9、首先进行排序 方案一：方案一：一一一一一一一一 方案二；方案二；一一一一一一一一 有两个方案有两个方案 设备设备 零件零件(1)车床车床 ti1681237(2)铣床铣床 ti21195342022-11-26生产作业计划与控制设备零件设备零件(1)车床车床681237(2)铣床铣床119534Fi1 计算的根据：一个零件在设备计算的根据：一个零件在设备(1)上加工必须等到它前面的零上加工必须等到它前面的零 件在设备件在设备(1)上加工完成之后才能进行。上加工完成之后才能进行。ti1ti2Fi1Fi2336812745911336 29179640342920故故:从表中可以看出，最大流程时间
10、从表中可以看出，最大流程时间(零件的总加工周期）为零件的总加工周期）为40Fi2 计算的根据：一个零件在设备计算的根据：一个零件在设备(2)上加工必须等到该零件在设上加工必须等到该零件在设 备备(1)上加工完并且设备上加工完并且设备(2)加工完前一个零件之后才能开始加工完前一个零件之后才能开始2022-11-26生产作业计划与控制ti1ti2Fi1Fi2611831274589636 2917141743393426设备设备 零件零件(1)车床车床 ti1681237(2)铣床铣床 ti2119584排序方案排序方案1（按照（按照ti2 从大到小）：从大到小）：一一一一 一一一一例例2：对下列
11、问题排序，使完成任务的最大流程时间最短：对下列问题排序，使完成任务的最大流程时间最短.排序方案排序方案2（按照（按照约翰逊法约翰逊法）：）：一一 一一 一一一一ti1ti2Fi1Fi2386812745911336 2917911403631222022-11-26生产作业计划与控制设备零件设备零件(1)车床车床681237(2)铣床铣床119534（1）aibi的零件为 ，按ai值不减的顺序列得：序列A：-解：（2）aibi的零件为，按bi值不增的顺序排列得：序列B：-（3）将A放到B之前得到：-2022-11-26生产作业计划与控制2022-11-26生产作业计划与控制设备零件设备零件 A
12、车床车床158612 B铣床铣床3156 C磨床磨床410572、三台设备流水型排序问题及解法、三台设备流水型排序问题及解法1）问题：）问题：n种零件在三台种零件在三台 设备上加工，其工艺顺设备上加工，其工艺顺 序均相同。序均相同。2)目标：加工周期最短，目标：加工周期最短，即最大流程时间最小。即最大流程时间最小。3)方法：约翰逊扩展法方法：约翰逊扩展法2022-11-26生产作业计划与控制设备零件设备零件 A车床车床158612 B铣床铣床3156C磨床磨床410575）步骤）步骤2022-11-26生产作业计划与控制设备零件设备零件 A车床车床158612 B铣床铣床3156C磨床磨床41
13、057设备零件设备零件G1891118H71110136)例题：已知如表，求加工周期。例题：已知如表，求加工周期。解：解：判定是否满判定是否满足使用条件：足使用条件：minti1=6 maxti2=6满足：满足：minti1 maxti2可得右下表：可得右下表：2022-11-26生产作业计划与控制设备零件设备零件 A车床车床158612 B铣床铣床3156C磨床磨床41057最优排序为：最优排序为：一一一一 一一 8 4126209443126ti1ti2Fi1Fi2ti3Fi3 8 1 12615 35 610754193338482022-11-26生产作业计划与控制课堂练习：课堂练习：
14、对下列流水型问题排序，使完成任务的最大流程时间最对下列流水型问题排序，使完成任务的最大流程时间最短，并求最短加工周期。短，并求最短加工周期。(1)(2)设备设备 零件零件(1)车床车床 ti1108642(2)铣床铣床 ti2135792022-11-26生产作业计划与控制式中：式中：i表示表示i零件的斜度指标零件的斜度指标 m为设备数为设备数 tik为为i零件在零件在k设备上的加工时间设备上的加工时间k=1,2,m设备零件设备零件(1)1263(2)8429(3)4582（1）零件的斜率指标法零件的斜率指标法(palmer)第一步：求各零件的斜度指标第一步：求各零件的斜度指标2022-11-
15、26生产作业计划与控制设备零件设备零件(1)1263(2)8429(3)4582k=1,2,m解：对于本例解：对于本例 i第二步：按不增的顺序排列零件，即得满意解第二步：按不增的顺序排列零件，即得满意解 故排序：故排序：一一一一一一或或一一一一一一=-ti1+ti32022-11-26生产作业计划与控制设备零件设备零件(1)1263(2)8429(3)4582ti13111614tik为为i零件在零件在k设备上的设备上的 加工时间加工时间,m为设备数为设备数.2022-11-26生产作业计划与控制设备零件设备零件(1)1263(2)8429(3)4582ti13111614解：计算此例中解：计
16、算此例中ti=ti1+ti2+ti3 总加工时间最长的为总加工时间最长的为零件，故关键零件选择零件，故关键零件选择 ti1 ti3的零件为的零件为，按按ti1的值的值从小到大排从小到大排 在在之前，即之前，即为为 一一一一 ti1 ti3的零件为的零件为，排在排在之后，即为之后，即为一一 故排序为故排序为一一一一一一 2022-11-26生产作业计划与控制设备零件设备零件(1)1263(2)8429(3)4582tikk=1L tikk=m+1-Lm和和第二步第二步:对于每个对于每个L,用上述两组数据构成一个两台设用上述两组数据构成一个两台设备的流水型排序问题备的流水型排序问题,并用约翰逊法进
17、行排序。并用约翰逊法进行排序。第三步第三步:对所得（对所得（m-1）个排序比较选优。）个排序比较选优。2022-11-26生产作业计划与控制当当L=1时，排序为时，排序为一一一一一一 Fmax=281 12939241513ti1ti2Fi1Fi2ti3Fi3 1 8 263 92 44582131826282022-11-26生产作业计划与控制2 12986271810ti1ti2Fi1Fi2ti3Fi3 2 4 613 98 2584211192329当当L=2时，排序为时，排序为一一一一一一 Fmax=29一一一一一一 Fmax=28 2022-11-26生产作业计划与控制课堂练习：课堂
18、练习：分别用零件的斜率指标法、关键零件法、分别用零件的斜率指标法、关键零件法、CDS法对下列流水型问题排序，并求加工周期。法对下列流水型问题排序，并求加工周期。2022-11-26生产作业计划与控制汽车汽车整修时间整修时间(小时小时)喷漆时间喷漆时间(小时小时)A63B04C52D86E212022-11-26生产作业计划与控制铣床铣床到达系统工到达系统工件的集合件的集合离开系统离开系统（机器）（机器）J J1 1J J2 2JkJk.JnJn车床车床磨床磨床车床车床离开系统离开系统（机器）（机器）磨床磨床铣床铣床JiJiJkJk单件作业排序问题的特征：零件的加工路线不同单件作业排序问题的特征
19、：零件的加工路线不同1、问题的描述、问题的描述2、排序方法、排序方法3、优选调度法则、优选调度法则2022-11-26生产作业计划与控制试说明事件试说明事件(3，4，1)和事件和事件(2，3，3)的含义的含义(3)上图中每个方框表示一个事件。事件的表达方式为：上图中每个方框表示一个事件。事件的表达方式为：(i，j，k)，i表示工件号，表示工件号，j表示工序号，表示工序号，k表示完成表示完成i工件的工件的第第j道工序的机器代号。道工序的机器代号。J1,1,J1,1,铣床铣床J1,2,J1,2,车床车床J1,mJ1,m，磨床磨床J1J1Jk,1,Jk,1,车床车床离开系统离开系统（机器）（机器）J
20、k,2,Jk,2,磨床磨床Jk,m,Jk,m,铣床铣床JkJk离开系统离开系统（机器）（机器）2022-11-26生产作业计划与控制(5)用加工描述矩阵用加工描述矩阵D来描述所有工件的加工来描述所有工件的加工 每一行描述一个工件的加工，故每一行的工件每一行描述一个工件的加工，故每一行的工件号相同，每一列的工序号相同号相同，每一列的工序号相同(6)加工时间矩阵加工时间矩阵 2 4 2 3 5 4T 1,1,1 1,2,3 1,3,2 2,1,3 2,2,1 2,3,2D2022-11-26生产作业计划与控制单件作业计划种类单件作业计划种类:q 半能动作业计划（半能动作业计划（Semi-activ
21、e scheduleSemi-active schedule）各工序都按最早可能开（完）工时间安排的各工序都按最早可能开（完）工时间安排的作业计划。作业计划。q能动作业计划（能动作业计划（Active scheduleActive schedule）任何一台机器的每段空闲时间都不足以加工任何一台机器的每段空闲时间都不足以加工一道可加工工序的半能动作业计划。一道可加工工序的半能动作业计划。q无延迟作业计划（无延迟作业计划（Non-delay schedu1eNon-delay schedu1e）没有任何没有任何延迟延迟出现的能动作业计划。出现的能动作业计划。“延迟延迟”：有工件等待加工时，机器出
22、现空闲，即使这有工件等待加工时，机器出现空闲，即使这段空闲时间不足于完成一道工序段空闲时间不足于完成一道工序。2 两种单件作业排序方法两种单件作业排序方法2022-11-26生产作业计划与控制(1)最小最早完工时间法（能动作业计划）最小最早完工时间法（能动作业计划）(2)最小最早开工时间法（无延迟作业计划）最小最早开工时间法（无延迟作业计划）1,1,1 1,2,3 1,3,2 2,1,3 2,2,1 2,3,2D 2 4 2 3 5 4T2022-11-26生产作业计划与控制 1,1,1 1,2,3 1,3,2 2,1,3 2,2,1 2,3,2D 2 4 2 3 5 4T排定事件条件排定事件
23、条件2022-11-26生产作业计划与控制最小最早完工时间法选择排定事件的条件：最小最早完工时间法选择排定事件的条件：（1）属于可排事件）属于可排事件（2）符合所需机器）符合所需机器（3）最早可能开工时间小于最小最早可能）最早可能开工时间小于最小最早可能完工时间完工时间返回返回2022-11-26生产作业计划与控制 1,1,1 1,2,3 1,3,2 2,1,3 2,2,1 2,3,2D 2 4 2 3 5 4T时间时间机器机器机器机器1机器机器2机器机器31,1,12,1,31,2,32,2,12,3,21,3,20032 378121482022-11-26生产作业计划与控制(2)最小最早
24、开工时间法最小最早开工时间法 1,1,1 1,2,3 1,3,2 2,1,3 2,2,1 2,3,2D 2 4 2 3 5 4T排定事件条件排定事件条件2022-11-26生产作业计划与控制最小最早开工时间法选择排定事件的条件：最小最早开工时间法选择排定事件的条件：（1）属于可排事件）属于可排事件（2）符合所需机器）符合所需机器（3）最早可能开工时间等于最小最早）最早可能开工时间等于最小最早可能开工时间可能开工时间返回返回2022-11-26生产作业计划与控制时间时间机器机器机器机器1机器机器2机器机器3 1,1,1 1,2,3 1,3,2 2,1,3 2,2,1 2,3,2D 2 4 2 3 5 4T按此方法编制出的按此方法编制出的作业计划叫做：作业计划叫做：无延迟作业计划无延迟作业计划 1,1,12,1,31,2,32,2,12,3,21,3,20032 37891372022-11-26生产作业计划与控制2022-11-26生产作业计划与控制
