准确理解制造执行系统（MES）（五）

----作业计划的优化(2)

同济大学中德学院  沈斌 教授

    一批零件要在一台设备或多台设备上加工，零件的不同先后加工顺序，其加工完工时间是大不相同的。下面举两个例子（一个例子是一台设备上加工，另一例子是在5台设备上加工），加以分析说明，这里假设每个零件数量都是1个。为了大家简单明了算法的重要性，选了这两个例子的算法，是众多算法中是最简单的。更复杂而有效的算法，可以查阅相关大量的研究文献。我在百度搜索了“作业计划的排序优化算法”，相关结果约457,000个之多！下面的内容对专业研究人员来说是一目了然地的，但对一般人员来说，可能有点难懂，所以，我尽可能写得通俗一点，并以具体例子加以说明。大家要有信心看下去。

1. 单台设备加工顺序的确定

现在有5个零件（J₁ 、J₂ 、J₃ 、J₄ 、J₅）在一台设备上加工，每个零件处理时间和交货期如表1所示。处理时间表示零件在设备加工占用时间（包括加工时间和调整等辅助时间）。交货期表示该零件在某月的几号交货。

表1 零件加工时间

如何安排零件的加工顺序呢？按照上文分析，将有n!种顺序，即5!=5x4x3x2x1=120种。真有哪么多吗？开始我也有点怀疑，笨人死办法，我将它们一一排了出来。

    如果将零件J₁排在第一个加工，则有如下24中加工顺序：

12345 12453 12543 12453 12354 12534

13245 13452 13542 13452 13254 13524

14235 14352 14532 14352 14253 14523      

15234 15342 15432 15342 15243 15423

    如果将零件J₂排在第一个加工，则有如下24中加工顺序：

21345 21453 21543 21453 21354 21534

23145 13451 23541 23451 23154 3514

24135 24351 24531 24351 24153 24513      

25134 25341 25431 25341 25143 25413

如果将零件J₃排在第一个加工，则有如下24中加工顺序：

32145 32451 32541 32451 32154 32514

31245 31452 31542 31452 31254 31524

34215 34152 34512 34152 34251 34521      

35214 35142 35412 35142 35241 35421

如果将零件J₄排在第一个加工，则有如下24中加工顺序：

42315 42153 42513 42153 42351 42531

43215 43152 43512 43152 43251 43521

41235 41352 41532 41352 41253 41523      

45231 45312 45132 45312 45213 45123

如果将零件J₅排在第一个加工，则有如下24中加工顺序：

52341 52413 52143 52413 52314 52134

53241 53412 53142 53412 53214 53124

54231 54312 54132 54312 54213 54123      

51234 51342 51432 51342 51243 51423

我们现在采用的排序准则，或优化目标是保证最大交货期误期为最小的前提下，得到Ｆ为最小的零件最优排序（注意这里的优化目标有两个，但是以第一目标为前提再考虑第二目标）。为此，假定在一台设备上加工ｎ种零件时，加工过程无故障，可连续加工。并设定：

Ji ──零件种类，ｉ＝１，２，···  ｎ；

Pi ──零件Ji的处理时间（包括加工时间与调整时间）；

Fi ──零件Ji的完工时间（即通过时间）；

di ──零件Ji的交货期；

Ti ──零件Ji的交货误期，，

    最大交货误期  ；

Di ──零件Ji的最大拖期时间  ；

F ──所有零件平均完工时间

             (1)

要保证最大交货期误期为最小的前提下，得到Ｆ为最小的零件最优排序，可先按零件交货期由小到大排序，求得最大交货误期，并分别算出Di。若按此最优顺序的原则找到最后一项设为零件k，则满足：

           (2)

    考虑到零件按处理时间由小到大排序，可使平均完工时间为最短。所以，在逐个反推搜索时，若同时出现零件Ｊ也符合时，则零件k还应满足：

                                   （3）

