零
摘要
件的加工排序的最优模型
于零件加工顺序模型的求解，我们不难想到运用多种方法来达到其求解目的，但是考虑到零件在M1工序上的总加工时间是固定的。关键是在M2及M3工序上会出现等待。如果采用不同序加工,那么在M1上已加工好的零件,在M2上加工的时间会落到在M1上比其后加工的零件的后面,则其在M2上等待的时间更长,同样在M2与M3工序上也是这样，要求加工时间最短的加工顺序，就必须尽量减少零件在M2及M3工序上的等待时间，由于零件必须在它们要求的时间内完工，即某零件在任务开始起到该零件加工完毕之间所用的总时间应少于该零件的规定完工时间。所以要使整个加工任务的零件总价值最大，必须合理选择加工零件的种类及其加工的次序。 本题根据已知数据，结合问题中的具体要求，再使用c++计算，得出其中的最优排序方案。使得完成这批零件加工任务所需要的总时间最省。在这里，我们通过对各个零件（排序后）完成某项特定工序所需总时间进行求和得到整个加工任务所需要的总时间。而各零件的总时间包括其机床加工时间和加工其他零件的等待时间。最优的零件排序为G－I-D－H－J－E－A－F－C－B；完成这批零件加工任务所需的最省总时间为425分钟.
关键字
最短时间 不同顺序 VC++
一、问题重述
某车间上午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上加工的时间会落到在M1上比其后加工的零件的后面,则其在M2上等待的时间更长,同样在M2与M3工序上也是这样，要求加工时间最短的加工顺序，就必须尽量减少零件在M2及M3工序上的等待时间，由于零件必须在它们要求的时间内完工，即某零件在任务开始起到该零件加工完毕之间所用的总时间应少于该零件的规定完工时间。所以要使整个加工任务的零件总价值最大，必须合理选择加工零件的种类及其加工的次序。
三、模型假设
假设一：在后面的模型中，我们都假定了忽略零件在转换工序时的运输时间。即将整个零件加工过程简化为一个连续的过程，只考虑机床在加工零件时其他零件的等待时间。
假设二：零件之间是相互独立的,从生产的角度看,先加工一个零件并不影响对后面零件的加工。不象有些流水线生产那样,存在固定的加工顺序。
假设三：工人都是熟练工人,零件在工序上的加工时间是固定不变的,与工人的操作水平无关。
假设四：零件在三个工序上采有同顺序加工,即在工序M1上的加工顺序与在M2及M3工序上的加工顺序相同。在工序M1上的加工是连续不断的。
四、符号说明
A[i][0]: i零件在车床M1开始加工时间； A[i][1]: i零件在车床M1加工结束时间； B[i][0]: i零件在车床M2开始加工时间； B[i][1]: i零件在车床M2加工结束时间； C[i][0]: i零件在车床M3开始加工时间； C[i][1]: i零件在车床M3加工结束时间； M:加工十个零件模型的总时间 M1[10]:A-J零件在M1所需时间； M2[10]:A-J零件在M1所需时间； M3[10]:A-J零件在M1所需时间；
A-J零件加工顺序 A-J分别用0-9表示。 Z[10]：；Z[10]为0-9一种排序,即A-J零件的加工顺序。
五、模型的建立
1.由问题分析可知第i个加工零件在M1中： 初始时间A[0][0]=0；
其余初始时间为上一个零件完成时间A[i][0]= A[i-1][0] 第i个零件完成时间：A[i][1]+ A[i][0]+ M1[Z[i]]; 2.由问题分析可知第i个加工零件在M2中：
初始时间为在第一个零件在M1的完成时间即：B[0][0]=A[0][1]；
其余初始时间为i-1个零件在M2的完成时间和i个零件在M1完成时间的最大值，即：B[i][0]= max（B[i-1][0]，A[i][1]）
第i个零件完成时间：B[i][1]+ B[i][0]+ M2[Z[i]]; 3.由问题分析可知第i个加工零件在M3中：
初始时间为在第一个零件在M2的完成时间即：C[0][0]=B[0][1]；
其余初始时间为i-1个零件在M3的完成时间和i个零件在M2完成时间的最大值，即：C[i][0]= max（C[i-1][0]，B[i][1]）
第i个零件完成时间：C[i][1]+ C[i][0]+ M3[Z[i]]; 4.各个零件加工时间之和：
M= (C[0][1]-A[0][0])+ (C[1][1]-A[1][0])+…+(C[9][1]-A[9][0])
根据不同的加工顺序，即不同的z[10]序列,得出最小的M,而z[10]中数据即为所求加工顺序。
六、模型求解
通过用Vc++编程（附录1程序）求解，我们得出以下结论：总加工时间最短的加工顺序为：D－H-G－I－J－E－A－F－C－B，最短时间为413，具体结果 顺序M1加工时间M2加工时间分M3加工时间 零件号 (1)(2)号 XI（分钟） XI钟） 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 表1-1 完成M1工序总完成M3工序总顺序完成M2工序总零件号 时间MI(1)（分时间MI(3)（分(2号 时间MI（分钟） 钟） 钟） 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 总时间：413 表1-2 由表6-1可知，我们可以排出各个零件加工的起止时间表，如下表所示： 起止时间表：
工序 号 起 止 时 顺 间 序 D H G I J E A F C B 机床等待时间： M1 M2 M3 8:00-8:08 8：08-8:24 8:24-8:35 8:35-8:50 8:50-9:03 9:03-9:12 9:12-9:25 9:25-9:44 9:44-10:04 10:04-10:14 8:08-8:18 8:24-8:33 8:35-8:51 8:51-9:03 9:03-9:10 9:12-9:26 9:26-9:41 9:44-10:04 10:04-10:20 10:20-10:40 8：18-8:24 8:33-8:51 8:51-9:03 9:03-9:10 9:10-9:19 9:26-9:39 9:41-10:01 10:04-10:18 10:20-10:35 10:40-10:58 等 工 待 序 时 号 间 顺 序 号 M1 M2 M3 D 0 0 0 H 0 6 9 G 0 2 0 I 0 0 0 J 0 0 0 E 0 2 7 A 0 0 2 F 0 3 3 C 0 0 2 B 0 0 5 针对问题三： 若零件加工还要满足下面条件，零件D必须在零件E之前加工；零件H与零件J的加工必须相连；机床M3加工每个零件等待时间不能超过5分钟，总等待时间
不能超过30分钟，我们还用此类似模型进行求解。唯一不同的是:该模型要满足上述要求， 从附录程序2的运行情况可知，最优的零件排序为G－I-D－H－J－E－A－F－C－B；完成这批零件加工任务所需的最省总时间为425分钟. 起止时间表：
工序 号 起 止 时 顺 间 序 G I D H J E A F C B 机床等待时间： M1 M2 M3 8:00-8:11 8：11-8:26 8:26-8:34 8:34-8:50 8:50-9:03 9:03-9:12 9:12-9:25 9:25-9:44 9:44-10:04 10:04-10:14 M1 8:11-8:27 8:27-8:39 8:39-8:49 8:50-8:59 9:03-9:10 9:12-9:26 9:26-9:41 9:44-10:04 10:04-10:20 10:20-10:40 M2 8：27-8:39 8:39-8:46 8:49-8:55 8:59-9;17 9:17-9:26 9:26-9:39 9:41-10:01 10:04-10:18 10:20-10:35 10:40-10:58 M3 等 工 待 序 时 号 间 顺 序 号 G I D H J E A F C B 0 0 0 0 0 0 0 0 0 0 0 0 0 1 4 2 0 3 0 0 0 0 3 4 0 0 2 3 2 5 七、模型评价
在本题的解答过程中所建立的数学规划模型中，我们始终围绕一种化整为零的数学思，根据各零件在加工过程中加工时间和总时间之间的联系，寻求各零件加工总时间的具体算法。再利用Lingo软件进行求解模型，得出零件的最优排序。其中逻辑严谨，论证充分，算法简洁准确。有效地提高了软件求解效率。
由于零件的生产与加工要受很多因素的影响，我们建立的模型中还有很多我们未考虑到的因素，对现实生活中的零件生产与加工的的排序问题影响不大，不适合全面推广。
八、参考文献
零件的加工排序的最优模型c编程
