数学建模-零件加工.doc

零件加工 零件加工【摘要】本文解决的是计划作业问题中的车间作业问题，分析了工序安排的最小平均时间和最大工件价值在不同约束条件下的建模环境，运用了冒泡法，并在化整为零的思想上引入了0/1变量，分别建立了有限源“单队单服务台”以及有限源“单队多服务台”串联的线性规划模型。在目标函数的选择上我们充分考虑了目标的全面性、独立性和易获取性。借助lingo软件进行求解运算，得出其中的最优排序方案，实现工件加工任务的平均时间与总工件价值最优。针对问题一：在不考虑完工时间和工件价值限制的基础上，分析了平均时间与其主要影响因素（零件加工时间和等待时间）之间的关系，通过冒泡法运用C+进行编程，得到10个零件在车间加工的最优排序为35110764289，最小平均时间为=10.82h。针对问题二、三：由于这两题模型相似，其差异在于目标函数与约束范围的选取，因此我们运用lingo软件实现了在完工时间的限制下，对于不同的目标函数建立的线性规划模型的求解，得到第二题的最优排序为：35291017648，其平均时间为=12.32h；第三题的最优排序为：57381104，其平均时间为=6.61h。针对问题四、五：由于第四题是第五题的特殊情况，因此我们只需要在第四题模型的基础上进行推广即可得到第五题的模型。经过分析我们发现这两题的模型基本一致，可以归结为：n个零件在车间待的总时间为各个零件从一开始到其在第m台机床上完成加工的时间和。利用lingo软件编程可得第四题的最优排序为：53161097284，其平均时间为=13.41h。关键字：冒泡法 线性规划 化整为零 0/1变量 最优排序一、问题重述计划作业问题中的车间作业问题是一个具有一定实际研究价值与应用价值的数学建模问题，它主要研究的是n个零件在m台机器上的有序加工问题。在该问题中每一个零件都具有自己的“加工时间”、“完工时间”以及“工件价值”，需要我们构建模型，将各个零件的加工顺序进行排列，以求得平均加工时间亦或是工件总价值的极值问题。这次所需要我们求解的五个问题，实则是一个递进的研究过程，我们可以依据这五个问题，从最简单的情况出发，不断地发散以及扩展，最终得到一个普遍的研究方法。问题一：要求我们将十种零件在一个工作程序中进行排序，依据十个零件的加工时间，求得平均时间的最小值。问题二：要求我们在第一题的基础上引入“完工时间”来限制零件加工的排序，以求得平均时间的最小值。问题三：再一次引入参数“工件价值”伴随着完工时间的限制，寻求总价值的最大化。问题四：加工的程序从一个加工程序变成串联的两个程序，加入了加工程序之间过渡时的等待时间的限制与思考，求解平均时间的最小值。第五题：则最终演化为让我们在前四题的基础上，探求n个零件在m台机器上的有序加工问题，找到最小平均时间的零件加工顺序的安排方法。二、符号说明符号说明对于只有一个工作程序时第i件零件加工时间对于只有一个工作程序时第i件零件等待时间总时间一个数学矩阵排序后一个零件时间的矩阵表示平均时间零件个数零件加工顺序点构成矩阵各个零件加工顺序点对于各个零件加工与否的标记矩阵对于某个零件加工与否的标记完工时间工件价值总价值从第1件零件在C上加工开始到第i件零件在C上加工结束所花时间从第1件零件在C上加工开始到第i件零件在Z上加工结束所花时间零件i在车床C上加工时间零件i在钻床Z上加工时间第i个零件在第m台机床上加工时间第1件零件在第一台机床上加工开始到第i件零件在第j台机床上加工结束所花时间三、模型假设假设：（1）忽略各零件交接时的时间损耗，无论是同一个设备上的，还是不同设备之间的；（2）工人的熟练度相同，各机床的工作性能良好，能够保证各个零件在工序上的加工时间固定不变；（3）只有在第一个工序上的时间是连续的，但是在之后的几个程序中会出现一定量的间断；（4）在最后一道程序上加工完的零件在零时刻离开车间，不计中间的时间损耗；（5）n个零件在各个机床上的加工顺序一致（分析见后）。四、模型的建立4.1 问题一模型建立建立在一般条件下有限源“单队单服务台”模型，在不考虑时间和价值限制的基础上，要求n个零件在车间停留的平均时间最短。因为每个零件在车间的停留时间包括零件加工时间和其等待时间，则设表示第i件零件加工时间， 表示第i件零件等待时间，可得总时间：其中 要使达到最小，即求 则只需要保证即可。对于简易的单调排序，我们采用冒泡法进行编程求解。其流程图如下：i=0iN交换aj与aj+1的位置i+j=0j+jaj+1NYNNY图1 冒泡法流程图Y4.2问题二、三模型建立通过分析第二题与第三题，我们可以发现两者均是在约束条件下的有限源“单队单服务台”模型，他们唯一的差别即是约束范围以及目标函数的不同。故对于第二题与第三题，我们只要构建两个类似的线性规划模型即可。 对于第二题，在考虑完成时间的约束条件下，建立模型来寻求整个路线最短的平均时间。由上题模型可知，我们设定第i件零件的加工时间为，另外设完工时间为。引入0-1变量构建模型，用矩阵表示零件加工点的排列顺序，用矩阵表示在原始零件加工序列下的加工时间。由于受到完工时间的限制，每一种排序可最多加工n种零件，将零件的加工选择表示为当在第i次加工的是第j件零件时，则对于上述函数表达式中的，只要对取1，而其余的均取0即可，这表示零件j为加工的第i件零件。因此我们的目标函数为而该模型的约束条件有以下三条：；其中对零件是否进行加工给予标记，记作矩阵，若零件i加工，则，否则。至于第三题，由于目标函数的改变，其所求的是在完成时间约束条件下的零件的最高价值。该模型中需要加入的参量为工件价值。统观整个加工过程，我们的目标函数记为而约束条件与第二题一致。4.3问题四、五模型建立问题四、五均属于n个零件在多个机床上的加工问题，即要建立有限源的“单队多服务台”串联模型，第四题则是第五题的特殊情况。对于问题四，设有n个零件需要在车床C和钻床Z上加工，每个零件都必须先经过车床，再经过钻床。设，分别表示零件在车床C和钻床Z上的加工时间。我们知道，n个零件在C上有加工顺序，在Z上也有加工顺序，且这两个顺序可以不同。假设n个零件在C上的最优加工顺序已经确定，而零件在Z上的加工顺序与以上不同，则说明一些先在C上加工了的零件不能及时在Z上完成加工，而要落后于比其在C上晚加工的零件，这样无疑增加了某些零件的等待时间。故我们可知最优加工顺序应该在两台机床上实现一致。n个零件在车间待的总时间为各个零件从一开始到其在Z上完成加工的时间和。即：其中，表示从第1件零件在C上加工开始到第i件零件在Z上加工结束所花时间，另外设表示从第1件零件在C上加工开始到第i件零件在C上加工结束所花时间，则其可分为两种情况：1）CiCi-1C2C1Zi-1Z1ZCZi 则2) Zi-1Z1ZCCiCi-1C2C1Zi 则综合1）2）可知：即故目标函数表示为：其中，对于问题五，设有n个零件在m台机床上进行加工，且每个零件依次经由第1,2,3,m台机床，由问题四的分析可以知道其最优排列顺序依然在m台机床上实现一致。用表示从第1件零件在第一台机床上加工开始到第i件零件在第j台机床上加工结束所花时间，则可由问题四的推广得其目标函数：其中，表示第i个零件在第m台机床上加工时间。五、模型的求解5.1问题一模型求解在不考虑完工时间和价值限制的基础上，要求n=10个零件在车间停留的平均时间最短，由上述建立的模型可知，只要知道这10个零件各自加工时间的递增排序即可，因此我们通过冒泡法运用C+编程，对各零件的加工时间进行排序（见附录一），得到零件加工顺序和时间如下表：顺序零件序号35110764289时间/1.922.42.733.14.1总时间=108.2h平均时间=10.82h故按零件加工顺序35110764289，可使10个零件在车间停留的平均时间最短，为=10.82h.5.2问题二模型求解至于第二题，我们将其参数进行扩充与赋值，使得各零件的参数都由“加工时间”与“完工时间”组成，我们将第二题中，对于“完工时间”没有确切要求的零件，都赋予其值23.8（其为第二题中所有零件完成的总时间跨度，只要完成所有时间零件的加工，则这些零件完工时间的限制绝对不会大于23.8）。基于上述模型的建立，我们运用lingo编程软件（见附录二），通过线性规划得到零件加工的安排顺序具体如下：顺序零件号35291017648加工时间2.0完工时间23.87.08.51113.523.823.823.823.823.8总时间=123.2h平均时间 =12.32h这就是我们得到的关于第二题的最优排序为：35291017648他的总时间为123.2h，平均时间为12.32h。5.3问题三模型求解在第三题中，我们主要是在第二题的模型上更进一步地加大约束条件的种类与范围，题目给出的十个零件都被赋予了“加工时间”、“完工时间”和“工件价值”三个值。由于题中要求的是加工工件价值的最大化，所以出于价值最大的考虑，我们无法保证这十个零件每一个都会加入生产。用lingo构建线性规划模型（见附录三），得到零件加工的安排顺序具体如下：顺序总和零件号00057381104加工时间0.7完工时间7568.510.313.515工件价值4741097243总时间=46.3h平均时间=6.61h可知对于第三题，若想求的工件价值的最大值，其最优排序为：57381104他的总时间为46.3h，平均时间为6.61h。5.4问题四模型求解对于问题四，10个零件都需要在车床C和钻床Z上加工，且每个零件都必须依次经过车床和钻床，由问题四所建立的模型，我们知道零件的加工顺序在两台机床上是一致的，故也有种可能。但要保证各个零件在车间待的总时间最少，其加工零件顺序固然只有一种。我们采用lingo编程（见附录四），得到零件的加工顺序和总时间如下表：顺序零件号53161097284车床加工时间2.3231.7钻床加工时间2.534总时间=134.1h平均时间=13.41h由上表可知：当10个零件分别在车床和钻床上加工的顺序都是53161097284时，可得总时间最少，为=134.1h，平均时间=13.41h。5.5问题五模型求解对于问题五，他是第四题的推广，有n个零件在m台机床上进行加工，且每个零件依次经由第1,2,3,m台机床，由问题四、五的模型分析可以知道其最优排列顺序依然在m台机床上实现一致。n个零件在车间待的总时间为各个零件从一开始到其在第m台机床上完成加工的时间和。Lingo编程（略）。六、模型评价在本题中，对于第一题我们构建了一个在无约束条件下的有限源的“单队单服务台” 模型，我们将其简化为各零件加工时间长短的简单排序，运用冒泡法大大缩短了运算的时间，简便了运算的过程。其次，对于第二题的在有约束条件下的有限源的“单队单服务台” 模型，我们始终围绕一种化整为零的数学思想将整批零件的加工任务拆分为在最优的排序下每个工件的实际加工情况来分析，根据各零件的加工时间，完工时间以及工件价值的限制，采用lingo编程软件，进行线性规划得到最优解，这种方法大大缩短了计算时间，提高了工作效率。对于四、五两题，考虑到它其实是一个有限源的“单队多服务台”串联模型，由于运用了lingo软件进行求解，使模型本身就具有很大的可移植性，方便了其到m件零件n台机床的延伸与应用。但是我们的模型还是存在着一些不足之处。模型对于无限源的情况并不适用，与现实生活并不相符，只是用于理论的研究。而且，也不适用于多服务台并联，或是多队的情况。但是总的来说，该模型对于日常生活中的工作安排问题还是具有很大的实际运用价值，值得推广。七、参考文献1清华大学运筹学教材编写组.运筹学（第三版）M清华大学出版社,2005.2 洪文，吴本忠，Lingo4.0 for windows 最优化软件及应用，北京大学出版社，2001.3姜启源,谢金星,叶俊,数学模型（第三版）M.北京:高等教育出版社,2003.4谢金星、薛毅，优化建模与LINDOLINGO软件M.清华大学出版社，20055高崚嶒、杨雨慧，关于零件加工排序问题数学模型的建立，南京工业职业技术学院学报，2002.6陈运标、邓风仪、黄深泉，工件加工排序，/view/68080fdc5022aaea998f0fbd.html，2010八、附录附录一：#include /链接标准头文件 #define N 10 /定义常量N并赋值为10 void main() /主函数入口 /表示主函数开始 int i,j; /定义整形变量i和j float gN,temp,min; /定义N维（N10，也就是十维啦）实数组和实数变量temp printf(输入10个数n); /在屏幕上显式输入10个数并且换行 for(i=0;iN;i+) /开始for循环，从i0,每次加1，直到i=9,共需循环10次 /循环体开始 scanf(%f,&gi); /依次获取用户输入的实数值并存入数组grade中 /循环结束 for(i=0;iN;i+) /开始外层for循环，从i0,每次加1，直到i=9 /外层循环体开始 for(j=0;jgj+1) /条件判断 /如果整形数组前面的数比其后的小,执行以下语句 temp=gj+1; /将比较大的数赋值给temp gj+1=gj; /将比较小的数赋值给数组中后面的变量 gj=temp; /将比较大的数赋值给数组中前面的变量 /从此便完成大小变量的交换，使得大值往前放 /结束内层循环 /结外内层循环，完成排序 printf(最后排序为:n); /在屏幕显式最后排序为:并换行 for(i=0;iN;i+) /同开始的for循环类似 /开始循环输出 printf(%.1fn,gi); /只是这里要逐个输出数组中的十个数值 /结束循环输出 printf(n); printf(min=%.1fn,10*g0+9*g1+8*g2+7*g3+6*g4+5*g5+4*g6+3*g7+2*g8+g9); /输出换行到屏幕，看不到什么效果，可删掉 /结束main()函数附录二：model: !考虑完工时间的排序问题;sets: gongjian/g1.g10/:shijian,endtime; ! 属性为原始排序下各个工件的机床加工时间，完工时间，工件价值; shunxu/s1.s10/:time,overtime; ! 属性为重新排序后各个工件的机床加工时间，完工时间，工件价值; links(shunxu,gongjian): note;endsets !目标函数; min=sum(shunxu(I):overtime(I);!从新排序后各工件的机床加工时间（可能为零，即表示未选中工件）; for(shunxu(I): time(I)=sum(gongjian(J):shijian(J)*note(I,J);!从新排序后各工件的完工时间（可能为零，即表示未选中工件）;for(shunxu(I): overtime(I)=sum(gongjian(J):endtime(J)*note(I,J); );!从新排序后各工件的工件价值（可能为零，即表示未选中工件）; !每个顺序位只能有一个工件或者没有工件; for(shunxu(I): sum(gongjian(J): note(I,J)=1); !每个工件只能排在一个顺序位上; for(gongjian(J):sum(shunxu(I): note(I,J)=1); !各工件的完工时间约束; for(shunxu(I): sum(shunxu(J)|J#le#I:time(J)=overtime(I); ); !定义0/1变量; for(links:bin(note); data: !原始排序下各个工件的机床加工时间; shijian=1.8 3 1.2 2.7 1.6 2.4 2 3.1 4.1 1.9; !原始排序下各个工件的完工时间; endtime=23.8 8.5 23.8 23.8 7 23.8 23.8 23.8 11 13.5; enddataend附录三：model: !考虑完工时间和工件价值的排序问题;sets: gongjian/g1.g10/:shijian,endtime,gj_value; ! 属性为原始排序下各个工件的机床加工时间，完工时间，工件价值; shunxu/s1.s10/:time,overtime,fin_value; ! 属性为重新排序后各个工件的机床加工时间，完工时间，工件价值; links(shunxu,gongjian): note;endsets !目标函数; max=sum(shunxu(I):fin_value(I);!从新排序后各工件的机床加工时间（可能为零，即表示未选中工件）; for(shunxu(I): time(I)=sum(gongjian(J):shijian(J)*note(I,J);!从新排序后各工件的完工时间（可能为零，即表示未选中工件）;for(shunxu(I): overtime(I)=sum(gongjian(J):endtime(J)*note(I,J); );!从新排序后各工件的工件价值（可能为零，即表示未选中工件）;for(shunxu(I): fin_value(I)=sum(gongjian(J):gj_value(J)*note(I,J); ); !每个顺序位只能有一个工件或者没有工件; for(shunxu(I): sum(gongjian(J): note(I,J)=1); !每个工件只能排在一个顺序位上; for(gongjian(J):sum(shunxu(I): note(I,J)=1); !各工件的完工时间约束; for(shunxu(I): sum(shunxu(J)|J#le#I:time(J)=overtime(I); ); !定义0/1变量; for(links:bin(note);data: !原始排序下各个工件的机床加工时间; shijian= 1.8,3.0,1.2,2.7,1.6,2.4,2.0,3.1,4.1,1.9; !原始排序下各个工件的完工时间; endtime=10.3,8.0,6.0,15.0,7.0,8.2,5.0,8.5,9.8,13.5; !原始排序下各个工件的工件价值; gj_value=9,2,4,2,4,6,7,10,4,7;enddataend附录四：model: !工件先车后钻的排序问题;sets: gongjian/g1.g10/:che_shijian,zuan_shijian; shunxu/s1.s10/:che_time,zuan_time,che_fintime,zuan_fintime; lin