工件加工优秀论文

B题 工件加工

组号：14

执笔人：彭嘉续

B题 工件加工

摘要

本文探讨的问题是如何安排工件的加工顺序以使得各工件的完工时间之和最短、机床花费的总时间最小、加工工件的总补偿费用最少。求解这一问题主要用到了图论和线性规划的数学方法。在第一问与第三问中，本文先将题中所给出的数据、条件转换为图，在此基础上表示出目标函数及约束条件，利用非线性规划求得最优解。第二问中，文本利用了图论中哈密顿链原理，将完成工件加工的问题转化为有向图中点的遍历，所建立的模型可遍历哈密顿链中的全部点且得到最短路径。

最终求解模型，结果如下：

(1) 加工顺序为4→10→9→7→11→5→3→8→6→1→2→14→12→13时，各工件的完工时间和最小，为2588。

(2) 加工顺序为4→7→11→10→9→5→3→8→6→2→1→14→12→13时，机床花费的总时间最小，为114。

(3) 加工顺序为4→7→11→10→5→9→3→8→6→1→2→14→12→13时，总补偿费最小，为142.42。

关键词：工件加工；非线性规划；图论；哈密顿链；最优化

1

一、问题重述与分析

1、问题重述

现有14件工件等待在一台机床上加工，某些工件的加工必须安排在另一些工件加工完工以后才能开始，第j号工件的加工时间tj及先期必须完工的工件号i由下表给出。 工件号j tj 0 前期工件号4 3,28 5,7,8 9 25 5,26 - 12 10,142 3,8,9 12 4 30 3,5,7 14 4 20 - 7 1 2 3 4 5 6 7 8 9 0 20 4,11 44 6,7,112 26 5,12 13 36 1,2,6 14 11（1） 若给出一个加工工序，则确定了每个工件的完工时间（包括等待与加工两个阶段）。试设计一个满足条件的加工顺序，使各工件的完工时间之和最小。 （2） 若第j号工件紧接着第i号工件完工后开工，机床需要花费的准备时间是：

ijij tij

2(ij)ij（3） 假定工件的完工时间（包括等待与加工两个阶段）超过一确定时限u时，则需支付一定的补偿费用，其数值等于超过时间与费用率之积，各工件的补偿费用率ωi如下： j ωi 1 12 2 10 3 15 4 16 5 10 6 11 7 10 8 8 9 5 10 4 11 10 12 10 13 8 14 12 u=100，tij=0，安排一个加工顺序，使总补偿最小。 2、问题分析

三个问题都是要求一种最优加工次序，使得工件完工时间和、机床花费时间、总补偿费分别达到最小。由于题中安排了各工件的前期工件，所以解题时可以先利用图论的知识将加工工件之间的先后关系表示出来。由于第j号工件完工时间和补偿费与其前置加工工件完工时间的累加密切相关，所以单纯用图论解决完工时间和补偿费的最优化是很复杂的，但是可以在有向图的基础上将目标函数、约

2

束条件巧妙表示出来，再结合非线性规划解出最优解。在第二问中，求得的是机床花费总时间的最小值问题，实质就是要解决机床的总准备时间最短的问题。该问题可转化为最短路径问题，但是同时要考虑到各加工工件的前期工件。这就需要构造一个好的有向图，再遍历点并求得最短路径。

二、模型假设与符号说明

1、模型假设

(1) 假设相邻工件之间的加工是紧挨着进行的，即除了准备时间外，不浪费任何时间。

(2) 假设机床在加工工件的过程中运转正常。 (3) 假设 2、符号说明

yi—第i号工件在加工流程中的加工序号 Z1—各工件完工时间之和 Z2—机床花费的总时间

Z3—加工时的总补偿费

wij—表示从节点i(表示加工工件i)到节点j(表示加工工件j)的准备时间。

xij—是0-1变量，表示是否选取直接从加工第i号工件接替到加工第j号工件这一顺序

0，表示选取了从加工i号工件到加工j号工件的顺序

xij1，表示不选取从加工i号工件到加工j号工件的顺序

三、模型建立与求解

1、总完工时间最优模型

问题1中要求根据各个工件的加工时间，以及其前期工件的要求，建立以总的完工时间最少为目标的目标函数。在加工时间一定的情况下，对其进行合理的排序，使目标函数达到最小值。

3

(1)模型建立

总的完工时间包括各工件的等待时间之和与各工件的加工时间之和。由于各工件的加工时间之和是一定的，所以完工时间最优问题等价于各工件等待时间总和的最优化问题。

设第i个工件的加工次序为yi，总的完工时间为Z1。

每个工件都被其后置加工工件所等待，因此，总的工件等待时间即每个工件被等待的时间总和。