ｍ ─ 尚未分配加工的零件数

通过逐项比较，重复这一步骤，即可得到排序方案。

大家看上面的算法可能不好理解，没有关系，看下面以表1的数据为例，逐步计算求出最优排序，再回过头了看可能就明白了。如果还是不理解，也没有关系，只要记住结论就可以了：不同的排序，产生不同的结果。一般MES系统里把算法写在程序里了。你只要会操作即可。

算法解题的步骤如下：

1. 先按交货期从小到大排序。

即交货期早的先加工，则加工顺序为为J5-J1-J2-J4-J3, 如图1中方案A所示。这个图就是作业计划的甘特图，并表示了每个零件的先后加工顺序、开始时间和完工时间。

若按此顺序加工，各零件的完工期为:

F1=8天 ；F2=9天；F3=15天；F4=11天；F5=5天。

平均完工时间F =（8+9+15+11+6）/ 5 = 9.6天。

零件Ji的交货误期，根据公式 Ti =max(0, Fi - di )：

T₁=1天，T₂=1天，T₃=3天，T₄=1天，T₅=0天。

方案A的最大交货误期为：T_max=3天。

图1 作业排序甘特图

2)保证最大交货期误期为最小的前提下，得到Ｆ为最小的零件最优排序。

计算各零件Ji的最大拖期时间 Di = di + Tmax

D1=7+3=10 ，D2=8+3=11，D3=12+3=15，D4=10+3=13，D5=6+3=9.

满足条件公式（2）的零件最后加工，这时5个零件的处理时间总和为15，所以零件J3满足，放在最后加工。

剩余4个零件的处理时间总和为11，零件J2和J4满足公式（2），再根据公式（3）选择处理时间大的J4后加工，即为顺序倒数第二个。

还有3个零件的处理时间总和为9，零件J1，J2和J5都满足公式（2），根据公式（3）选择处理时间大的J5后加工，即为顺序倒数第三个。

还有2个零件的处理时间总和为4，零件J1，J2都满足公式（2），根据公式（3）选择处理时间大的J1后加工，即为顺序倒数第四个。最后则J2为最先加工。

根据上述的加工排序为：J2-J1-J5-J4-J3（(见图1中方案B）。各零件的完工期为:

F1=4天 ；F2=1天；F3=15天；F4=11天；F5=9天。

平均完工时间F =（4+1+15+11+9）/ 5 = 8天

零件Ji的交货误期， Ti =max(0, Fi - di )：

T₁=0，T₂=0，T₃=3，T₄=1，T₅=0。

方案B的最大交货误期为：Tmax=3天。

3)按处理时间从小到大排序。

即按照零件处理时间小的先加工，则加工顺序为为J2-J4-J1-J3-J5 (见图1中方案C）。各零件的完工期为:

F1=6天 ；F2=1天；F3=10天；F4=3天；F5=15天。

平均完工时间F =（6+1+10+3+15）/ 5 = 7天

零件Ji的交货误期， Ti =max(0, Fi - di )：

T₁=0，T₂=0，T₃=2，T₄=0，T₅=9。

方案C的最大交货误期为：T_max=9天

通过以上计算，得到三个方案的以下结果：

方案A： 最大交货误期T_max =3， 平均完工时间F＝9.6天(按交货期排序）

方案B： 最大交货误期T_max   =3， 平均完工时间F=8天（按优化排序）

方案C：最大交货误期T_max     =9， 平均完工时间F=7天（按加工时间排序）

方案A和方案C都是单目标的优化，而方案B大的优化是在保证最大交货期误期为最小的前提下，得到Ｆ为最小的零件最优排序，兼顾了两个目标大的优点。这里仅仅是5个零件，如果有更多的零件，其结果差别就更大了。这就是优化算法（数学模型）的威力所在。

下文，我即将介绍多工序加工作业排序的确定，即一批零件在多台设备上加工顺序的优化算法（数学模型）。