数学建模-零件加工

零件加工1零件加工【摘要】本文解决的是计划作业问题中的车间作业问题，分析了工序安排的最小平均时间和最大工件价值在不同约束条件下的建模环境，运用了冒泡法，并在化整为零的思想上引入了0/1变量，分别建立了有限源“单队——单服务台”以及有限源“单队——多服务台”串联的线性规划模型。在目标函数的选择上我们充分考虑了目标的全面性、独立性和易获取性。借助lingo软件进行求解运算，得出其中的最优排序方案，实现工件加工任务的平均时间与总工件价值最优。针对问题一：在不考虑完工时间和工件价值限制的基础上，分析了平均时间与其主要影响因素（零件加工时间和等待时间）之间的关系，通过冒泡法运用C++进行编程，得到10个零件在车间加工的最优排序为3—5—1—10—7—6—4—2—8—9，最小平均时间为T=10.82h。针对问题二、三：由于这两题模型相似，其差异在于目标函数与约束范围的选取，因此我们运用lingo软件实现了在完工时间的限制下，对于不同的目标函数建立的线性规划模型的求解，得到第二题的最优排序为：3—5—2—9—10—1—7—6—4—8，其平均时间为T=12.32h；第三题的最优排序为：5—7—3—8—1—10—4，其平均时间为T=6.61h。针对问题四、五：由于第四题是第五题的特殊情况，因此我们只需要在第四题模型的基础上进行推广即可得到第五题的模型。经过分析我们发现这两题的模型基本一致，可以归结为：n个零件在车间待的总时间为各个零件从一开始到其在第m台机床上完成加工的时间和。利用lingo软件编程可得第四题的最优排序为：5—3—1—6—10—9—7—2—8—4，其平均时间为T=13.41h。关键字：冒泡法线性规划化整为零0/1变量最优排序零件加工2一、问题重述计划作业问题中的车间作业问题是一个具有一定实际研究价值与应用价值的数学建模问题，它主要研究的是n个零件在m台机器上的有序加工问题。在该问题中每一个零件都具有自己的“加工时间”、“完工时间”以及“工件价值”，需要我们构建模型，将各个零件的加工顺序进行排列，以求得平均加工时间亦或是工件总价值的极值问题。这次所需要我们求解的五个问题，实则是一个递进的研究过程，我们可以依据这五个问题，从最简单的情况出发，不断地发散以及扩展，最终得到一个普遍的研究方法。问题一：要求我们将十种零件在一个工作程序中进行排序，依据十个零件的加工时间，求得平均时间的最小值。问题二：要求我们在第一题的基础上引入“完工时间”来限制零件加工的排序，以求得平均时间的最小值。问题三：再一次引入参数“工件价值”伴随着完工时间的限制，寻求总价值的最大化。问题四：加工的程序从一个加工程序变成串联的两个程序，加入了加工程序之间过渡时的等待时间的限制与思考，求解平均时间的最小值。第五题：则最终演化为让我们在前四题的基础上，探求n个零件在m台机器上的有序加工问题，找到最小平均时间的零件加工顺序的安排方法。二、符号说明符号说明1it对于只有一个工作程序时第i件零件加工时间2it对于只有一个工作程序时第i件零件等待时间T总总时间A一个数学矩阵t排序后一个零件时间的矩阵表示T平均时间n零件个数零件加工3y零件加工顺序点构成矩阵iy各个零件加工顺序点Y对于各个零件加工与否的标记矩阵iY对于某个零件加工与否的标记ip完工时间iq工件价值Q总价值()cfi从第1件零件在C上加工开始到第i件零件在C上加工结束所花时间()zfi从第1件零件在C上加工开始到第i件零件在Z上加工结束所花时间ic零件i在车床C上加工时间iz零件i在钻床Z上加工时间im第i个零件在第m台机床上加工时间()jfi第1件零件在第一台机床上加工开始到第i件零件在第j台机床上加工结束所花时间三、模型假设假设：（1）忽略各零件交接时的时间损耗，无论是同一个设备上的，还是不同设备之间的；（2）工人的熟练度相同，各机床的工作性能良好，能够保证各个零件在工序上的加工时间固定不变；（3）只有在第一个工序上的时间是连续的，但是在之后的几个程序中会出现一定量的间断；（4）在最后一道程序上加工完的零件在零时刻离开车间，不计中间的时间损耗；（5）n个零件在各个机床上的加工顺序一致（分析见后）。零件加工4四、模型的建立4.1问题一模型建立建立在一般条件下有限源“单队——单服务台”模型，在不考虑时间和价值限制的基础上，要求n个零件在车间停留的平均时间最短。因为每个零件在车间的停留时间包括零件加工时间和其等待时间，则设1it表示第i件零件加工时间，2it表示第i件零件等待时间，可得总时间：121()niiiTttAt总其中1211;1iikkttin(1...21)Ann'11211,1,1(...)nnttttt要使T达到最小，即求minnTT总则只需要保证11,1iitt即可。对于简易的单调排序，我们采用冒泡法进行编程求解。其流程图如下：零件加工5i=0iN交换a[j]与a[j+1]的位置i++j=0j++jN-1-ia[j]a[j+1]NYNNY图1冒泡法流程图Y零件加工64.2问题二、三模型建立通过分析第二题与第三题，我们可以发现两者均是在约束条件下的有限源“单队——单服务台”模型，他们唯一的差别即是约束范围以及目标函数的不同。故对于第二题与第三题，我们只要构建两个类似的线性规划模型即可。对于第二题，在考虑完成时间的约束条件下，建立模型来寻求整个路线最短的平均时间。由上题模型可知，我们设定第i件零件的加工时间为1it，另外设完工时间为ip。引入0-1变量构建模型，用矩阵121(...)nnyyyyy表示零件加工点的排列顺序，用矩阵11,12,11,1,1(...)innttttt表示在原始零件加工序列下的加工时间。由于受到完工时间的限制，每一种排序可最多加工n种零件，将零件的加工选择表示为11,11,12,11,2,11,21,12,12,12,2,12,11,11,12,11,2,11,1,1,12,1,2,1,..............................nnnninnnnnnnnnnnnytxtxtxytxtxtxyytxtttxytxtxtx当在第i次加工的是第j件零件时，则对于上述函数表达式中的,,1,1,2,1,......iiniiniiinytxtxtx，只要对,ijx取1，而其余的均取0即可，这表示零件j为加工的第i件零件。因此我们的目标函数为minnTT总而121()niiiTttAt总零件加工7该模型的约束条件有以下三条：,11nijix；,11nijjx；11jiijitYp；其中1,ijn对零件是否进行加工给予标记，记作矩阵Y，若零件i加工，则1iY，否则0iY。至于第三题，由于目标函数的改变，其所求的是在完成时间约束条件下的零件的最高价值。该模型中需要加入的参量为工件价值iq。统观整个加工过程，我们的目标函数记为1maxniiiQqY而约束条件与第二题一致。4.3问题四、五模型建立问题四、五均属于n个零件在多个机床上的加工问题，即要建立有限源的“单队——多服务台”串联模型，第四题则是第五题的特殊情况。对于问题四，设有n个零件需要在车床C和钻床Z上加工，每个零件都必须先经过车床，再经过钻床。设ic，iz分别表示零件(1)iin在车床C零件加工8和钻床Z上的加工时间。我们知道，n个零件在C上有加工顺序，在Z上也有加工顺序，且这两个顺序可以不同。假设n个零件在C上的最优加工顺序已经确定，而零件在Z上的加工顺序与以上不同，则说明一些先在C上加工了的零件不能及时在Z上完成加工，而要落后于比其在C上晚加工的零件，这样无疑增加了某些零件的等待时间。故我们可知最优加工顺序应该在两台机床上实现一致。n个零件在车间待的总时间为各个零件从一开始到其在Z上完成加工的时间和。即：1()nziTfi总其中，()zfi表示从第1件零件在C上加工开始到第i件零件在Z上加工结束所花时间，另外设()cfi表示从第1件零件在C上加工开始到第i件零件在C上加工结束所花时间，则其可分为两种情况：1）z(1)()cfifi()cfiz(1)fi则()()zcififizCiCi-1C2C1Zi-11Z11ZCZi零件加工92)z(1)()cfifi()cfiz(1)fi则z()(1)zififiz综合1）2）可知：zzz()(1)()()(1)(1)()ciczicfizfifififizfifi即z()max((),(1))zcifififizZi-1Z1ZCCiCi-1C2C1Zi零件加工10故目标函数表示为：z2min(1){max((),(1))}nzciiTffifiz总其中，11(1)zfcz对于问题五，设有n个零件在m台机床上进行加工，且每个零件依次经由第1,2,3,…,m台机床，由问题四的分析可以知道其最优排列顺序依然在m台机床上实现一致。用()(1,1)jfiinjm表示从第1件零件在第一台机床上加工开始到第i件零件在第j台机床上加工结束所花时间，则可由问题四的推广得其目标函数：1m2min(1){max((),(1))}nmmiiTffifim总其中11(1)(1)mmffm，im表示第i个零件在第m台机床上加工时间。五、模型的求解5.1问题一模型求解在不考虑完工时间和价值限制的基础上，要求n=10个零件在车间停留的平均时间最短，由上述建立的模型可知，只要知道这10个零件各自加工时间的递增排序即可，因此我们通过冒泡法运用C++编程，对各零件的加工时间进行排序（见附录一），得到零件加工顺序和时间如下表：零件加工11顺序1y2y3y4y5y6y7y8y9y10y零件序号35110764289时间/1it1.21.61.81.922.42.733.14.1总时间T总=108.2h平均时间T=10.82h故按零件加工顺序3—5—1—10—7—6—4—2—8—9，可使10个零件在车间停留的平均时间最短，为T=10.82h.5.2问题二模型求解至于第二题，我们将其参数进行扩充与赋值，使得各零件的参数都由“加工时间”与“完工时间”组成，我们将第二题中，对于“完工时间”没有确切要求的零件，都赋予其值23.8（其为第二题中所有零件完成的总时间跨度，只要完成所有时间零件的加工，则这些零件完工时间的限制绝对不会大于23.8）。基于上述模型的建立，我们运用lingo编程软件（见附录二），通过线性规划得到零件加工的安排顺序具体如下：顺序1y2y3y4y5y6y7y8y9y10y零件号35291017648加工时间1.21.63.04.11.91.82.02.42.73.1完工时间23.87.08.51113.523.823.823.823.823.8总时间T总=123.2h平均时间T=12.32h零件加工12这就是我们得到的关于第二题的最优排序为：3—5—2—9—10—1—7—6—4—8他的总时间为123.2h，平均时间为12.32h。5.3问题三模型求解在第三题中，我们主要是在第二题的模型上更进一步地加大约束条件的种类与范围，题目给出的十个零件都被赋予了“加工时间”、“完工时间”和“工件价值”三个值。由于题中要求的是加工工件价值的最大化，所以出于价值最大的考虑，我们无法保证这十个零件每一个都会加入生产。用lingo构建线性规划模型（见附录三），得到零件加工的安排顺序具体如下：顺序1y2y3y4y5y6y7y8y9y10y总和零件号00057381104加工时间1.61.31.22.12.81.90.7完工时间7568.510.313.515工件价值4741097243总时间T总=46.3h平均时间T=6.61h可知对于第三题，若想求的工件价值的最大值，其最优排序为：5—7—3—8—1—10—4．他的总时间为46.3h，平均时间为