数学建模 工件的加工次序问题PPT.ppt

工件的加工次序问题,孙瑜张成伟徐兆国,摘要,本文探讨的问题是如何安排工件的加工顺序以使得各工件的完工时间之和最短、机床花费的总时间最小、加工工件的总补偿费用最少。求解这一问题主要用到了图论和线性规划的数学方法。在第一问与第三问中，本文先将题中所给出的数据、条件转换为图，在此基础上表示出目标函数及约束条件，利用非线性规划求得最优解。第二问中，文本利用了图论中哈密顿链原理，将完成工件加工的问题转化为有向图中点的遍历，所建立的模型可遍历哈密顿链中的全部点且得到最短路径。,最终求解模型，结果如下：(1)加工顺序为4109711538612141213时，各工件的完工时间和最小，为2588。(2)加工顺序为4711109538621141213时，机床花费的总时间最小，为114。(3)加工顺序为4711105938612141213时，总补偿费最小，为142.42。(4)对u进行讨论，可分为以下几种情况:u=345,并进而用lingo可求出答案(5)把一般情况下上述各问题的解法进行的一些讨论。,问题重述与分析,现有14件工件等待在一台机床上加工，某些工件的加工必须安排在另一些工件加工完工以后才能开始，第j号工件的加工时间tj及先期必须完工的工件号i由下表给出。,1）若给出一个加工工序，则确定了每个工件的完工时间（包括等待与加工两个阶段）。试设计一个满足条件的加工顺序，使各工件的完工时间之和最小。2）若第j号工件紧接着第i号工件完工后开工，机床需要花费的准备时间是：3）假定工件的完工时间（包括等待与加工两个阶段）超过一确定时限u时，则需支付一定的补偿费用，其数值等于超过时间与费用率之积，各工件的补偿费用率i如下：u=100，tij=0，安排一个加工顺序，使总补偿最小。(4)试对(3)中的u进行讨论。(5)能否对一般情况下上述各问题的解法进行一些讨论。,问题分析,这五个问题都是要求一种最优加工次序，使得工件完工时间和、机床花费时间、总补偿费分别达到最小。由于题中安排了各工件的前期工件，所以解题时可以先利用图论的知识将加工工件之间的先后关系表示出来。由于第j号工件完工时间和补偿费与其前置加工工件完工时间的累加密切相关，所以单纯用图论解决完工时间和补偿费的最优化是很复杂的，但是可以在有向图的基础上将目标函数、约束条件巧妙表示出来，再结合非线性规划解出最优解。在第二问中，求得的是机床花费总时间的最小值问题，实质就是要解决机床的总准备时间最短的问题。该问题可转化为最短路径问题，但是同时要考虑到各加工工件的前期工件。这就需要构造一个好的有向图，再遍历点并求得最短路径。,模型假设,(1)假设相邻工件之间的加工是紧挨着进行的，即除了准备时间外，不浪费任何时间。(2)假设机床在加工工件的过程中运转正常。(3)假设不会发生意外情况（机器坏掉、加工的工件不能正常使用等。）,符号说明,第i号工件在加工流程中的加工序号各工件完工时间之和机床花费的总时间加工时的总补偿费表示从节点i(表示加工工件i)到节点j(表示加工工件j)的准备时间。是0-1变量，表示是否选取直接从加工第i号工件接替到加工第j号工件这一顺序，表示选取了从加工i号工件到加工j号工件的顺序，表示不选取从加工i号工件到加工j号工件的顺序表示第个工件的完工时间超过了确定时限uj=1,2.14表示第个工件的完工时间没有超过了确定时限uj=1,2.14,模型建立与求解,1、总完工时间最优模型问题1中要求根据各个工件的加工时间，以及其前期工件的要求，建立以总的完工时间最少为目标的目标函数。在加工时间一定的情况下，对其进行合理的排序，使目标函数达到最小值。,(1)模型建立总的完工时间包括各工件的等待时间之和与各工件的加工时间之和。由于各工件的加工时间之和是一定的，所以完工时间最优问题等价于各工件等待时间总和的最优化问题。设第个工件的加工次序为，总的完工时间为。每个工件都被其后置加工工件所等待，因此，总的工件等待时间即每个工件被等待的时间总和。第个工件被等待的时间为，则所有工件被等待的时间为所有工件的加工时间为因此总的完工时间之和为：,(2)约束条件分析设是的前期工件，则第个工件的加工次序应早于第个工件的加工次序，所以由题目当中的表可得约束条件为：均为正整数，i=1,2,314。,(3)相关图形由题目中的表可作图如下：,(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计算得使得总完工时间最短的最佳加工次序为：，此时总完工时间为2588。,2、机床花费总时间最优模型(1)模型建立机床花费总时间包括机床的总准备时间和总的工件加工时间。总的工件加工时间是一定的，因此解决机床花费总时间最短问题等价于机床准备总时间的最优化问题。本模型将此问题转化为图论中的遍历哈密顿链问题。构造图如下,图中的顶点表示加工工件号，实线表示规定的加工先后顺序，如有向实线表示加工顺序应该是先加工了4号工件才能加工9号工件。有向虚线表示可以相邻加工的两个工件号，如虚线表示可以先加工5号工件，再紧接着加工9号工件；表示可以先加工9号工件，再紧接着加工5号工件。有向弧的权用表示从节点i(表示加工工件i)到节点j(表示加工工件j)的准备时间。是0-1变量，表示是否选取加工第i号工件后紧接着加工第j号工件这一路径。，表示选取了从加工i号工件到加工j号工件的顺序，表示不选取从加工i号工件到加工j号工件的顺序,现要求求得一种加工顺序，使得机床的总等待时间最短。转换为图论问题即是寻找一条最短路径，并满足如下要求：该路径经过所有节点一次且仅一次，且无环，因此路径数目要比节点数目少1；该路径经过工件i所代表的节点时，必须已经经过工件i的所有前置节点。根据图1，与图2，3号工件必定是排在第7个序号上，13号工件必定排在最后一个加工序号上，同理，12号工件必定是倒数第二个被加工，14号工件必定是倒数第三个被加工。因此问题简化为找到图3、图4这两部分的最优加工顺序。建立模型为：Mins.t.,(2)模型求解本模型用求解：对图一求解求解结果为：471110953所需机床花费总时间为45。对图二求解求解结果为：38621141213所需机床花费总时间为69。,3、总补偿费最少模型本问题主要研究如何给出一个加工顺序使得总补偿费最小。(1)目标函数分析变量说明:表示第个工件的完工时间（包括等待与加工两个阶段）j=1,214u表示确定时限，题目中给的值为100表示第j个工件的完工时间超过了确定时限u表示第j个工件的完工时间没有超过了确定时限uj=1,214表示第j个工件的补偿费率根据题目要求，只有超过了确定时限的工件才需要支付补偿费用，由此可以得到目标函数为：Min（1.1）,(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）为约束条件建立模型,Min,(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，它们可能超过也可能不超过确定时限，这只能根据加工的顺序来得到的值。,4.对(3)中的u进行讨论。对u进行讨论，可以分为以下几种情况当u92时，所有工件加工时间都超过了时限，所有（j=1,2,3,5.）.由式（1.2），（.3）和mj的值。当92=u108，此情况与u=100相同，答案为总补偿费最小的加工顺序为总补偿费为142.24。当108=u174其他约束条件相同当174=U199其他约束条件相同,当199=U209当209=u219其他约束条件同(1.2)(1.3)当219=u269其他约束条件同(1.2)(1.3)当269=u309其他约束条件同(1.2)(1.3)当309=u345其他约束条件同(1.2)(1.3)当345=u,所有工件加工时间皆没有超过时限u，此时原问题相当于问题二,5.对一般情况下上述各问题的解法进行的一些讨论对于前两个问题总的完工时间包括各工件的等待时间之和与各工件的加工时间之和。由于各工件的加工时间之和是一定的，所以完工时间最优问题等价于各工件等待时间总和的最优化问题。设第i个工件的加工次序为，总的完工时间为。每个工件都被其后置加工工件所等待，因此，总的工件等待时间即每个工件被等待的时间总和。第i个工件被等待的时间为，则所有工件被等待的时间为所有工件的加工时间为为确定的数因此总的完工时间之和为:,（3）中变量说明:表示第个工件的完工时间（包括等待与加工两个阶段）j=1,2nu表示确定时限表示第个工件的完工时间超过了确定时限uj=1,2n表示第个工件的完工时间没有超过了确定时限uj=1,2n表示第个工件的补偿费率根据题目要求，只有超过了确定时限的工件才需要支付补偿费用，由此可以得到目标函数为：（1.1）可根据给出的时间与费率表的出如同（1.2）的约束条件，得出如同（1.3），（1.4）的约束条件。建立了本问题的最优模型,模型评价,优点：1、模型结构简单，可读性强,容易操作。2、模型采用先进