基于数学规划模型的工件加工问题的求解.docx

基于工件加工问题的求解
摘要
对于一个加工企业而言,如何在最短时间内完成加工任务，是一个企业提高竞争力和利润的关键。本文就是一篇关于工件加工的排序优化问题，在给定的数据和符合实际生产的条件下,合理的安排工件的加工顺序，使总加工时间达到最少.对于工件加工次序模型的求解,我们可以运用许多方法来进行求解，但是考虑到3台机床加工10个零件的给定一加工顺序,所有零件通过机床的顺序是一致的； 每个零件在各机床的加工时间已知,且每台机床在同一时间只能加工一个零件。M2及M3工序上会出现等待.如果采用不同序加工，那么在M1上已加工好的零件,在M2上加工的时间会落到在M1上比其后加工的零件的后面，则其在M2上等待的时间更长，同样在M2与M3工序上也是这样,要求加工时间最短的加工顺序,就必须尽量减少零件在M2及M3工序上的等待时间,由于零件必须在它们要求的时间内完工，即某零件在任务开始起到该零件加工完毕之间所用的总时间应少于该零件的规定完工时间.所以要使各个零件在车间待的总时间最短,其加工零件顺序固然只有一种。那么就要合理选择加工零件的种类及其加工的次序。
本题根据已知数据，结合问题中的具体要求，我们引入0/1变量建立零件排序的数学规划模型.通过lingo得出其中的最优排序方案。使得完成这批工件加工任务所需要的总时间最省。然后我们对各个排序后的零件完成特定工序所需花费时间进行求和得到整个加工程序所需总时间。总时间包括了各个零件在机床的加工时间以及加工其它零件的等待时间。
最后,根据建立的模型求出某车间加工十个零件所需最短的时间为413分钟,总加工时间最短的加工顺序为D-H—G-I—J-E-A—F-C—B，具体结果如表1—1，1-2.
若件加工还要满足下面条件，零件D必须在零件E之前加工;零件H与零件J的加工必须相连;机床M3加工每个零件等待时间不能超过5分钟，总等待时间不能超过30分钟。那么继续利用lingo软件求解可以得出在此条件下最优的顺序为G－I-D－H－J－E－A－F－C－B，所需最短的时间为425分钟，具体结果如表3—1,3—2。
关键词： 线性规划 0/1变量 数学规划模型 lingo软件
一、 问题重述
车间上午8：00开始加工十个零件，这些零件必须依次通过机床M1，M2，M3，其加工时间如下表（单位：分钟）.