第i个工件被等待的时间为(14-yi)ti，则所有工件被等待的时间为(14yi)ti

i114所有工件的加工时间为ti=345

i114因此总的完工时间之和为：Z1(14yi)titi(15yi)ti。

i1i1i1141414(2) 约束条件分析

设yi是yj的前期工件，则第i个工件的加工次序应早于第j个工件的加工次序，所以yiyj

由题目当中的表可得约束条件为：

y1-y31;y2-y81;y3-y51;y3-y91;y5-y101;y5-y111;y6-y81;y7-y41;y8-y31;y9-y41;y11-y71;y12-y141;y13-y121;y14-y11;y14-y21;y14-y61;(y10-y11)21;(y1-y2)21;(y1-y6)21;(y2-y6)21;y13=14;y4=1;

yi均为正整数，i=1,2,3…14。 (3) 相关图形

由题目中的表可作图如下：

4

9 3 4 5 7 11 10 图1 1 3 2 14 8 6 图2 12 13

(4) 模型求解

这是一个最优化问题，由于变量和约束条件都很多，人工求解有一定困难，因此可以借助lingo软件，求解得到最佳加工顺序和最少总完工时间。

在lingo软件中求解的部分代码：

MIN=5175-20*y1-28*y2-25*y3-16*y4-42*y5-12*y6-32*y7-10*y8-24*y9-20*y10-40*y11-24*y12-36*y13-16*y14=0;（目标函数的表示）。 由lingo计算得使得总完工时间最短的最佳加工次序为：

4109711538612141213，

此时总完工时间为2588。

5

2、机床花费总时间最优模型 (1)模型建立

机床花费总时间包括机床的总准备时间和总的工件加工时间。总的工件加工时间是一定的，因此解决机床花费总时间最短问题等价于机床准备总时间的最优化问题。本模型将此问题转化为图论中的遍历哈密顿链问题。构造图如下

9 3 4 5 7 11 10 图3

1 3 8 2 14 12 13 6 图4

图中的顶点表示加工工件号，实线表示规定的加工先后顺序，如有向实线x49表示加工顺序应该是先加工了4号工件才能加工9号工件。有向虚线表示可以相邻加工的两个工件号，如虚线x59表示可以先加工5号工件，再紧接着加工9号

6

工件；x95表示可以先加工9号工件，再紧接着加工5号工件。有向弧的权用wij表示，wij表示从节点i(表示加工工件i)到节点j(表示加工工件j)的准备时间。 表示是否选取加工第i号工件后紧接着加工第j号工件这一xij—是0-1变量，路径。

0，表示选取了从加工i号工件到加工j号工件的顺序

xij，表示不选取从加工i号工件到加工j号工件的顺序

1

现要求求得一种加工顺序，使得机床的总等待时间最短。转换为图论问题即是寻找一条最短路径，并满足如下要求：

① 该路径经过所有节点一次且仅一次，且无环，因此路径数目要比节点数目少1；

② 该路径经过工件i所代表的节点时，必须已经经过工件i的所有前置节点。

根据图1，与图2，3号工件必定是排在第7个序号上，13号工件必定排在最后一个加工序号上，同理，12号工件必定是倒数第二个被加工，14号工件必定是倒数第三个被加工。因此问题简化为找到图3、图4这两部分的最优加工顺序。建立模型为：

Min zwijxij,i,j0,1...14

i1j11414s.t.

14xij1j0,1...14i114xij1i0,1...14 j1x0,1i,j0,1...14ij1414xij13i1j1(2) 模型求解 本模型用lingo求解： 对图一求解（代码见附录7.1）

7

求解结果为：4→7→11→10→9→5→3 所需机床花费总时间为45。 对图二求解（代码见附录7.2）：

求解结果为：3→8→6→2→1→14→12→13 所需机床花费总时间为69。 3、总补偿费最少模型

本问题主要研究如何给出一个加工顺序使得总补偿费最小。 (1) 目标函数分析

变量说明:xj 表示第j个工件的完工时间（包括等待与加工两个阶段）

j=1 214

u表示确定时限，题目中给的值为100

mj1表示第j个工件的完工时间超过了确定时限u j=1 214 mj0表示第j个工件的完工时间没有超过了确定时限u

j=1 214

wj表示第j个工件的补偿费率

根据题目要求，只有超过了确定时限的工件才需要支付补偿费用，由此可以得到目标函数为：MIN Z3mjwjxju （1.1）

j114(2) 约束条件分析

