|||
准确理解制造执行系统(MES)(五)
----作业计划的优化(2)
同济大学中德学院 沈斌 教授
一批零件要在一台设备或多台设备上加工,零件的不同先后加工顺序,其加工完工时间是大不相同的。下面举两个例子(一个例子是一台设备上加工,另一例子是在5台设备上加工),加以分析说明,这里假设每个零件数量都是1个。为了大家简单明了算法的重要性,选了这两个例子的算法,是众多算法中是最简单的。更复杂而有效的算法,可以查阅相关大量的研究文献。我在百度搜索了“作业计划的排序优化算法”,相关结果约457,000个之多!下面的内容对专业研究人员来说是一目了然地的,但对一般人员来说,可能有点难懂,所以,我尽可能写得通俗一点,并以具体例子加以说明。大家要有信心看下去。
1. 单台设备加工顺序的确定
现在有5个零件(J1 、J2 、J3 、J4 、J5)在一台设备上加工,每个零件处理时间和交货期如表1所示。处理时间表示零件在设备加工占用时间(包括加工时间和调整等辅助时间)。交货期表示该零件在某月的几号交货。
表1 零件加工时间
零件 Ji | J1 | J2 | J3 | J4 | J5 |
处理时间 Pi(天) | 3 | 1 | 4 | 2 | 5 |
交货期(日) | 7 | 8 | 12 | 10 | 6 |
如何安排零件的加工顺序呢?按照上文分析,将有n!种顺序,即5!=5x4x3x2x1=120种。真有哪么多吗?开始我也有点怀疑,笨人死办法,我将它们一一排了出来。
如果将零件J1排在第一个加工,则有如下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
如果将零件J2排在第一个加工,则有如下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
如果将零件J3排在第一个加工,则有如下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
如果将零件J4排在第一个加工,则有如下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
如果将零件J5排在第一个加工,则有如下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
我们现在采用的排序准则,或优化目标是保证最大交货期误期为最小的前提下,得到F为最小的零件最优排序(注意这里的优化目标有两个,但是以第一目标为前提再考虑第二目标)。为此,假定在一台设备上加工n种零件时,加工过程无故障,可连续加工。并设定:
Ji ──零件种类,i=1,2,··· n;
Pi ──零件Ji的处理时间(包括加工时间与调整时间);
Fi ──零件Ji的完工时间(即通过时间);
di ──零件Ji的交货期;
Ti ──零件Ji的交货误期,,
最大交货误期 ;
Di ──零件Ji的最大拖期时间 ;
F ──所有零件平均完工时间
(1)
要保证最大交货期误期为最小的前提下,得到F为最小的零件最优排序,可先按零件交货期由小到大排序,求得最大交货误期,并分别算出Di。若按此最优顺序的原则找到最后一项设为零件k,则满足:
(2)
考虑到零件按处理时间由小到大排序,可使平均完工时间为最短。所以,在逐个反推搜索时,若同时出现零件J也符合时,则零件k还应满足:
(3)
m ─ 尚未分配加工的零件数
通过逐项比较,重复这一步骤,即可得到排序方案。
大家看上面的算法可能不好理解,没有关系,看下面以表1的数据为例,逐步计算求出最优排序,再回过头了看可能就明白了。如果还是不理解,也没有关系,只要记住结论就可以了:不同的排序,产生不同的结果。一般MES系统里把算法写在程序里了。你只要会操作即可。
算法解题的步骤如下:
先按交货期从小到大排序。
即交货期早的先加工,则加工顺序为为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 ):
T1=1天,T2=1天,T3=3天,T4=1天,T5=0天。
方案A的最大交货误期为:Tmax=3天。
图1 作业排序甘特图
2)保证最大交货期误期为最小的前提下,得到F为最小的零件最优排序。
计算各零件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 ):
T1=0,T2=0,T3=3,T4=1,T5=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 ):
T1=0,T2=0,T3=2,T4=0,T5=9。
方案C的最大交货误期为:Tmax=9天
通过以上计算,得到三个方案的以下结果:
方案A: 最大交货误期Tmax =3, 平均完工时间F=9.6天(按交货期排序)
方案B: 最大交货误期Tmax =3, 平均完工时间F=8天(按优化排序)
方案C:最大交货误期Tmax =9, 平均完工时间F=7天(按加工时间排序)
方案A和方案C都是单目标的优化,而方案B大的优化是在保证最大交货期误期为最小的前提下,得到F为最小的零件最优排序,兼顾了两个目标大的优点。这里仅仅是5个零件,如果有更多的零件,其结果差别就更大了。这就是优化算法(数学模型)的威力所在。
下文,我即将介绍多工序加工作业排序的确定,即一批零件在多台设备上加工顺序的优化算法(数学模型)。
Archiver|手机版|科学网 ( 京ICP备07017567号-12 )
GMT+8, 2024-8-31 00:20
Powered by ScienceNet.cn
Copyright © 2007- 中国科学报社