M1
M2
M3
A
13
15
20
B
10
20
18
C
20
16
15
D
8
10
6
E
9
14
13
F
19
20
14
G
11
16
12
H
16
9
18
I
15
12
7
J
13
7
9
1。 试建立模型求出使总加工时间最短的加工顺序。
2. 写出各零件加工起止时间表,求出各机床的等待时间.
3. 若零件加工还要满足下面条件，零件D必须在零件E之前加工;零件H与零件J的加工必须相连；机床M3加工每个零件等待时间不能超过5分钟，总等待时间不能超过30分钟.试建立模型，重新回答前面两个问题.
二、 问题分析
零件在M1工序上的总加工时间是固定的,无关乎零件加工顺序.问题关键在于零件在M2以及M3工序上回出现等待。若采取不同加工顺序，那么在M1上已加工好的零件会在M2工序上出现等待.同样在M2上加工好的零件在M3工序上也会出现这种现象.要求加工时间最短的加工顺序,就必须尽量减少零件在M2及M3工序上的等待时间，由于零件必须在它们要求的时间内完工，即某零件在任务开始起到该零件加工完毕之间所用的总时间应少于该零件的规定完工时间。若要使整个加工任务的零件总价值最大，应选择最优加工零件的种类及其加工的次序。
若零件D必须在零件E之前加工且零件H与零件J的加工必须相连；机床M3加工每个零件等待时间不能超过5分钟,总等待时间不能超过30分钟.那么就需在第一个建立好的模型上附上条件，得出该条件下的最优次序.
三、 模型假设
假设一：在后面的模型中，我们都假定了忽略零件在转换工序时的运输时间。即将整个零件加工过程简化为一个连续的过程,只考虑机床在加工零件时其他零件的等待时间.
假设二：零件之间是相互独立的,从生产的角度看,先加工一个零件并不响对后面零件的加工。不象有些流水线生产那样，存在固定的加工顺序。
假设三：工人都是熟练工人，零件在工序上的加工时间是固定不变的，与工人的操作水平无关。
假设四：零件在三个工序上采有同顺序加工,即在工序M1上的加工顺序与在M2及M3工序上的加工顺序相同。在工序M1上的加工是连续不断的。
四、 符号说明
Xi （1）:i零件在车床M1加工所需时间
Xi （2) ：i零件在车床M2加工所需时间
Xi （3） ：i零件在车床M3加工所需时间
Ti (1)：i零件完成在M1加工的总时间
Ti （2）:i零件完成在M2加工的总时间
Ti （3)：i零件完成在M3加工的总时间
Ti-1（2)：（i-1)零件完成在M2加工的总时间（i〉1)
Ti-1（3)（i-1)零件完成在M3加工的总时间(i〉1）
T：加工十个零件模型的总时间
五、 模型的建立
由问题分析可知工件i在M1工序完成的时间：
Ti1=Ti-11+Ti1 (1)
对于工件i在M1工序完成的时间Ti1与（i—1）工件完成在M2加工的总时间Ti-12要分两种情况分析：
（1)当Ti1≥Ti-12时，即i工件完成M1工序的总时间大于或等于（i-1）工件完成M2工序的总时间，此时i工件不需要等待（i—1）工件而立即就进入下一工序，因此i工件完成 M2工序的总时间表达式为：
Ti2=Ti1+Xi2
(2）当Ti1≤Ti-12时,即i工件完成M1工序的总时间小于或等于（i—1)工件完成M2工序的总时间,此时i工件需要等待（i—1）工件完成M2工序才能进入M2加工。因此i工件 完成M2工序的总时间表达式为：
Ti2=Ti-12+Xi2
综合以上两种情况，得到i工件完成M2工序的总时间计算公式为：
-=+>Ti2=maxTi1，Ti-12+Xi2 （i>1） （2）
同理:对于工件i在M2工序完成的时间Ti2与（i—1）工件完成在M3加工的总时Ti-13，有i工件完成M3工序的总时间计算公式为:
Ti3=maxTi2,Ti-13+Xi3 （i〉1) （3）
综合（1）（2）(3）可得加工十件零件需要的总时间为:
T=Ti3+i=210maxTi2,Ti3+Xi3
约束条件：
s.t. =1,（i=1，2，3，…，10）
=1，（j=1,2,3，…，10）
六、 模型求解
算法流程图
通过lingo求解，我们得出以下结论：
顺序号
零件号
M1加工时间XI（1)(分钟）
M2加工时间分XI(2）钟）
M3加工时间
Xi（3 (分钟）
1
D
8
10
6
2
H
16
9
18
3
G
11
16
12
4
I
15
12
7
5
J
13
7
9
6
E
9
14
13
7
A
13
15
20
8
F
19
20
14
9
C
20
16
15
10
B
10
20
18
顺序号
零件号
完成M1工序总时间MI(1）(分钟)
完成M2工序总时间MI(2(分钟）
完成M3工序总时间MI（3）（分钟)
1
D
8
18
24
2
H
24
33
51
3
G
35
51
63
4
I
50
63
70
5
J
63
70
79
6
E
72
86
99
7
A
85
101
121
8
F
104
124
138
9
C
124
140
155
10
B
134
160
178
表1-1

序
顺
间
时
止
起
号
序
工

M1
M2
M3
D
8：00—8：08
8:08-8：18
8:18—8:24
H
8：08—8：24
8：24-8：33
8:33—8：51
G
8：24—8:35

8：35—8:51
8：51-9：03
I
8:35—8：50
8：51—9：03
9：03-9；10
J
8:50—9:03
9：03—9：10
9:10—9：19
E
9：03-9：12
9：12-9：26
9：26—9:39
A
9:12-9：25
9：26—9:41
9：41—10:01
F
9：25—9：44
9：44—10:04
10:01—10：18
C
9：44-10：04
10：04—10：24
10:24—10:35
B
10:04—10：26
10：26—10：40
10：40-10：58
表1-2
工
序
号
等
待
时
间
顺
序
号

M1
M2
M3
D
0
0
0
H
0
6
7
G
0
2
0
I
0
0
0
J
0
0
0
E
0
0
0
A
0
0
0
F
0
4
0
C
0
0
5
B
0
0
6
顺序号
零件号
M1加工时间XI（1）（分钟）
M2加工时间分XI（2）钟）
M3加工时间
Xi(3 (分钟）
1
G
11
16
12
2
I
15
12
7
3
D
8
10
6
4
H
16
9
18
5
J
13
7
9
6
E
9
14
13
7
A
13
15
20
8
F
19
20
14
9
C
20
16
15
10
B
10
20
18
顺序号
零件号
完成M1工序总时间MI（1)（分钟）
完成M2工序总时间MI(2（分钟）
完成M3工序总时间MI（3）（分钟)
1
G
11
27
39
2
I
26
39
46
3
D
32
49
55
4
H
48
58
76
5
J
61
68
85
6
E
70
84
98
7
A
83
99
119
8
F

102
122
136
9
C
122
138
153
10
B
132
158
176
表3—1

序
顺
间
时
止
起
号
序
工

M1
M2
M3
D
8：00—8：11
8：11-8:27
8：27—8:39
H
8:11-8：26
8:27—8：39
8:39—8:46
G
8:26—8：32
8：39—8：49
8:49—8：55
I
8:32-8:48
8：49-8：58
8:58—9：16
J
8：48—9：01
9：01-9：09
9：16—9:25
E
9：01—9：10
9:10-9:24
9:25—9：38
A
9：10—9:23
9：24-9：39
9：39—9：59
F
9：23—9：42
9：42—10：02
10：02-10：26
C
9:42—10:02
10：02—10:18
10：26—10:33
B
10：02—10：32
10：32—10：38
10:38-10：56
表3—2
工
序
号
等
待
时
间
顺
序
号

M1
M2
M3
G
0
0
0
I
0
0
0
D
0
0
3
H
0
0
3
J
0
3
0
E
0
1
0
A
0
0
1
F
0
3
3
C
0
0
0
B
0
14
5
七、 模型评价
在本题中，对于第一题中构建了数学规划模型，将整批工件的加工任务拆分为在最优的排序下每个工件的实际加工情况来分析，根据各工件在加工过程中加工时间和总时间之间的联系，寻求各工件加工总时间的具体算法。再利用Lingo软件进行求解模型，得出工件的最优排序。其中逻辑严谨，论证充分，算法简洁准确。有效地提高了软件求解效率.
考虑到它其实是一个有限源的“单队—-多服务台”模型由于运用了lingo软件进行求解,使模型本身就具有很大的可移植性，方便了其到m件零件n台机床的延伸与应用。
但是我们的模型还是存在一些不足之处.模型对于无限源的情况并不适用，与现实生活并不相符合，只是用于理论的研究。
但是总的来说，该模型对于日常生活中的工作安排问题还是具有很大的实际运用价值，值得推广。
八、 参考文献
［1]清华大学《运筹学》教材编写组。运筹学（第三版）[M]清华大学出版社，2005
［2]洪文,吴本忠，Lingo4.0 for windows 优化软件及应用，北京大学出版社,2001。
［3］颜文勇，数学建模，高等教育出版社，北京，2011。6
［4］姜启源 谢金星 叶俊等，数学模型（第四版），高等教育出版社，2010.
[5]卢开澄。单目标、多目标与整数规划［M］。北京：清华大学出版社，1999。
［6］张建中.线性规划，[M］.北京:科学出版社,1999
[7］ http：//wenku。baidu。com/view/63bfcf3410661ed9ad51f391.html
九、附录
model：
！工件先M1后M2再M3的的排序问题;
sets：
gongjian/g1。。g10/：M1_shijian,M2_shijian，M3_shijian；
shunxu/s1。。s10/：M1_time,M2_time，M3_time，M1_fintime，M2_fintime,M3_fintime;
links（shunxu，gongjian）： note；
endsets
！目标函数;
min=＠sum（shunxu（I）:M3_fintime（I))；
！重新排序后各工件的M1床加工时间;
＠for（shunxu（I):
che_time（I)=＠sum（gongjian（J)：M1_shijian（J)*note(I，J)）；
）；
！ 重新排序后各工件的M2床加工时间；
＠for(shunxu(I)：
zuan_time(I）=＠sum(gongjian(J）：M2_shijian（J）*note(I，J））;
）;
！ 重新排序后各工件的M3床加工时间；
@for(shunxu（I):
xi_time（I)=＠sum（gongjian（J）：M3_shijian（J）＊note(I,J）)；
)；
！每个顺序位只能有一个工件；
＠for(shunxu（I)：
＠sum（gongjian(J）： note（I，J)）=1；
）;
！每个工件只能排在一个顺序位上；
@for（gongjian（J）:
＠sum（shunxu（I): note(I，J）)=1；
)；
！从新排序后各工件的M1完工时间；
@for(shunxu（I）：
chefintime（I)=@sum(shunxu（J）｜J＃le＃I：M1_time(J）);
);
！从新排序后各工件在M2工序的完工时间;
＠for（shunxu（I）｜ I＃gt＃1：
M2_fintime(I）=＠if（M1_fintime（I）#ge＃M2_fintime（I—1），M1_fintime(I），M2_fintime(I-1）)+M1_time(I）;
）；
！顺序1中的M1床工序的完工时间；
M2_fintime(1）=M1_fintime（1）+M2_time（1）;
！ 重新排序后各工件在完成M3工序的时间；
@for(shunxu（I）｜ I＃gt＃1:
M3_fintime（I）=@if（M2_fintime(I)#ge#M3_fintime(I—1），M2_fintime（I），M3_fintime(I—1）)+M3_time(I);
）；
！顺序1中的M3工序的完工时间;
M3_fintime（1）=M2_fintime（1)+M3_time（1）;
！定义0/1变量;
@for（links：＠bin（note)）；
data:
！输出数据到Excel文档;
＠OLE（'D:\liebiao。XLS’)=M1_time,M2_time，M3_time，M1_fintime，M2_fintime,M3_fintime；
!原始排序下各个工件的M1加工时间；
M1_shijian= 13,10，20，8，9，19,11，16，15,13；
!原始排序下各个工件的M2加工时间；
M2_shijian=15，20,16，10，14，20，16,9，12,7；
！原始排序下各个工件的M3加工时间；
M3_shijian=20，18,15,6,13，14,12,18，7，9；
enddata
end