关于零件加工排序问题的数学模型、

摘要：

根据问题“建立模型求出使总加工时间最短的加工顺序”可知，本题为建立最优化模型，求出零件加工时间最短的加工顺序。

本题根据已知数据，结合问题中的具体要求，我们引入0/1变量建立工件排序的数学规划模型。借助Lingo软件进行求解运算，得出其中的最优排序方案。使得完成这批工件加工任务所需要的总时间最省。在这里，我们通过对各个工件（排序后）完成某项特定工序所需总时间进行求和得到整个加工任务所需要的总时间。而各工件的总时间包括其机床加工时间和加工其他零件时的等待时间。

最后，根据我们建立的模型求解得出某塑料厂加工十个零件模型所需最短总加工时间为943分钟，总加工时间最短的加工顺序为：4－5－10－7－8－2－9－1－6－3，具体结果如表6-1，6-2。

- 1 -

一、问题重述

某塑料厂要加工十个零件模型(编号为1，2，…，10),这些零件模型必须依次通过3个设备C1,C2,C3，每个设备一次只能加工一个零件，其加工时间如下表(单位：分钟)。

1 2 3 4 5 6 7 8 9 10 C1 13 10 20 8 9 19 11 16 15 13 C2 15 20 16 10 14 20 16 9 12 7 C3 20 18 15 6 13 14 12 18 7 9 试建立模型求出使总加工时间最短的加工顺序。

二、问题分析

零件在C1工序上的总加工时间是固定的。关键是在C2及C3工序上会出现等待。如果采用不同序加工,那么在C1上已加工好的零件,在C2上加工的时间会落到在C1上比其后加工的零件的后面,则其在C2上等待的时间更长,同样在C2与C3工序上也是这样，要求加工时间最短的加工顺序，就必须尽量减少工件在C2及C3工序上的等待时间，由于工件必须在它们要求的时间内完工，即某工件在任务开始起到该工件加工完毕之间所用的总时间应少于该工件的规定完工时间。所以要使整个加工任务的工件总价值最大，必须合理选择加工工件的种类及其加工的次序。

三、模型假设

假设一：在后面的模型中，我们都假定了忽略工件在转换工序时的运输时间。即将整个工件加工过程简化为一个连续的过程，只考虑机床在加工工件时其他工件的等待时间。

假设二：零件之间是相互独立的,从生产的角度看,先加工一个零件并不影响对后面零件的加工。不象有些流水线生产那样,存在固定的加工顺序。

假设三：工人都是熟练工人,零件在工序上的加工时间是固定不变的,与工人的操作水平无关。

假设四：零件在三个工序上采有同顺序加工,即在工序C1上的加工顺序与在C2及C3工序上的加工顺序相同。在工序C1上的加工是连续不断的。

四、符号说明

Xi(1)Xi(2)

：i工件在车床C1加工所需时间 ：i工件在车床C2加工所需时间

- 2 -

Xi(3)Mi(1)Mi(2)Mi(3)Mi(2)1Mi(3)1：i工件在车床C3加工所需时间 ：i工件完成在C1加工的总时间 ：i工件完成在C2加工的总时间 ：i工件完成在C3加工的总时间

：（i1）工件完成在C2加工的总时间（i1） ：（i1）工件完成在C3加工的总时间（i1）

M: 加工十个零件模型的总时间

五、模型的建立

由问题分析可知工件i在C1工序完成的时间：

(1)Mi(1)Mi(1)1Mi （1）

(2)MM对于工件i在C1工序完成的时间i与（i1）工件完成在C2加工的总时间i1，

要分两种情况分析：

1）当

(1)Mi(1)Mi(2)1时，即i工件完成C1工序的总时间大于或等于（i1）工件完成C2

工序的总时间，此时i工件不需要等待（i1）工件而立即就进入钻工序，因此i工件完成C2工序的总时间表达式为

2) 当

Mi(2)Mi(1)Mi(2);

