工件加工的排序优化问题

湖南工学院数学建模竞赛承诺书我们仔细阅读了第五届湖南工学院数学建模竞赛的竞赛规则。我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与本队以外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的,如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们愿意承担由此引起的一切后果。我们的参赛报名号为：参赛队员(签名)：队员1：***队员2：***队员3：***湖南工学院数学建模竞赛编号专用页参赛队伍的参赛号码：（请各个参赛队提前填写好）：竞赛统一编号（由竞赛组委会送至评委团前编号）：竞赛评阅编号（由竞赛评委团评阅前进行编号）：-1-湖南工学院数学建模竞赛工件加工的排序优化问题摘要众所周知，对于一个加工企业而言，如何在最短时间内完成加工任务，是一个企业提高竞争力和利润的关键。本文就是一篇关于工件加工的排序优化问题，即在给定的数据和做出符合实际生产的条件下，合理的安排工件的加工顺序，使加工的效率或所获得的利润等指标达到最大值。问题一是在零件只加工一次，如何合理安排加工顺序，使得完成这批工件加工任务所需的总时间最省或总价值最大。为此，我们引入了一个0-1变量表示加工工件的顺序和工件的种类，求出该变量，即可得到在不同情况下加工顺序，然后对结果进行分析，计算结果唯一（实际可能不唯一）。问题一的一二问安排如下：1）工件的加工顺序为6-3-9-10-7-5-1-2-8-11-4-12此时总时间最少，为171.9工件的加工时间为33.12）在时间充足的情况下，总价值最大为117，工件的加工顺序如下9112378114610问题二三四是在问题一上的推广,因此我们运用前面算法归纳出i种工件，每种工件需要j部机床的情况，只需在前面的程序中的工件顺序集里加入相应的属性，便能到达目的。对于i种工件，每种工件需要j部机床加工的情况我们建立的模型如下：车床M1钻床M2铣床M3…Mj1110X+1112MX+1213MX+…,-11ijjMx+21121MX+211222(MM)XMax+，221323(M,M)XMax+…2,j-11j2j(M,M)XMax+32131MX+312232(M,M)XMax+322333(M,M)XMax+…3,j-12j3j(M,M)XMax+…………………………i-1,11iiMX+i1i-1,2i2(M,M)XMax+i2i-1,3i3(M,M)XMax+…i,j-1i-1,ji,j(M,M)XMax+关键词：0-1变量、lingo、排序-2-1.问题重述计划排序问题中的车间作业问题，研究n个工件在m台机器上有序的加工问题，每个工件都有完工的日期（DD，Duedate）,加工的时间（PT，Processingtime）和工件的价值（VAL，Valueifjobisselected）.车间作业计划研究一个工厂生产工序的计划和安排，需要计划与合理安排各个工件在这些机器上加工的先后次序，即拟订加工工序，通过各个工件在各种机器上加工次序的合理安排，使得完成这批工件加工任务所需的总时间最省（注：总时间即为各个零件的加工时间和加工其他零件时它们等待时间之和）或要求整个选择加工的工件价值最大。有一个工厂现在有12种工件（编号为工件1，工件2，…，工件12）需要在车床，钻床，铣床几种不同的设备上加工。考虑下面的工件加工的排序问题：（一）这12种工件都要求在车床上加工，车床一次只能加工一种工件，这12种工件加工所需时间，每个工件的完工时间和每个工件的价值如表1所示：工件加工时间（h）完工时间(h)工件价值12.89823.27.5431.215164423352.710760.9222072.5171783.3331191.777102.51812113.6255124.71118表11、不考虑工件的完工时间和工件的价值，为该工厂安排工件加工的次序，使得完成这批工件加工任务所需的总时间最省。建立数学模型并给出相应的算法。2、由于工件必须在它们要求的时间内完工，按照表1的数据，为该工厂安排选择加工工件的种类及加工的次序，使得整个选择加工的工件价值最大。建立数学模型并给出相应的算法。（二）如果这12种工件都要求先在车床上加工，然后再在钻床上加工（即工件在钻床加工之前必须先在车床上加工过），每种机器一次只能加工一种工件，这12种工件加工所需时间如表2所示：-3-工件车床加工时间（h）钻床加工时间(h)12.8423.21.331.21.8442.252.7360.94.572.51.783.32.591.74.5102.52.5113.63.8124.71.9表2为该工厂安排工件加工的次序，使得完成这批工件加工任务所需的总时间最省。建立数学模型并给出相应的算法。（三）如果这12种工件都要求先在车床上加工，然后再在钻床上加工，最后再在铣床上加工，每种机器一次只能加工一种工件，这12种工件加工所需时间如表3所示：工件车床加工时间（h）钻床加工时间(h)铣床加工时间(h)12.84323.21.3131.21.82.5442.21.352.731.860.94.5272.51.73.683.32.50.891.74.51102.52.51.1113.60.91.3124.71.90.7表3为该工厂安排工件加工的次序，使得完成这批工件加工任务所需的总时间最省。建立数学模型并给出相应的算法。（四）对于上述问题你做出的数学模型和相应的算法给出评价。并将模型推广到n个工件在m台机器上加工的一般的工件排序问题，给出你的想法和解决问题的思路。-4-2.问题分析问题（一），第一问，题目只要求完成这批工件加工任务所需的总时间最省，不考虑完工时间和工件价值，为此引入一个12×12的0-1变量，下标分别表示工件序号和加工顺序序号。如：y(1,7)=1表示工件1加工顺序为7。利用约束条件和目标函数求出此变量，就能得到题目要求的工件加工次序。第二问，题目要求考虑完工时间并使利润最大，在第一问的基础上将目标函数中的总时间改为总利润，并加上完工时间的约束，将0-1变量解出，就是需要加工的工件序号和顺序。问题二是在问题一第一问的基础上，将加工次数增为两次，根据总时间的定义，某工件从任务开始时刻起到完成钻床工序止所需要的总时间包括该工件完成车工序的时间，等待上一个工件加工完的时间（即从该工件在车床加工完毕时刻起到其上一个工件在钻床上加工完毕这一段时间），该工件在钻床上加工的时间。建立数学模型求解。问题三四也都是将问题一二进行推广，因此只需将相应的数据用变量代替即可。3.符号说明ijy为0/1变量ia为i工件的车床加工时间jb在最优排列下第j次在车床加工的时间im为i工件的钻床加工时间jn在最优排列下第j次在钻床加工的时间iq为i工件的铣床加工时间jr在最优排列下第j次在铣床加工的时间id第i种工件在车床的完工时间jf在最优排列下第j种工件在车床工件的完工时间js在最优排列下第j种工件在完成钻床序的总时间ju在最优排列下第j种工件在完成铣床序的总时间it为i工件在从最优排列下车床加工所用的总时间W完成这批工件加工任务所需的总时间P工件总价值-5-4.模型假设4.1.不考虑的完工时间和工件的价值，安排工件加工的次序，使得完成这批工件加工任务所需的总时间最省。4.2.工件在转换工序时所需的运输时间为零。4.3.机器加工完一种工件后，能及时另外一种零件。4.4.工件和机器在加工过程中不发生意外。5.模型的建立与求解5.1.对于问题一1）设it为i工件实际完工时间，所以完成这批工件的总时间为Z=121iit=∑而加工i工件在最优排列下所用的总时间it=b1i−+bi=b2−i+b1−i+bi=b1+b2+…+ib即1iijjtb==∑共12工件，第i工件加工顺序在1到12之间，即121ijiy=∑。加工顺序为j是，一定有一个工件i，即121ijjy=∑。最优排列下第j次加工的时间121jijiibya==∑因此:问题1）的数学模型为目标函数:minZ=121iit=∑约束条件:1iijjtb==∑121ijiy=∑，121ijjy=∑121jijiibya==∑对此数学模型用lingo编程，运行程序即得完成这批工件的总时间和加工顺序，程序见附件-程序一-6-2）设P为工件的总价值，je在最优排列下第j种工件的价值，那么有：121maxjjPe==∑因为不要求每一种工件都加工，所以1211ijiy=≤∑，1211ijjy=≤∑因为第二问是在第一问的基础上，因此需要满足第一问的约束121jijiibya==∑，121jijiieyc==∑完工时间约束121jijiifyd==∑为i工件在从最优排列下加工所用的总时间需要小于完工时间，故ijtf≤（i=j）。综上所述可得问题2）的数学模型为目标函数：121maxjjPe==∑约束条件：1211ijiy=≤∑，1211ijjy=≤∑121jijiibya==∑，121jijiieyc==∑121jijiifyd==∑，ijtf≤(i=j)对此数学模型用lingo编程，运行程序即得完成这批工件的总价值以及相应的总时间和加工顺序，程序见附录-程序二5.2.对于问题二问题二要求完成任务使总时间最少，根据题意总时间为加工时间加上等待时间，所以有如下式子完成这批工件加工任务所需的总时间最少121minjjWs==∑其中js最优排列下第j种工件在完成钻工序的总时间111{ijijjjjijtntsssnts−=−−+≥+≤111stn=+it为i工件在从最优排列下车床加工所用的总时间1iijjtb==∑-7-ni为i工件在从最优排列下车床加工所用的总时间11jijinnym==∑mi为i工件的钻床加工时间，根据前面第一问可知还有如下约束∑==121iiijjayb，1211ijiy==∑，1211ijjy==∑因此问题二的数学模型可以表述为目标函数：121minjjWs==∑约束条件：111{ijijjjjijtntsssnts−=−−+≥+≤111stn=+1iijjtb==∑11jijinnym==∑∑==121iiijjayb，1211ijiy==∑，1211ijjy==∑对此数学模型用lingo编程，运行程序即得完成这批工件的最少总时间和加工顺序，程序见附件-程序三。5.3.对于问题三这是在问题一二上的推广，我们仍然按照第一问推广到第二问的方法，将第二问推广到第三问，设uj最优排列下第j种工件在完成铣床序的总时间那么最少的总时间121minjjWu==∑···································································(1)在最优排列下第j次在车床加工的时间121jijiibya==∑···············································(2)在最优排列下第j次在钻床加工的时间∑==11niijjmyn················································(3)在最优排列下第j次在铣床加工的时间∑==11niijjqyr···············································(4)共12工件，第i工件加工顺序在1到12之间，即121ijiy=∑··························(5)加工顺序为j是，一定有一个工件i，即121ijjy=∑·······································(6)-8-最优排列下第j次加工的时间121jijiibya==∑···························································(7)为i工件在从最