根据题目给出的表中可以得知各工件之间的关系（1.2），由此也可以得到各工件完工时间之间的关系（1.3）。由分析知道工件3的完工时间为199，工件14的完工时间为285，工件12的完工时间为309，工件13的完工时间为345，因此工件3以后完工的工件的完工时间都会超过确定时限u，则mj1（j为工件3以后完工的工件号，包括工件3）；而不管安排怎样的加工顺序工件4的完工时间都不会超过u，则m40；对于工件5，它加工之前工件4、7、11、10必须完工，因此工件5的完工时间至少为108，也超过了确定时限u，则m51；对于工件7，它最多排在工件4、9、10的后面，因此它的完工时间最多为92，不超过u，则m70；对于工件9、10、11，它们可能超过也可能不超过确定时限，

8

这只能根据加工的顺序来得到m9、m10、m11的值。

工件的完工时间xj与工件的加工顺序yi之间的关系为（1.5），由问题一可知。 (3) 总补偿费最少模型的建立

基于上面的分析，以（1.1）为目标函数，以（1.2）、（1.3）、（1.4）、（1.5）为约束条件建立模型

14MIN Z3mjwjxju

j1y1-y3>=1 y2-y8>=1 y3-y5>=1 y3-y9>=1 y5-y10>=1 y5-y11>=1 y6-y8>=1 y7-y4>=1 y8-y3>=1

（1.2） y9-y4>=1 y11-y7>=1 y12-y14>=1 y13-y12>=1 y14-y1>=1 y14-y2>=1 y14-y6>=1

x1>=219 m11

x2-x8>=28 m21 x5<=174 m31

x9<=174 m40 x5-x10>=42 m51 x5-x11>=42 m61

x6-x8>=12 m70x7-x4>=32 m81

x8>=209 （1.3） m121 x9-x4>=24 m131x11-x7>=40 m141 x1<=269 x2<=269 x6<=269 9

（1.4） x15yt （1.5）

jiij1i11414(4) 模型的求解

经过化简后，目标函数中只剩下x1、x2、x5、x6、x8、x9、x10、x11、m9、

m10、m11几个未知变量，根据lingo软件可以得出结果。总补偿费最小的加工顺序为4711105938612141213，总补偿费为142.24。

四、参考文献

[1] 谢金星 薛毅，优化建模与LINDO/LINGO软件，北京：清华大学出版社，2007年。

[2] 何坚勇，最优化方法，北京：清华大学出版社，2007年。 [3] 朱德通，最优化模型与实验，上海：同济大学出版社，2003年。 [4]（美）Mark M.Meerschaert，数学建模方法与分析，2009年。 [5] 刘育兴，钟剑，垃圾运输问题的模型及其求解，

http://wenku.baidu.com/view/12ae37b765ce0508763213d2.html，2006年

五、附录

1、问题（二）图一的代码

min=11*x47+13*x49+14*x410+12*x93+8*x95+4*x97+19*x910+20*x911+12*x104+10*x105+6*x107+2*x109+21*x1011+18*x711+16*x79+17*x710+12*x115+4*x119+2*x1110+4*x53+14*x59;

x47+x49+x410=1;x93+x95+x97+x910+x911=1;x105+x107+x109+x1011=1; x711+x79+x710=1;x115+x119+x1110=1;x53+x59=1;

x104=0;x410+x1110+x910+x710=1;x49+x109+x79+x119+x59=1; x47+x97+x107=1;x911+x1011+x711=1;x95+x105+x115=1; x93+x53=1;

x47+x49+x410+x93+x95+x97+x910+x911+x104+x105+x107+x109+x1011+x711+x79+x710+x115+x119+x1110+x53+x59=6;

10

@bin(x53);@bin(x59);

@bin(x910);@bin(x97);@bin(x1110);@bin(x109);@bin(x911);@bin(x107);@bin(x105);@bin(x104);@bin(x1011);@bin(x711);@bin(x79);@bin(x710);@bin(x115);@bin(x119);@bin(x47);@bin(x49);@bin(x93);@bin(x95);@bin(x410);

2、问题（二）图二的代码

min=4*x31+11*x38+9*x18+3*x12+7*x16+15*x114+14*x81+12*x82+4*x86+2*x21+8*x26+16*x214+10*x61+8*x62+20*x614;

x18+x16+x12+x114=1; x86+x82+x81=1;x62+x614+x61=1; x38+x31=1;x26+x214+x21=1;x31+x81+x21+x61=1; x38+x18=1;x12+x82+x62=1;x16+x86+x26=1; x114+x214+x614=1;

x31+x38+x18+x12+x16+x114+x81+x82+x86+x21+x26+x214+x61+x62+x614=5; @bin(x31);@bin(x38);@bin(x18);@bin(x12);@bin(x16);@bin(x114);@bin(x81);@bin(x82);@bin(x86);@bin(x21);@bin(x26);@bin(x214);@bin(x61);@bin(x62);@bin(x614);

11