零件加工排序问题.doc

姓名：_班级：_学号：_座号：_装订线商丘师范学院2011-2012学年度第二学期期终考试数学与信息科学学院 数学与应用数学、信息与计算科学专业10级（数本10-1班、数本10-2班、信计10-1班）数学建模答卷评分标准数学模型（30分）求解方法（30分）结果与分析（30分）总体印象（10分）总分总分人得分零件加工顺序的数学模型摘要对于零件加工顺序模型的求解，我们不难想到运用多种方法来达到其求解目的，但是考虑到零件在M1工序上的总加工时间是固定的。关键是在M2及M3工序上会出现等待。如果采用不同序加工,那么在M1上已加工好的零件,在M2上加工的时间会落到在M1上比其后加工的零件的后面,则其在M2上等待的时间更长,同样在M2与M3工序上也是这样，要求加工时间最短的加工顺序，就必须尽量减少零件在M2及M3工序上的等待时间，由于零件必须在它们要求的时间内完工，即某零件在任务开始起到该零件加工完毕之间所用的总时间应少于该零件的规定完工时间。所以要使整个加工任务的零件总价值最大，必须合理选择加工零件的种类及其加工的次序。本题根据已知数据，结合问题中的具体要求，我们引入0/1变量建立零件排序的数学规划模型。借助Lingo软件进行求解运算，得出其中的最优排序方案。使得完成这批零件加工任务所需要的总时间最省。在这里，我们通过对各个零件（排序后）完成某项特定工序所需总时间进行求和得到整个加工任务所需要的总时间。而各零件的总时间包括其机床加工时间和加工其他零件的等待时间。最后，根据我们建立的模型求解得出某车间加工十个零件模型所需最短总加工时间为943分钟，总加工时间最短的加工顺序为：DE-JGHBIAFC，具体结果如表1-1，1-2。关键词：0/1变量 数学规划模型 Lingo软件一、问题重述某车间上午8:00开始加工十个零件,这些零件必须依次通过机床M1，M2，M3,其加工时间如下表(单位：分钟)。M1M2M3A101510B101018C221615D8106E91010F152114G111612H16910I13107J10791. 试建立模型求出使总加工时间最短的加工顺序。2. 写出个零件加工起止时间表，求出个机床的等待时间。3. 若零件加工还要满足下面条件，零件D必须在零件E之前加工；零件H与零件J的加工必须相连；机床M3加工每个零件等待时间不能超过5分钟，总等待时间不能超过30分钟。试建立模型，重新回答前面两个问题。二、问题分析零件在M1工序上的总加工时间是固定的。关键是在M2及M3工序上会出现等待。如果采用不同序加工,那么在M1上已加工好的零件,在M2上加工的时间会落到在M1上比其后加工的零件的后面,则其在M2上等待的时间更长,同样在M2与M3工序上也是这样，要求加工时间最短的加工顺序，就必须尽量减少零件在M2及M3工序上的等待时间，由于零件必须在它们要求的时间内完工，即某零件在任务开始起到该零件加工完毕之间所用的总时间应少于该零件的规定完工时间。所以要使整个加工任务的零件总价值最大，必须合理选择加工零件的种类及其加工的次序。三、模型假设假设一：在后面的模型中，我们都假定了忽略零件在转换工序时的运输时间。即将整个零件加工过程简化为一个连续的过程，只考虑机床在加工零件时其他零件的等待时间。假设二：零件之间是相互独立的,从生产的角度看,先加工一个零件并不影响对后面零件的加工。不象有些流水线生产那样,存在固定的加工顺序。假设三：工人都是熟练工人,零件在工序上的加工时间是固定不变的,与工人的操作水平无关。假设四：零件在三个工序上采有同顺序加工,即在工序M1上的加工顺序与在M2及M3工序上的加工顺序相同。在工序M1上的加工是连续不断的。四、符号说明XI(1)：i零件在车床M1加工所需时间XI(2) ：i零件在车床M2加工所需时间Xi(3) ：i零件在车床M3加工所需时间MI(1):i零件完成在M1加工的总时间MI(2):i零件完成在M2加工的总时间MI(3):i零件完成在M3加工的总时间MI-1(2):(i-1)零件完成在M2加工的总时间(i1)MI-1(3)(i-1)零件完成在M3加工的总时间(i1)M:加工十个零件模型的总时间五、模型的建立由问题分析可知零件i在M1工序完成的时间：MI(1)= MI-1(1) + MI(2) （1）对于零件在M1工序完成的时间MI(1)与(i-1)零件完成在M2加工的总时间，MI-1(2)要分两种情况分析：1）当时MI(1)MI-1(2)即i零件完成M1工序的总时间大于或等于(i-1)零件完成M2工序的总时间，此时零件不需要等待(i-1)零件而立即就进入钻工序，因此零件完成M2工序的总时间表达式为; MI(2)= MI(1)+ MI(2)2) 当时MI(1) MI-1(2)，即零件完成M1工序的总时间小于或等于(i-1)零件完成M2工序的总时间，此时零件需要等待(i-1)零件完成M2工序才能进入M2加工。因此零件完成M2工序的总时间表达式为MI(1)= MI-1(1) + XI(2)。综合以上两种情况，得到零件完成M2工序的总时间计算公式为:MI(1)=max(MI(1), MI-1(1) + XI(2) （2）同理：对于零件在M2工序完成的时间MI(1)与(i-1)零件完成在M3加工的总时间MI(3)，有i零件完成M3工序的总时间计算公式为:MI(3)=max(MI(1), MI-1(3) + XI(3) （3）综合（1）（2）（3）可得加工十件零件需要的总时间为：M= MI(3)+ 约束条件：s.t. =1,(i=1,2,3,10) =1,(j=1,2,3,10)六、模型求解通过用Lingo编程求解，我们得出以下结论：顺序号零件号M1加工时间XI(1)（分钟）M2加工时间分XI(2)钟）M3加工时间Xi(3 （分钟）AD8106BE91010CJ1079DG111612EH16910FB101018GI13107HA101510IF152114JC221615 表1-1顺序号零件号完成M1工序总时间MI(1)（分钟）完成M2工序总时间MI(2（分钟）完成M3工序总时间MI(3)（分钟）AD81824BE173245CJ303954DG415769EH576687FB6787105GI8299112HA95114134IF114134148JC134150165总时间：943 表1-2由表6-1可知，我们可以排出各个零件加工的起止时间表，如下表所示：起止时间表：序顺间时止起号序工M1M2M3D8:00-8:088:08-8:188：18-8:24E8：08-8:178:18-8:288:28-8:38J8:17-8:278:28-8:358:38-8:47G8:27-8:388:38-8:548:54-9;06H8:38-8:548:54-9:039:06-9:16B8:54-9:049:04-9:149:16-9:34I9:04-9:179:17-9:279:34-9:41A9:17-9:279:27-9:429:42-9:52F9:27-9:429:42-10:0310:03-10:17C9:42-10:0410:04-10:2010:20-10:35机床等待时间：工序号等待时间顺序号M1M2M3D010E013J000G003H002B007I000A000F000C000针对问题三：若零件加工还要满足下面条件，零件D必须在零件E之前加工；零件H与零件J的加工必须相连；机床M3加工每个零件等待时间不能超过5分钟，总等待时间不能超过30分钟，我们还用此类似模型进行求解。唯一不同的是:该模型要满足上述要求， 从软件的运行情况可知，最优的零件排序为DE-BGHJFAIC；完成这批零件加工任务所需的最省总时间为846分钟.起止时间表：序顺间时止起号序工M1M2M3D8:00-8:088:08-8:188：18-8:24E8：08-8:178:18-8:288:28-8:38B8:17-8:278:28-8:388:38-8:56G8:27-8:388:38-8:548:56-9;08H8:38-8:548:54-9:039:08-9:18J8:54-9:049:04-9:139:18-9:34F9:04-9:199:19-9:409:40-9:54A9:17-9:279:27-9:429:42-9:52I9:27-9:409:42-9:529:52-9:59C9:40-10:0210:02-10:1810:18-10:33机床等待时间：工序号等待时间顺序号M1M2M3D010E013B000G002H005J005F000A000I020C000七、模型评价在本题的解答过程中所建立的数学规划模型中，我们始终围绕一种化整为零的数学思，根据各零件在加工过程中加工时间和总时间之间的联系，寻求各零件加工总时间的具体算法。再利用Lingo软件进行求解模型，得出零件的最优排序。其中逻辑严谨，论证充分，算法简洁准确。有效地提高了软件求解效率。由于零件的生产与加工要受很多因素的影响，我们建立的模型中还有很多我们未考虑到的因素，对现实生活中的零件生产与加工的的排序问题影响不大，不适合全面推广。X=八、参考文献1姜启源，谢金星，叶俊，数学模型（第三版）