工件加工问题

1工件加工问题摘要由于纯手工的加工制造手段效率低下，错误率高，成本昂贵，因此如今的工厂越来越多的采用流水线作业的方式进行生产制造。对于不同的零部件，机器加工生产的时间不尽相同，如何合理的安排零件加工的顺序是提高生产效率很重要的一环。本文主要通过动态规划的数学模型，对如何合理安排零件加工顺序进行了深入研究。为了更好的研究此问题，本文采用逐步递进的模式，由简到繁对问题进行了研究。首先，对于单个机床多个零件的情况，本文采用了直接加和的方式。其次，建立穷举模型对两个机床而零件数较少的情况，进行穷举计算，并分析计算结果。为了解决穷举模型对于零件数较大时失效性，建立了动态规划模型。该模型通过对问题进行阶段划分，状态分析，变量设定，确定方案并求解，得到了零件数目较多情况下，最优加工排序的选择方法，并用穷举法的计算结果对该模型的可行性进行了检验。检验表明，该模型能够很好的解决此类问题。而对于n个零件，m个机床的n/m/FmaxNP完全问题，本文给出了在定序条件下最短时间的快速计算方法。关键词工件加工排序动态规划n/m/Fmax问题21、问题重述某修理车间因修理工作需要生产n个不同的工件，每个工件都需要先在A机床，后在B机床上进行加工。不妨用1,2,…,n编号分别代表不同的工件，以,iiab表示工件i需在A,B机床上加工的时间。如果该车间只有一台A机床，一台B机床，且,iiab不受加工工件顺序的影响，问如何安排零件在A,B机床上的加工顺序，才能使机床加工总时间（从A机床开始加工，至两机床均将工件加工完为止）最短？2、问题分析为解决此问题，首先从以下几种情况考虑：情形1考虑一个机床n个工件；情形2考虑两个机床4个工件，5个工件；情形3考虑两个机床n个工件；情形4考虑m个机床n个工件；根据这样的递进分析，找到解决此种问题的普适性解法。3、模型假设与符号说明3.1模型假设(1)不考虑A、B机床之间转移传送的时间；(2)不考虑机床启动的时间；(3)加工时间与加工顺序无关；(4)每台机器同时只能加工一个工件；(5)加工时间与加工顺序无关；(6)不考虑机床磨损，工作状态良好。3.2符号说明N总加工方案数jt第j个工件加工时间iT第i种方案机床运转的加工总时间iaA机床加工零件i所需的时间ibB机床加工零件i所需的时间kS在A加工第k个零件时的状态kt第k个加工零件从完成A机床的加工到完成B机床的加工的时间kkfS()在kS状态下剩余未加工工件的最短加工时间34、情形1模型的建立与求解4.1简单加和模型对于情形1，由于此时为单一因子影响，无需考虑等待时间的问题，所以可以很容易的分析得到此时最短机床加工总时间为：1njjt5、情形2模型的建立与求解5.1穷举模型5.1.1模型的建立对于情形2，因为机床A是没有限制因素的，即非紧约束因子。因此为了加工时间最短，机床A应该一直不停的工作直至完成其工作任务——完成所有工件的加工。因此机床B的安排次序为本问题紧约束因子。根据以上分析，得到如下结论：工件按照依次在A、B机床加工的方式，在所有工件的全排列下，可以找到最优加工次序。因此，对于4、5个工件的小数量问题，可以首先采用穷举法进行求解。5.1.2模型的求解首先解决如下情况如表1所示：工件时间1234A6873B3259表1求解每种情况机床的总工作时间分析如下：当工件按1-2-3-4情况加工时，加工示意图如图1：图1显然加工总时间为:T6875935当工件按4-3-1-2情况加工时，加工示意图如图2：4图2显然加工总时间为:T3768226通过对工件所有排列的计算，我们得到在工件数目为4，机床数为2时的总时间表(表2)：1号工件2号工件3号工件4号工件总用时123435124331132433134229143226142329213435214331231433234132243128241329321433324130312433314227341226342127423127421329432127431226413226412329表2四个工件情况下总时间表5由此我们得到了工件数目为4时总时间最短的工件加工排序方案如表3所示：最优排列方案总时间143226341226431226413226表3四个工件的最优安排方案表通过穷举法，我们还对5个工件的情况进行了计算。假设情况如表4：1x2x3x4x5xA68735B32594表4所有情况的总时间表见附录二。这里给出5个工件情况下总时间最短的工件加工排序方案如表5：最优方案总时间14352311453231154323131452313415231345123135412314315231435123141352314153231453123145132315341231543123154132315143231表5五个工件的最优安排方案表5.1.3结果分析对于工件数目较小，机床个数为2的情况下，我们采用可以通过穷举的方法得到所工件机床6有最短工作总时间的安排方案。在工件数目为4时，上述假设情况下，工件加工的最短时间为26，共4种最佳方案；在工件数目为5时，上述假设情况下，工件加工的最短时间为31，共17种最佳方案。但可以看到，穷举法的致命弱点在于对于工件数量较大的情况下，计算工程量过大。当工件数达到20时，两个机床的情况下，所有安排方案种数：N=182.43910因此，穷举法并不是解决该问题很好的方法。5.2动态规划模型5.2.1模型的建立由模型一的分析可以得到如下一些结论：1.若假设第k+1个工件在A机床上的加工时间恒定，那么第k个加工的工件在B机床上加工时间越短，相同情况下B机床等待第k+1个工件的时间越长；2.若假设第k个工件在B机床上的加工时间恒定，那么第k+1个加工的工件在A机床上加工时间越长，相同情况下B机床等待第k+1个工件的时间越长。现设有1,2,…,m个工件，kS表示在A加工第k个零件时的状态，kkfS()表示在kS状态下剩余未加工工件的最短加工时间，kt表示第k个加工零件从完成A机床的加工到完成B机床的加工的时间。因此，可以得到如下递推公式：kkkkkkkkkmmiimfSfSttbabfSb1111...()min()max()()min()5.2.2模型的求解例如对于如下情况：工件机床1234A6873B3259此时m=4，mmkfSb()min()2根据上述递归方程我们可以采用如下方法得到零件加工的排列方案：第一步在上表中的数值区域选择最小的数值；第二步判断：若该数值在A机床一行，则将对应工件放在左1位置，若该数值在B机床一行，则放在右1位置；第三步删除所选数值一列；7第四步重复第一步，判断：若该数值在A机床一行，则将对应工件放在左2位置，若该数值在B机床一行，则放在右2位置；第五步重复上述步骤，直至选完所有工件。5.2.3结果分析得到如下序列：左1左2右2右14312因此以4-3-1-2加工过程可以得到最短加工总时间。经穷举法检验，该加工序列确实在最优加工序列中，最优加工时间为26。6、情形3模型的建立与求解运用上述方案，我们可以对工件数为m，机床数为n的零件加工情况进行求解。如对于如下假设：1x2x3x4x5xA68735B32594我们可以得到最优加工序列：4-3-5-1-2.。并且经计算此种方法编程实现的时间复杂度在O(n)阶，远优于O(n!)阶。对于情形4，这里只给出再定序情况下，工件加工最短时间的计算方法：对于加工顺序为nxxx12,,...,的情况，假设ix对于机床myyy12,,...,的生长时间分别为iiimttt12,,...,，其计算步骤如下：ijTI表示ix零件在jy机床上的完工时间，ijTD为ix零件在jy机床上的加工时间，则有：iiiijijijijnmTITITDTITITITDinjmFC1-1,11,-1-1,maxmax(,),1,2...,,1,2,...,7、模型的评价本文通过分析，采用了动态规划的手段对问题进行了求解，并运用穷举法对工件数目较小的情况进行了验证。验证表明，动态规划的模型能够很好的解决在机床数等于2的情况下工件加工的最优排序问题，并且时间复杂度很低，是一种较好的计算方法。但是其不足在于没有能够求解出满足最优时间的所有工件加工序列。而对于n/m/Fmax的NP完全问题，解决的方法主要有分枝定界类型的算法,Johnson算法等。本文只给出了在定序情况下最短加工时间的计算方法。工件机床88、参考文献[1]姜启源,数学模型(第三版)[M],北京：高等教育出版社，2003.[2]薛定宇,陈阳泉,高等应用数学问题的Matlab求解（第二版）[M],北京：清华大学出版社，2008.[3]谭浩强,C语言程序设计[M],北京:清华大学出版社,2005.[4]陈卫卫,王庆瑞,数据结构与算法[M],北京：高等教育出版社，2010.9附录一clear;clc;A=[68735];B=[32594];C=perms([54321])n=5;%¹¤¼þÊým=2;%»ú´²Êýfori=1:factorial(n);yu=0;T(i)=sum(B)+A(C(i,1));forj=2:n%A(1,C(i,j)),B(1,C(i,j-1))if(A(1,C(i,j))=B(1,C(i,j-1)))yu=yu+B(1,C(i,j-1))-A(1,C(i,j));elseif(yu==0)T(i)=T(i)+A(1,C(i,j))-B(1,C(i,j-1));elseif(yu(A(1,C(i,j))-B(1,C(i,j-1))))T(i)=T(i)+A(1,C(i,j))-B(1,C(i,j-1))-yu;yu=0;elseyu=yu-(A(1,C(i,j))-B(1,C(i,j-1)));endendendANSWER=C(find(T(:)==min(T)),:)xlswrite('C:\DocumentsandSettings\Administrator\×ÀÃæ\¹¤¼þ¼Ó¹¤µÄ¶¯Ì¬¹æ»®\data.xls',C,'Sheet1','H1');xlswrite('C:\DocumentsandSettings\Administrator\×ÀÃæ\¹¤¼þ¼Ó¹¤µÄ¶¯Ì¬¹æ»®\data.xls',T','Sheet1','N1');xlswrite('C:\DocumentsandSettings\Administrator\×ÀÃæ\¹¤¼þ¼Ó¹¤µÄ¶¯Ì¬¹æ»®\data.xls',ANSWER,'Sheet1','P1');10附录二表F-1五个工件的穷举法数据1号工件2号工件3号工件4号工件5号工件总用时1234539123543912435351245335125433712534401324537132543913425331345233135423313524381432533143523114235331425334145233414532311534234153243815432311542334152433615234402134539213543921435352145335215433721534402314537231543923415362345136235413623514382431533243513224135331124153342451334245313225341372531438254313425413342514336251344032145373215439324153432451343254136325143831245373125439314253331452313154233315243834125333415231342153334251323452132345123135142323512438354123135421323524135352143842315334235132