沈斌分享 http://blog.sciencenet.cn/u/bshen 同济大学中德学院机械工程系主任、制造执行系统(MES)分会理事长

博文

准确理解制造执行系统(MES)(五)作业计划的优化(2)

已有 1625 次阅读 2019-8-13 14:35 |个人分类:学术论文|系统分类:科研笔记|关键词:学者| 作业计划优化, MES, 数字化工厂, 智能制造

 

准确理解制造执行系统(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

 

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

Ji ──零件种类,=1,2,··· 

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 ):

T1=1天,T2=1天,T3=3天,T4=1天,T5=0天。

方案A的最大交货误期为:Tmax=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,零件J2J4满足公式(2),再根据公式(3)选择处理时间大的J4后加工,即为顺序倒数第二个。

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

还有2个零件的处理时间总和为4,零件J1J2都满足公式(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=0T2=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=0T2=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大的优化是在保证最大交货期误期为最小的前提下,得到为最小的零件最优排序,兼顾了两个目标大的优点。这里仅仅是5个零件,如果有更多的零件,其结果差别就更大了。这就是优化算法(数学模型)的威力所在。

 

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

 



https://m.sciencenet.cn/blog-39413-1193471.html

上一篇:准确理解制造执行系统(MES)(四)作业计划的优化(1)
下一篇:准确理解制造执行系统(MES)(六)作业计划的优化(3)

0

该博文允许注册用户评论 请点击登录 评论 (0 个评论)

数据加载中...

Archiver|手机版|科学网 ( 京ICP备07017567号-12 )

GMT+8, 2022-10-5 19:32

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部