求得总流程时间为48小时(记得减去多加的一组B机器上的零件
的加工时间)。
（三）m台设备的流水型排序问题 台设备的流水型排序问题
1. 关键零件法：把总工时最大的零件作 关键零件法：
为关键零件，其余零件按照一定规则排 列在关键零件之前或之后，可得到近似 最优的加工顺序安排方案。
2. 最小排序系数法：按排序系数的值 最小排序系数法： 由小到大排列。
贝尔曼规则步骤： 约翰逊—贝尔曼规则步骤：
以零件编号为列， 1) 以零件编号为列，零件在机床上的加工 时间为行列表，从中找最小值（ 时间为行列表，从中找最小值（如果有 多个最小值，可任取一个） 多个最小值，可任取一个）； 2) 如果上述最小值属于tiA行，则对应零件 如果上述最小值属于t 应尽先安排； 如果上述最小值属于t 应尽先安排 ； 如果上述最小值属于 tiB 则对应零件应尽后安排； 行，则对应零件应尽后安排； 将已经排定的零件除去，再重复前两步， 3) 将已经排定的零件除去，再重复前两步， 直到全部零件排完为止。 直到全部零件排完为止。
以8台设备为例的贝尔曼扩展法
① ② ③ ④ ⑤ ⑥ ⑦ 1；8 1、2；7、8 1、2、3；6、7、8 1、2、3、4；5、6、7、8 1、2、3、4、5；4、5、6、7、8 1、2、3、4、5、6；3、4、5、6、7、8 1、2、3、4、5、6、7；2、3、4、5、6、7、8
Tmin
六、非流水型排序问题 • 坐标图法
约翰逊—贝尔曼规则扩展法 约翰逊 贝尔曼规则扩展法（续） 贝尔曼规则扩展法
4) 重复以上运算。最后将第1、2、…、 （m-1）台共（m-1）台机床的加工时 间合并，第2、3、…、m台共（m-1） 台机床的加工时间合并，所得到的两组 加工时间，排出方案m-1； 5) 求出以上（m-1）个方案中总流程时间 最短者为最优或近似最优方案。
Ji t tiA tiB tiC 15 3 4 8 1 10 6 5 5 12 6 7 J1 J2 J3 J4
因为mintiA=6≥maxtkB=6，符合条件1，故可 将A、B、C转换为G与H:
Ji t tiG tiH 18 7 9 11 11 10 18 13 J1 J2 J3 J4
加工顺序：J2 —J4 —J3—J1,
三、作业排序的优先规则
规则： ⑴ FCFS规则：优先选择最早到达的工件。 规则 优先选择最早到达的工件。 规则： ⑵ SPT规则：优先选择加工时间最短的工件。 规则 优先选择加工时间最短的工件。 规则： ⑶ EDD规则：优先选择交货期最短的工件。 规则 优先选择交货期最短的工件。 ⑷ SCR： 优先选择临界比最小的工件 。 临界比 ： 优先选择临界比最小的工件。 为工件允许停留时间和工件余下加工时间之比。 为工件允许停留时间和工件余下加工时间之比。 规则： ⑸ MWKR规则 ： 优先选择余下加工时间最长的 规则 工件。 工件。 规则： ⑹ LWKR规则 ： 优先选择余下加工时间最短的 规则 工件。 工件。 ⑺ MOPNR：优先选择余下工序数最多的工件。 ：优先选择余下工序数最多的工件。
生产任务编 号Ji 完成时间C 完成时间 i (天 (天) 交货延期量 Li (天) 天 J3 2 0 J6 5 0 J1 9 0 J4 14 8 J2 22 0 J5 31 0
最大延期量Lmax=8天，平均延期量为：8/6=1.33天，平均流程时间：
1 F = 6
6
∑
i =1
1 F i = (2 + 5 + 9 + 14 + 22 + 31 ) = 13 . 8 6
三、作业排序的任务和目标
（1） 进行优先权设定； ） 进行优先权设定； （2）针对具体设备分配任务及人力； ）针对具体设备分配任务及人力； （3）为目标分配工作，使工作任务按期完成； ）为目标分配工作，使工作任务按期完成； （4）不断监督以确保任务的完成； ）不断监督以确保任务的完成； （5）对实施过程中的问题或异常辨识； ）对实施过程中的问题或异常辨识； （6）作业排序进行检查和修改。 ）作业排序进行检查和修改。
例12-4： 设有J1、J2两种零件，在A、B、C、D四种 机床上加工，其工艺顺序及所需时间如表 12-8所示，要求合理安排每台机床上零件 的加工顺序，以便使总流程时间最短。 （A、B、C、D四种机床各一台）
零件在四台机床上的加工顺序及时间
零 J1
件
机
床
工艺顺序 时间（小时） 工艺顺序 时间（小时）
四、单台设备排序问题 例12-1
生产任务编 号Ji 加工时间t 加工时间ti (天) 天 预定交货期 di (天) 天 J1 4 24 J2 8 23 J3 2 8 J4 5 6 J5 9 32 J6 3 13
解法一、按SPT规则排序
• 加工顺序为： J3 —J6 —J1 —J4 —J2 —J5
12.1 排序问题概述
一、排序问题的分类 • 按行业分：
生产作业排序 劳动力作业排序
制造业 为主 服务业 为主
•按机器种类和数量不同分
单机排序 多机排序
•按工件加工路线的特征
流水型排序 非流水型作业排序
二、影响作业排序的因素 影响作业排序的因素
1、生产任务的到达方式 、 2、设备种类和数量 、 3、工作人员数量 、 4、生产工艺流程方式 、
（二）三台设备的流水型排序问题
约翰逊—贝尔曼拓展法： 约翰逊 贝尔曼拓展法： 贝尔曼拓展法
设有A、B、C三台加工设备，在满足： mintiA≥maxtkB 或mintiC≥maxtkB 两条件之一的情况下，可将三台设备转换为 两台假想设备G与H，且：
tiG=tiA+tiB tiH=tiB+tiC
例12-3
顾客平均等待时间最短准则 响应顾客服务的概率最大准则 总成本最小准则 销售损失最小准则 预期利润最大准则
服务作业的排序方法
1. 优先准则排序 2. 服务人员的轮班排序
– 全部雇佣专职人员情况下的排序（重点） – 雇佣部分兼职人员情况下的排序 教材P311 教材P311 例：连续休息两天的五日工作制下的 人员安排方法。
上例方案1，采用矩阵法计算总流程时间为40 小时
J4 ta tb 3 3 3 6 11 20 6 9 9 29 J1 8 17 5 34 J2 12 29 4 40 J3 7 36 J5
同样，可求得方案2总流程时间也为40小时。但不同之处在 于，两种排序结果中机床B的加工、停歇时间不同，设备利 用率不同。
A—B—C—D 2 1 8 2 A—D—B—C 1 4 1 4
J2
产品J 产品 2 C
B
A A B C D 产品J 产品 1
求解最短的总流程时间可采用最短折线上的时间之 和。在本例中：F=2+1+8+2+（2）=15小时
12.3 服务业中的作业排序
• 服务业与制造业排序的区别 • 服务作业排序的分类 服务作业的排序准则
二、排序方案的评价标准
• 总流程时间最短； 总流程时间最短； • 平均流程时间最短； 平均流程时间最短； • 最大延迟时间或最大误期最短； 最大延迟时间或最大误期最短； • 平均延迟或平均误期最短； 平均延迟或平均误期最短； • 平均在制品占用量最小； 平均在制品占用量最小； • 总调整时间最小； 总调整时间最小；
1 6 1 F = ∑ Fi = (5 + 7 + 10 + 18 + 22 + 31) = 15.5 6 i =1 6
五、流水型排序问题 （一）两台设备的流水型排序问题 1、排序方法： 约翰逊—贝尔曼规则 设零件Ji（i=1、2、…，n）的 加工顺序是从设备A到设备B，t iA 和 t iB 分别是零件J 在A和B上的加工时间。 i
例12-2
Ji t（小时） 小时） tiA tiB J1 6 11 J2 8 9 J3 12 5 J4 3 3 J5 7 4
加工顺序如下： 加工顺序如下： J4—J1 —J2—J3—J5 或 J1 —J2 —J3—J5—J4
2、确定总流程时间
• • 甘特图法 画法与零件移动方式图的画法相同； 矩阵表法 按确定的零件加工顺序列表。 （见下页）
排序系数：零件在前半部机床上加 工工时与在后半部机床上加工工时的比 值。若机床数为奇数，最中间机床的加 工工时平分于前后两部分。
3. 约翰逊 贝尔曼扩展法 约翰逊—贝尔曼扩展法
1) 将零件在第1台与第m台设备上的加工看作 两台设备流水排序问题，排出方案1； 2) 将零件在第1、2台设备上的加工时间合并、 第（m-1）、m台设备上的加工时间合并， 所得到的两组加工时间，排出方案2； 3) 将第1、2、3台设备的加工时间合并、第 （m-2）、（m-1）、m台设备上的加工时 间合并，所得到的两组加工时间，排出方 案3；
解法二、按EDD规则排序
• 加工顺序为：J4 —J3 —J6 —J2 —J1 —J5
生产任务编 号Ji 完成时间C 完成时间 i (天) 天 交货延期量 Li (天) 天 J4 5 0 J3 7 0 J6 10 0 J2 18 0 J1 22 0 J5 31 0
最大延期量和平均延期量均为零，而平均流程时间为：
12.2 制造业作业排序
一、排序问题的假设 排序问题的假设 一个工件不能同时在几台机器上加工； ⑴ 一个工件不能同时在几台机器上加工； 每台机器同时只能加工一个工件； ⑵ 每台机器同时只能加工一个工件； 每道工序只在一台机器上完成； ⑶ 每道工序只在一台机器上完成； 工件在加工过程中采取平行移动方式； ⑷ 工件在加工过程中采取平行移动方式； 工件在加工过程中不允许中断； ⑸ 工件在加工过程中不允许中断； 工件数、机器数和加工时间均已知； ⑹ 工件数、机器数和加工时间均已知；