Mi(1)Mi21时，即i工件完成C1工序的总时间小于或等于（i1）工件完成C2

工序的总时间，此时i工件需要等待（i1）工件完成C2工序才能进入C2加工。因此i工件完成C2工序的总时间表达式为

(2)Mi(2)Mi(2)1Xi。

综合以上两种情况，得到i工件完成C2工序的总时间计算公式为:

(2)Mi(2)Max(Mi(1),Mi(2)1)Xi(i1) （2）

M同理：对于工件i在C2工序完成的时间i与（i1）工件完成在C3加工的总时间Mi(3)1，有i工件完成C3工序的总时间计算公式为:

(2) - 3 -

(3)Mi(3)Max(Mi(2),Mi(3)1)Xi(i1) （3）

综合（1）（2）（3）可得加工十件零件需要的总时间为：

MM约束条件：

(3)1Max(Mi(2),Mi(3)Xi(3))i210

s..txj110ij1,(i1,2,3,...,10)

xi110ij1,(j1,2,3,...,10)

xij0,1

（Lingo编程：附录（wenti.lg4）文件）

六、模型求解

通过用Lingo编程求解，我们得出以下结论： 顺序号 1 2 3 4 5 6 7 8 9 10 工件号 4 5 10 7 8 2 9 1 6 3 C1加工时间8 9 13 11 16 10 15 13 19 20 Xi(1)C2加工时间10 14 7 16 9 20 12 15 20 16 Xi(1)C3加工时间6 13 9 12 18 18 7 20 14 15 Xi(1)（分钟） （分钟） （分钟）

表6-1

- 4 -

顺序号 1 2 3 4 5 6 7 8 9 10 工件号 4 5 10 7 8 2 9 1 9 3 完成C1工序总时间M（分钟） 8 17 30 41 57 67 82 95 114 134 (1)i完成C2工序总时间M（分钟） 18 32 39 57 66 87 99 114 134 150 (2)i完成C3工序总时间Mi（分钟） 24 45 54 69 87 105 112 134 148 165 总时间：943 (3) 表6-2

从软件的运行情况可知，最优的工件排序为4－5－10－7－8－2－9－1－6－3；完成这

批工件加工任务所需的最省总时间为943分钟。

七、模型评价

在本题的解答过程中所建立的数学规划模型中，我们始终围绕一种化整为零的数学思想，将整批工件的加工任务拆分为在最优的排序下每个工件的实际加工情况来分析，根据各工件在加工过程中加工时间和总时间之间的联系，寻求各工件加工总时间的具体算法。再利用Lingo软件进行求解模型，得出工件的最优排序。其中逻辑严谨，论证充分，算法简洁准确。有效地提高了软件求解效率。

由于零件的生产与加工要受很多因素的影响，我们建立的模型中还有很多我们未考虑到的因素，对现实生活中的零件生产与加工的的排序问题影响不大，不适合全面推广。

x11x21x31x41Xx51x61...x101

x12x22x32x42x52x62...x102x13x23x33x43x53x63...x103x14x24x34x44x54...............x64.........x104...x110x210x310x410 x510x610...x1010- 5 -

八、参考文献

[1]颜文勇，数学建模，高等教育出版社，北京，2011.6

[2] http://wenku.baidu.com/view/66c42373f242336c1eb95ee9.html [3] http://wenku.baidu.com/view/63bfcf3410661ed9ad51f391.html [4] http://wenku.baidu.com/view/4199d2be960590c69ec376b2.html

九、附录

wenti.lg4：

model: sets:

linjian/g1..g10/:c1_shijian,c2_shijian,c3_shijian;

shunxu/s1..s10/:c1_time,c2_time,c3_time,c1_fintime,c2_fintime,c3_fintime; links(shunxu,linjian):note; endsets

min=@sum(shunxu(I):c3_fintime(I));

