论文-工件的加工次序.doc

姓名：杨鑫磊 高鑫 高震 专业：计算机科学与技术工件的加工次序摘要 本文讨论的是如何安排工件的加工顺序使得工件加工时间总和最小、机床加工时间总和最小以及加工工件的总补偿费用最低三个问题。 本文运用了非线性规划解决了工件加工时间总和最小的问题，建立了模型，结合多个约束条件，使用lingo软件做线性规划得出工件加工顺序：加工时间最小和为2588。运用哈米尔顿图原理解决了机床加工总时间最小的问题，使用lingo软件做非线性规划得出加工顺序为： 机床最小总加工时间为459。运用线性规划原理解决了加工工件总补偿费用最小问题，建立了模型，结合约束条件，使用lingo软件做线性规划处理得出工件加工顺序为：最小补偿费 14242。关键字：线性规划 哈密尔顿图 一、问题重述现有14件工件等待在一台机床上加工，某些工件的加工必须安排在另一些工件完工以后才能开始。第号工件的加工时间及先期完工的工件号用下表给出：工件号12345678910111213142028251642123210242040243616前期工号3,45,7,85,9-10,113,8,943,5,74-4,76,7,145,121,2,6 （1）若给出一个加工顺序，则确定了每个工件的完工时间（包括等待与加工两个阶段）。 试设计一个满足条件的加工顺序，使各个工件的完工时间之和达到最小。 （2）假若第号工件紧接着第号工件后开工，机床需要花费的准备时间是， 试设计一个满足条件的加工顺序，使机床花费的总时间最小。 （3）假定工件的完工时间（包括等待与加工两个阶段）超过一确定时限,则需支付一定的补偿费用，其数值等于超过时间与费率之乘积（各个工件补偿率, 见下表）。 1234567891011121314121015161011108541010812试在=100，=0，安排一个加工顺序，使的总补偿费用最小。二、符号说明为第号工件加工顺序编号；为各个工件的完工时间之和；为机床需要花费的总时间；为补偿费；表示从工件i到工件j的准备时间；是0-1变量，表示是否选取直接从加工第i号工件接替到加工第j号工件这一顺序，1表示选取了，0表示为选取；其中以上3、 模型假设1、 假设机床在加工工件时不会出现问题。2、 假设每个工件可以反复使用。3、 假设加工各个工件之间的时间是连续的。4、 假设不会发生意外情况（机器坏掉、加工的工件不能正常使用等）。4、 模型的建立与求解问题一:试设计一个满足条件的加工顺序，使各个工件的完工时间之和最小。总的完工时间包括各工件的等待时间之和与各工件的加工时间之和。由于各工件的加工时间之和是一定的，所以完工时间之和最小的最优顺序问题等价于各工件等待时间总和的最优化问题。1） 模型建立设第个工件的加工次序为，总的完工时间为。每个工件都被其后置加工工件所等待，因此，总的工件等待时间即每个工件被等待的时间总和。第个工件被等待的时间为，则所有工件被等待的时间。所有工件的加工时间为： 。因此总的完工时间之和为： 2） 约束条件分析由题目中的次序表可以看出各零件的生产某工件与其前期工件的生产次序，可得对于生产次序的的相关约束：(为正整数且=1,2,3.14)y1y3;y1y4;Y2y5;y2y7;y2y8;.y14y1;y14y2;y14y6;3） 使用lingo软件编程对该题进行运算求解， 得出工件加工顺序最佳的方案为：图1的最优解为： 问题二：机床花费总时间包括机床的总准备时间和总的工件加工时间。总的工件加工时间是一定的，因此解决机床花费总时间最短问题等价于机床准备总时间的最优化问题。本模型将此问题转化为图论中的遍历哈密顿链问题。构造图如下：图2图中的顶点表示加工工件号，黑线表示规定的加工先后顺序，有向弧的权用 表示从节点i(表示加工工件i)到节点j(表示加工工件j)的准备时间。是0-1变量，表示是否选取加工第i号工件后紧接着加工第j号工件这一路径。现要求求得一种加工顺序，使得机床的总等待时间最短。转换为图论问题即是寻找一条最短路径，并满足如下要求：1）该路径经过所有节点一次且仅一次，且无环，因此路径数目要比节点数目少1；2）该路径经过工件i所代表的节点时，必须已经经过工件i的所有前置节点。根据图1与图2，3号工件必定是排在第7个序号上，13号工件必定排在最后一个加工序号上，同理，12号工件必定是倒数第二个被加工，14号工件必定是倒数第三个被加工。因此问题简化为找到图3、图4这两部分的最优加工顺序。建立模型为：St. 本模型求解为：4711109538621141213所需机床花费总时间最短为 ： 问题三： 本问题主要研究如何给出一个加工顺序使得总补偿费最小。(1) 目标函数分析变量说明:表示第j个工件的完工时间（包括等待与加工两个阶段）j=1,214表示确定时限，题目中给的值为100表示第 j个工件的完工时间超过了确定时限u 表示第j 个工件的完工时间没有超过了确定时限u j=1,214表示第 j个工件的补偿费率根据题目要求，只有超过了确定时限的工件才需要支付补偿费用，由此可以得到目标函数为： （2） 约束条件分析根据题目给出的表中可以得知各工件之间的关系（1.2），由此也可以得到各工件完工时间之间的关系（1.3）。由分析知道工件3的完工时间为199，工件14的完工时间为285，工件12的完工时间为309，工件13的完工时间为345，因此工件3以后完工的工件的完工时间都会超过确定时限 u，则（ 为工件3以后完工的工件号，包括工件3）；而不管安排怎样的加工顺序工件4的完工时间都不会超过 u，则；对于工件5，它加工之前工件4、7、11、10必须完工，因此工件5的完工时间至少为108，也超过了确定时限 u，则；对于工件7，它最多排在工件4、9、10的后面，因此它的完工时间最多为92，不超过 u，则；对于工件9、10、11，它们可能超过也可能不超过确定时限，这只能根据加工的顺序来得到的值。工件的完工时间与工件的加工顺序之间的关系为（1.5），由问题一可知。(3) 总补偿费最少模型的建立基于上面的分析，以（1.1）为目标函数，以（1.2）、（1.3）、（1.4）、（1.5）为约束条件建立模型： 1.2 1.3 1.4（4）模型的求解经过化简后，目标函数中只剩下几个未知变量，根据lingo软件可以得出结果。总补偿费最小的加工顺序为： 总补偿费为：142.24。根据题目给出的表中可以得知各工件之间的关系（1.2），由此也可以得到各工件完工时间之间的关系（1.3）。由分析知道工件3的完工时间为199，工件14的完工时间为285，工件12的完工时间为309，工件13的完工时间为345，因此工件3以后完工的工件的完工时间都会超过确定时限u ，则（ 为工件3以后完工的工件号，包括工件3）；而不管安排怎样的加工顺序工件4的完工时间都不会超过 u，则；对于工件5，它加工之前工件4、7、11、10必须完工，因此工件5的完工时间至少为108，也超过了确定时限 u，则；对于工件7，它最多排在工件4、9、10的后面，因此它的完工时间最多为92，不超过 ，则 ；对于工件9、10、11，它们可能超过也可能不超过确定时限，这只能根据加工的顺序来得到的值。5、 模型评价优点：1、模型结构简单，可读性强,容易操作。2、模型采用先进算法，利用最优模型，经验证正确率较高，具有很好的通用性 和推广性。3、模型的建立过程科学严谨，采用专业的计算软件，可信度较高。4、原创性很强，文章中的大部分模型都是自行推导建立的；5、建立的模型能与实际紧密联系，结合实际情况对问题进行求解，使得模型具有很好的通用性和推广性；缺点：1、在问题5的求解过程中，工件加工时限是人为确定的，缺少理论依据。2、论文总体把握不是太好，论文格局安排还有待改进。六、参考文献1 谢金星，薛毅，优化建模与软件，北京：清华大学出版社，20072 孙惠泉，图论及其应用，北京：科学出版社，20063 邦詹森，.古庭，有向图的理论算法及其应用，北京：科学出版社，2009附录：问题一：model:sets:time/1.14/:t,y;endsetsmin=sum(time(j):(14-y(j)*t(j);x1=y1+1;x2=y2+1;x3=y3+1;x4=y4+1;x5=y5+1;x6=y6+1;x7=y7+1;x8=y8+1;x9=y9+1;x10=y10+1;x11=y11+1;x12=y12+1;x13=y13+1;x14=y14+1;y(1)-y(3)=1;y(1)-y(4)=1;y(2)-y(8)=1;y(2)-y(7)=1;y(2)-y(5)=1;y(3)-y(5)=1;y(3)-y(9)=1;y(5)-y(10)=1;y(5)-y(11)=1;y(6)-y(8)=1;y(6)-y(3)=1;y(6)-y(9)=1;y(7)-y(4)=1;y(8)-y(3)=1;y(8)-y(5)=1;y(8)-y(7)=1;y(9)-y(4)=1;y(11)-y(7)=1;y(11)-y(7)=1;y(12)-y(14)=1;y(12)-y(7)=1;y(12)-y(6)=1;y(13)-y(5)=1;y(13)-y(12)=1;y(14)-y(1)=1;y(14)-y(2)=1;y(14)-y(6)=1;sum(time(j):y(j)=91;for(time(j):gin(y(j);data:t=20 28 25 16 42 12 32 10 24 20 40 24 36 16;enddatasqrt(y(6)-y(2)2)10(-1);sqrt(y(1)-y(6)2)10(-1);sqrt(y(1)-y(2)2)10(-1);sqrt(y(1)-y(8)2)10(-1);sqrt(y(5)-y(9)2)10(-1);sqrt(y(11)-y(9)2)10(-1);sqrt(y(7)-y(9)2)10(-1);sqrt(y(11)-y(10)2)10(-1);sqrt(y(7)-y(10)2)10(-1);sqrt(y(4)-y(10)2)10(-1);sqrt(y(9)-y(10)2)10(-1);end问题二：model:sets:time/1.14/:U;matrix(time,time):w,x;endsetsmin=sum(time(i):sum(time(j):w(i,j)*x(i,j);for(time(i):sum(time(j):x(i,j)=1);for(time(i):sum(time(j):x(j,i)=1);for(time(i):for(time(j):bin(x(i,j);sum(time(i):sum(time(j):x(i,j)=13;data:w=5000 3 5000 5000 5000 7 5000 9 5000 5000 5000 5000 5000 15 2 0 5000 5000 5000 8 5000 5000 5000 5000 5000 5000 5000 16 4 5000 0 5000 5000 5000 5000 11 5000 5000 5000 5000 5000 5000 5000 5000 5000 0 5000 5000 11 5000 13 14 5000 5000 5000 5000 5000 5000 4 5000 0 5000 5000 5000 14 5000 5000 5000 5000 5000 10 8 5000 5000 5000 0 5000 5000 5000 5000 5000 5000 5000 20 5000 5000 5000 5000 5000 5000 0 5000 16 17 18 5000 5000 5000 14 12 5000 5000 5000 4 5000 0 5000 5000 5000 5000 5000 5000 5000 5000 12 5000 8 5000 4 5000 0 19 20 5000 5000 5000 5000 5000 5000 12 10 5000 6 5000 2 0 21 5000 5000 5000 500