作业排序与生产作业计划培训课件.ppt

(二) 作业排序的三类启发式算法 1、优先调度法 ( 见教材311~314页) 对应用优先调度法则的说明 2.随机抽样法 3.概率调度法 8个主要的优先调度法则：P312 二、一般n/m/G/Fmax问题的启发式算法 1、SPT法则(最短加工时间规则)例题 SPT法则就是优先选择加工时间最短的工序。即排序时将各个工件的加工时间由短到长进行排队，排在前面的加工时间最短的工序优先按排加工。其优点是，使平均流程时间F最短，使在制品的占用量减少，其缺点是没有考虑交货期，有可能会使部分工件延误了交货期。 例：现有一个6/1/F问题，其加工时间与交货期如表11-10所示，试采用SPT法则进行作业排序。 (三) 优先调度法则例题(此为单台设备排序问题例题) 表11-10 加工时间与交货期表 工序号 J1 J2 J3 J4 J5 J6 加工时间 4 8 2 5 9 3 交货期 24 23 8 6 32 13 1、SPT法则(最短加工时间规则)例题。解： 2 5 9 14 22 31 2 3 4 5 8 9 1 6 F = ?(2+5+9+14+22+31)=13.8 工 件 号 J3 J6 J1 J4 J2 J5 交货期di 8 13 24 6 23 32 流程时间Fi=Ci 2 5 9 14 22 31 延期交货Li -6 -8 -15 8 -1 -1 由求解过程可知，按SPT法则排序顺序为：J3， J6， J1，J4， J2， J5； 流程时间分别为：2， 5 ， 9 ， 14 ， 22， 31； F=13.8；工件 J4 延期交货8个时间单位。其余提前完成 (4) 统计延期交货状况： (3)计算平均流程时间 (2)计算各工件加工流程时间，标在加工时间的右上角： (1)将各个工件加工时间由短到长排队为： J3 2，J6 3，J1 4，J4 5，J2 8，J5 9 表11-11 延期交货统计表 转后例 2、EDD规则(最早预定交货规则)例题 EDD规则就是优先选择完工期限紧的工件。即，在进行工件作业排序时，按工件完工期限由紧到松进行排序，排在前面的完工期限最紧的工件优先按排加工。EDD 法则的优点是考虑了交货期，有利于做到按期交货，使工件中的最大延迟时间最小。其缺点是使平均流程时间F增加，增大了在制品占用量。 (三) 优先调度法则例题(此为单台设备排序问题例题) 工序号 J1 J2 J3 J4 J5 J6 加工时间 4 8 2 5 9 3 交货期 24 23 8 6 32 13 试进行作业排序(使Lmax最小)。 表11-10 加工时间与交货期 例：(仍采用上例)有一个6/1/Lmax问题(即6个工件，1台机器，使最大延迟时间最小)，其加工时间与交货期如表11-10所示。 由表11-12计算可知，该例采用EDD法则排序为： J4、 J3 、J6 、J2 、J1、 J5，且各工件延迟时间均为0。平均流程时间 F=15.5 (三) 优先调度法则例题(此为单台设备排序问题例题) 2、EDD规则(最早预定交货规则)例题 解：根据EDD法则是将完工期限最紧的工序优先按排，为此 采用 表 11-12把 交货期短的工件先按排，再求出流程时间与交货期相比较，检查是否存在有延迟时间的工件，延迟时间是多少，是否可以在排序上再进行调整。 工 件号 J4 J3 J6 J2 J1 J5 交货期 6 8 13 23 24 32 加工与流程时间 5 2 3 8 4 9 延迟时间 5 7 10 18 22 31 表11-12 延迟时间分析表 0 0 0 0 0 0 转前例 3、SPT与EDD混合(结合)法则例题 这是将SPT规则(最短加工时间规则)与EDD规则(最早预定交货规则)结合起来的在单台设备上的排序方法。这种排序方法克服了SPT与EDD两个单一规则只能达到一个目标的缺点，可以获得较为理想的结果。为了说明问题方便，仍以表11-10所示的排序问题为例。 (三) 优先调度法则例题(此为单台设备排序问题例题) 表11-10 加工时间与交货期表 工序号 J1 J2 J3 J4 J5 J6 加工时间 4 8 2 5 9 3 交货期 24 23 8 6 32 13 (三) 优先调度法则例题(此为单台设备排序问题例题) 3、SPT与EDD混合(结合)法则例题 按SPT与EDD结合的规则排序步骤如下： （1）首先根据EDD规则排序，即安排一个使Lmax?min(使最长延迟时间最短)的