约翰逊—贝尔曼规则：优化流通加工排序

一、约翰逊—贝尔曼规则

约翰逊—贝尔曼规则指比较各零件在两台机床上的加工时间的数值，选出最小值，若在第一行，则该零件最先加工;若在第二行，则该零件最后加工;若A、B两行的最小值相等，则可最先加工，也可最后加工。除去已选定的零件，重复上一步骤，直到全部零件的加工顺序确定为止。

二、约翰逊—贝尔曼规则的应用范围

其应用有两类: n×2排序问题和n×3排序问题。

n×2排序问题是指有n种零件要依次经过A、B两台流通加工设备加工，如何安排它们的加工顺序，使其加工周期最短的问题。

n×3排序问题是指有n种零件要依次经过A、B、C三台流通加工设备加工，如何安排它们的加工顺序，使其加工周期最短的问题。

实战案例6-4

n×2排序问题

(一) 案例背景

某物流中心要对A、B、C、D四种产品进行相应的流通加工，加工项目包括两个，一是贴标签，二是封口包装。每种产品均需先在贴标签机上进行贴标签，然后在封口机上进行封口操作。各个产品在这两台设备上的加工时间见表6-5。

表6-5 各个产品在这两台设备上的加工时间

(二) 案例要求

1. 请根据以上资料，为该物流中心设计一个合理的产品的流通加工顺序。

2. 这四件商品总的加工时间是多少?

(三) 案例分析

1. 找出加工顺序

第一步: 选出最小值4，在第二行，产品A最后加工。

第二步: 剩下的产品最小值5，在第一行，产品C最先加工。

第三步: 剩下的最小值7，在第二行，产品D倒数第二加工。

最后结果是: C—B—D—A。

2. 利用图表法求出加工总时间，如表6-6所示。

表6-6 图表法求加工总时间

从表6-6可以看出，总加工时间为44分钟。(www.xing528.com)

实战案例6-5

n×3排序问题应用

(一) 案例背景

某配送中心将要对一批产品进行流通加工，整个流通加工工程有5个加工段(A、B、C、D、E)3道(a、b、c)工序，其各加工段的工序工期见表6-7。

表6-7 各加工段及其工序工期

(二) 案例要求

1. 根据方案资料请确定其最优流通加工次序。

2. 总加工周期是多少天?

(三) 案例分析

1. 对于这类问题，如果符合下列两种情况中的一种，就有一个简单的解决办法。这两种情况是:

(1) 第1道工序中的最小加工期大于或等于第2道工序中的最大加工期;

(2) 第3道工序中的最小加工期大于或等于第2道工序中的最大加工期。

本案例符合这个条件。

可按下述方法求得最优施工次序:

第一步，将各项任务中第1道工序和第2道工序的加工期依次加在一起;

第二步，将各项任务中第2道工序和第3道工序的加工期依次加在一起;

第三步，将上两步中得到的加工工期序列看作2道工序的加工期(参见表6-8中的a+b，b+c);

第四步，按上述任务2道工序的方法，求出最优加工次序;

第五步，按所确定的加工次序绘制施工进度图并确定加工总工期。

表6-8 工序工期表

2. 本方案按上述方法确定出最优加工次序为B、A、E、D、C，总加工期为39天;若按A、B、C、D、E的顺序加工，则总工期为42天。