@for(shunxu(I):c1_time(I)=@sum(linjian(J):c1_shijian(J)*note(I,J));); @for(shunxu(I):c2_time(I)=@sum(linjian(J):c2_shijian(J)*note(I,J));); @for(shunxu(I):c3_time(I)=@sum(linjian(J):c3_shijian(J)*note(I,J));); @for(shunxu(I):

@sum(linjian(J): note(I,J))=1;); @for(linjian(J):

@sum(shunxu(I): note(I,J))=1;); @for(shunxu(I):

C1_fintime(I)=@sum(shunxu(J)|J#le#I:C1_time(J));); @for(shunxu(I)| I#gt#1:

C2_fintime(I)=@if(C1_fintime(I)#ge#C2_fintime(I-1),C1_fintime(I),C2_fintime(I-1))+C2_time(I););

C2_fintime(1)=C1_fintime(1)+C2_time(1); @for(shunxu(I)| I#gt#1:

C3_fintime(I)=@if(C2_fintime(I)#ge#C3_fintime(I-1),C2_fintime(I),C3_fintime(I-1))+C3_time(I););

C3_fintime(1)=C2_fintime(1)+C3_time(1);

@for(links:@bin(note));

data:@OLE('D:\\liebiao.XLS')=c1_time,c2_time,c3_time,c1_fintime,c2_fintime,c3_fintime;

- 6 -

c1_shijian=13,10,20,8,9,19,11,16,15,13; c2_shijian=15,20,16,10,14,20,16,9,12,7; c3_shijian=20,18,15,6,13,14,12,18,7,9; enddata end

Feasible solution found.

Objective value: 943.0000 Extended solver steps: 157 Total solver iterations: 141457

Export Summary Report ---------------------

Transfer Method: OLE BASED Workbook: D:\\liebiao.XLS Ranges Specified: 6 C1_TIME C2_TIME C3_TIME C1_FINTIME C2_FINTIME C3_FINTIME

Ranges Found: 0 Range Size Mismatches: 0 Values Transferred: 0

Variable Value C1_SHIJIAN( G1) 13.00000 C1_SHIJIAN( G2) 10.00000 C1_SHIJIAN( G3) 20.00000 C1_SHIJIAN( G4) 8.000000 C1_SHIJIAN( G5) 9.000000 C1_SHIJIAN( G6) 19.00000 C1_SHIJIAN( G7) 11.00000 C1_SHIJIAN( G8) 16.00000 C1_SHIJIAN( G9) 15.00000

- 7 -

C1_SHIJIAN( G10) 13.00000 C2_SHIJIAN( G1) 15.00000 C2_SHIJIAN( G2) 20.00000 C2_SHIJIAN( G3) 16.00000 C2_SHIJIAN( G4) 10.00000 C2_SHIJIAN( G5) 14.00000 C2_SHIJIAN( G6) 20.00000 C2_SHIJIAN( G7) 16.00000 C2_SHIJIAN( G8) 9.000000 C2_SHIJIAN( G9) 12.00000 C2_SHIJIAN( G10) 7.000000 C3_SHIJIAN( G1) 20.00000 C3_SHIJIAN( G2) 18.00000 C3_SHIJIAN( G3) 15.00000 C3_SHIJIAN( G4) 6.000000 C3_SHIJIAN( G5) 13.00000 C3_SHIJIAN( G6) 14.00000 C3_SHIJIAN( G7) 12.00000 C3_SHIJIAN( G8) 18.00000 C3_SHIJIAN( G9) 7.000000 C3_SHIJIAN( G10) 9.000000 C1_TIME( S1) 8.000000 C1_TIME( S2) 9.000000 C1_TIME( S3) 13.00000 C1_TIME( S4) 11.00000 C1_TIME( S5) 16.00000 C1_TIME( S6) 10.00000 C1_TIME( S7) 15.00000 C1_TIME( S8) 13.00000 C1_TIME( S9) 19.00000 C1_TIME( S10) 20.00000 C2_TIME( S1) 10.00000 C2_TIME( S2) 14.00000 C2_TIME( S3) 7.000000 C2_TIME( S4) 16.00000 C2_TIME( S5) 9.000000 C2_TIME( S6) 20.00000 C2_TIME( S7) 12.00000 C2_TIME( S8) 15.00000 C2_TIME( S9) 20.00000 C2_TIME( S10) 16.00000 C3_TIME( S1) 6.000000 C3_TIME( S2) 13.00000 C3_TIME( S3) 9.000000

- 8 -

C3_TIME( S4) 12.00000 C3_TIME( S5) 18.00000 C3_TIME( S6) 18.00000 C3_TIME( S7) 7.000000 C3_TIME( S8) 20.00000 C3_TIME( S9) 14.00000 C3_TIME( S10) 15.00000 C1_FINTIME( S1) 8.000000 C1_FINTIME( S2) 17.00000 C1_FINTIME( S3) 30.00000 C1_FINTIME( S4) 41.00000 C1_FINTIME( S5) 57.00000 C1_FINTIME( S6) 67.00000 C1_FINTIME( S7) 82.00000 C1_FINTIME( S8) 95.00000 C1_FINTIME( S9) 114.0000 C1_FINTIME( S10) 134.0000 C2_FINTIME( S1) 18.00000 C2_FINTIME( S2) 32.00000 C2_FINTIME( S3) 39.00000 C2_FINTIME( S4) 57.00000 C2_FINTIME( S5) 66.00000 C2_FINTIME( S6) 87.00000 C2_FINTIME( S7) 99.00000 C2_FINTIME( S8) 114.0000 C2_FINTIME( S9) 134.0000 C2_FINTIME( S10) 150.0000 C3_FINTIME( S1) 24.00000 C3_FINTIME( S2) 45.00000 C3_FINTIME( S3) 54.00000 C3_FINTIME( S4) 69.00000 C3_FINTIME( S5) 87.00000 C3_FINTIME( S6) 105.0000 C3_FINTIME( S7) 112.0000 C3_FINTIME( S8) 134.0000 C3_FINTIME( S9) 148.0000 C3_FINTIME( S10) 165.0000 NOTE( S1, G1) 0.000000 NOTE( S1, G2) 0.000000 NOTE( S1, G3) 0.000000 NOTE( S1, G4) 1.000000 NOTE( S1, G5) 0.000000 NOTE( S1, G6) 0.000000 NOTE( S1, G7) 0.000000

- 9 -

NOTE( S1, G8) 0.000000 NOTE( S1, G9) 0.000000 NOTE( S1, G10) 0.000000 NOTE( S2, G1) 0.000000 NOTE( S2, G2) 0.000000 NOTE( S2, G3) 0.000000 NOTE( S2, G4) 0.000000 NOTE( S2, G5) 1.000000 NOTE( S2, G6) 0.000000 NOTE( S2, G7) 0.000000 NOTE( S2, G8) 0.000000 NOTE( S2, G9) 0.000000 NOTE( S2, G10) 0.000000 NOTE( S3, G1) 0.000000 NOTE( S3, G2) 0.000000 NOTE( S3, G3) 0.000000 NOTE( S3, G4) 0.000000 NOTE( S3, G5) 0.000000 NOTE( S3, G6) 0.000000 NOTE( S3, G7) 0.000000 NOTE( S3, G8) 0.000000 NOTE( S3, G9) 0.000000 NOTE( S3, G10) 1.000000 NOTE( S4, G1) 0.000000 NOTE( S4, G2) 0.000000 NOTE( S4, G3) 0.000000 NOTE( S4, G4) 0.000000 NOTE( S4, G5) 0.000000 NOTE( S4, G6) 0.000000 NOTE( S4, G7) 1.000000 NOTE( S4, G8) 0.000000 NOTE( S4, G9) 0.000000 NOTE( S4, G10) 0.000000 NOTE( S5, G1) 0.000000 NOTE( S5, G2) 0.000000 NOTE( S5, G3) 0.000000 NOTE( S5, G4) 0.000000 NOTE( S5, G5) 0.000000 NOTE( S5, G6) 0.000000 NOTE( S5, G7) 0.000000 NOTE( S5, G8) 1.000000 NOTE( S5, G9) 0.000000 NOTE( S5, G10) 0.000000 NOTE( S6, G1) 0.000000

- 10 -

NOTE( S6, G2) 1.000000 NOTE( S6, G3) 0.000000 NOTE( S6, G4) 0.000000 NOTE( S6, G5) 0.000000 NOTE( S6, G6) 0.000000 NOTE( S6, G7) 0.000000 NOTE( S6, G8) 0.000000 NOTE( S6, G9) 0.000000 NOTE( S6, G10) 0.000000 NOTE( S7, G1) 0.000000 NOTE( S7, G2) 0.000000 NOTE( S7, G3) 0.000000 NOTE( S7, G4) 0.000000 NOTE( S7, G5) 0.000000 NOTE( S7, G6) 0.000000 NOTE( S7, G7) 0.000000 NOTE( S7, G8) 0.000000 NOTE( S7, G9) 1.000000 NOTE( S7, G10) 0.000000 NOTE( S8, G1) 1.000000 NOTE( S8, G2) 0.000000 NOTE( S8, G3) 0.000000 NOTE( S8, G4) 0.000000 NOTE( S8, G5) 0.000000 NOTE( S8, G6) 0.000000 NOTE( S8, G7) 0.000000 NOTE( S8, G8) 0.000000 NOTE( S8, G9) 0.000000 NOTE( S8, G10) 0.000000 NOTE( S9, G1) 0.000000 NOTE( S9, G2) 0.000000 NOTE( S9, G3) 0.000000 NOTE( S9, G4) 0.000000 NOTE( S9, G5) 0.000000 NOTE( S9, G6) 1.000000 NOTE( S9, G7) 0.000000 NOTE( S9, G8) 0.000000 NOTE( S9, G9) 0.000000 NOTE( S9, G10) 0.000000 NOTE( S10, G1) 0.000000 NOTE( S10, G2) 0.000000 NOTE( S10, G3) 1.000000 NOTE( S10, G4) 0.000000 NOTE( S10, G5) 0.000000

- 11 -

NOTE( S10, G6) 0.000000 NOTE( S10, G7) 0.000000 NOTE( S10, G8) 0.000000 NOTE( S10, G9) 0.000000 NOTE( S10, G10) 0.000000

Row Slack or Surplus 1 943.0000 2 0.000000 3 0.000000 4 0.000000 5 0.000000 6 0.000000 7 0.000000 8 0.000000 9 0.000000 10 0.000000 11 0.000000 12 0.000000 13 0.000000 14 0.000000 15 0.000000 16 0.000000 17 0.000000 18 0.000000 19 0.000000 20 0.000000 21 0.000000 22 0.000000 23 0.000000 24 0.000000 25 0.000000 26 0.000000 27 0.000000 28 0.000000 29 0.000000 30 0.000000 31 0.000000 32 0.000000 33 0.000000 34 0.000000 35 0.000000 36 0.000000 37 0.000000

- 12 -

38 0.000000 39 0.000000 40 0.000000 41 0.000000 42 0.000000 43 0.000000 44 0.000000 45 0.000000 46 0.000000 47 0.000000 48 0.000000 49 0.000000 50 0.000000 51 0.000000 52 0.000000 53 0.000000 54 0.000000 55 0.000000 56 0.000000 57 0.000000 58 0.000000 59 0.000000 60 0.000000 61 0.000000 62 0.000000 63 0.000000 64 0.000000 65 0.000000 66 0.000000 67 0.000000 68 0.000000 69 0.000000 70 0.000000 71 0.000000 72 0.000000 73 0.000000 74 0.000000 75 0.000000 76 0.000000 77 0.000000 78 0.000000 79 0.000000 80 0.000000 81 0.000000

- 13 -