工件加工的排序问题

1、工件加工的排序问题摘要作为经典排序问题的推广,处理机的排序问题具有广泛的实际背景.对于目标函数是极小化排序时间表长度的情况,可以采用启发性的搜索方法。此文中根据所提的问题采用了局部搜索方法，对问题进行描述与解答，力求通过局部搜索问题的最优解或近似最优解。第一问的第（1）小问，为单机排序问题，利用Spt规则，按工件加工时间长短，从短到长顺序排列，可使平均流程时间最小。这种方法又称“最短加工时间规则”应用SPT规则，可减少加工其它零件时它们的等待时间的和。得到的最优总时间为171.9h，加工次序为：J-J-J-J-J-J-J-J-J-J-J-J639710512811412或者J-J-J-J-J-

2、J-J-J-J-J-J-J6391075128114第一问的第（2）小问，要求规定的完工时间内，选择完成工件，使获得的价值量最大。很容易可以得到，最优解的加工次序必然可以通过调换得到工件的完工时间先后的顺序一致。从而建立一个0T规划模型，求得最优解MAXU=117,选择的工件和加工次序为：J-J-J-J-J-J-J-J-J-J9112371064118第二，三问中要求工件的加工顺序使得加工工件的总时间最短。加工工件的总时间等于每个工件的加工时间与加工其他工件时它的等待时间的和。而问题中的工件的加工时间是一定的，因此问题可以转化为求等待时间的最小。建立等待时间的目标函数，把工件按在第一台机器的加

3、工时间的升序进行一个重新排列，得到的新序列，通过局部的交换工件的次序，再比较等待时间，若时间段则继续进行迭代，否则继续交换工件的加工次序，直到所有的工件的顺序交换完为止。这样可以得到第二问的总加工时间的最优值为：225.6h。工件加工的总周期为：35h。加工次序为：J-J-J-J-J-J-J-J-J-J-J-J627310514981112第三问的总加工时间的最优值为：242.5h。工件加工的总周期为：35.7h。加工次序为：J-J-J-J-J-J-J-J-J-J-J-J。362710518119412关键字SPT规则加工时间工件等待时间机器等待时间局部搜索问题重述计划排序问题中的车间作业问题

4、，研究n个工件在m台机器上有序的加工问题，每个工件都有完工的日期（DD，Duedate），加工的时间（PT，Processingtime）和工件的价值（VAL,Valuefjobisselected）.车间作业计划研究一个工厂生产工序的计划和安排，需要计划与合理安排各个工件在这些机器上加工的先后次序，即拟订加工工序，通过各个工件在各种机器上加工次序的合理安排，使得完成这批工件加工任务所需的总时间最省（注：总时间即为各个零件的加工时间和加工其他零件时它们等待时间之和）或要求整个选择加工的工件价值最大。有一个工厂现在有12种工件（编号为工件1，工件2，工件12）需要在车床，钻床，铣床几种不同的设备

5、上加工。考虑下面的工件加工的排序问题：（一）这12种工件都要求在车床上加工，车床一次只能加工一种工件，这12种工件加工所需时间，每个工件的完工时间和每个工件的价值如表（1）所示：1）不考虑工件的完工时间和工件的价值，建立数学模型，为该工厂安排工件加工的次序，使得完成这批工件加工任务所需的总时间最省。2）由于工件必须在它们要求的时间内完工，按照表（1）的数据，建立数学模型，为该工厂安排选择加工工件的种类及加工的次序，使得整个选择加工的工件价值最大。（二）如果这12种工件都要求先在车床上加工，然后再在钻床上加工（即工件在钻床加工之前必须先在车床上加工过），每种机器一次只能加工一种工件，这12种工件

6、加工所需时间如表（2）所示：建立数学模型，为该工厂安排工件加工的次序，使得完成这批工件加工任务所需的总时间最省。（三）如果这12种工件都要求先在车床上加工，然后再在钻床上加工，最后再在铣床上加工，每种机器一次只能加工一种工件，这12种工件加工所需时间如表（三）所示：建立数学模型，为该工厂安排工件加工的次序，使得完成这批工件加工任务所需的总时间最省。模型假设1、是在工作过程中是不会出现故障的，且第一个机器为连续作业安排，无需等待时间，故闲置时间为零；2、作业系列已知，处理过程开始后不再有新作业，作业不会被撤消，不存在加工过程的中断，如机器故障、意外事故等；3、工件在每一台机器上的加工次序是不变的

7、，即在第一台机器上加工的第i个工件排在第j个工件前，则在第二台机器上加工，第i个工件也排在第j个工件前。4、对加工任务所需总时间的理解有两种：总时间即为各个零件的加工时间和加工其他零件时它们等待时间之和；从第一个工件加工开始算起到最后一个工件加工完成所用的时间。这里对问题的求解都采用第一种理解。符号说明P是个mxn矩阵，其元素pj表示工件J在机器“j上加工的时间pij表示工件J在机器Mj上加工的时间；c工件的数量ti工件i完工时间Li最迟加工时间，表示工件i的完工时间减去工件i的加工时间MAXU最大工件价值量x二i1表示第i个工件被选上x二i0表示第i个工件没有被选上vi表示加工工件j的价值量

8、iQk表示按完工时间先后排列后工件k的加工时间T工件的总加工时间qij工件的一个重新排序后工件J在机器Mj上加工的时间Tp工件的加工时间之和Tw工件的等待时间之和gij第i台机器在加工第j个工件时的机器等待时间W第i个工件的等待时间i模型分析与模型建立问题一:N个工件在一台设备上的加工的作业排序。单一设备（单工序）排序是作业的排序最简单,最基本的问题。显然，当N个工件在一台设备上进行加工时，可能有N!种排序方案。但是，不管是哪种方案,N个工件的最大流程时间是固定值，即与工件的加工先后排序无关。所以，单一设备的优化排序评价标准，通常是平均流程时间最小，最大拖期量最小或者为零。单一机床的零件加工排

9、序问题可按以下规则进行。SPT规则按工件加工时间长短，从短到长顺序排列，可使平均流程时间最小。这种方法又称“最短加工时间规则”应用SPT规则，可减少在制品占用量，节省流动资金。由于未考虑交货期，有可能产生交货延迟现象。同时也可以考虑建立目标函数，MinC=弋kxy其中y为J的一个排kkkk=1列。(2)由于工件都有各自的完工时间限制,和不同的加工时间,显然,主要的约束条件是完工时间。工件的加工顺序是于完工时间的排列顺序一致。若不一致我们可以调换其中不一致的工件加工顺序。在j,j都能在规定的完工时间内完i+1成时,假如工件j的完工时间为t,j的完工时间为t,j排在j之前且ii+1i+1ii+1t

10、t,那么此时调换j,j的顺序,将不会造成j无法在规定的时间完成。因为i+1ii+1i有条件tt保证。因此，可以肯定工件的加工顺序于完工时间的排列顺序一ii+1致。这只是充分条件，不是必要条件。引进最迟加工时间L=tpiii所以我们对数据做了一个按完工时间先后的重新排列的处理并对其重新编号，得到下表：新序号工件加工时间(h)完工时间(h)工件价值最迟加工时间191.7775.3223.27.544.3312.8986.2452.71077.35124.711186.3631.2151613.8772.5171714.58102.5181215.5960.9222021.1104423319111

11、13.625521.41283.3331129.7模型的建立：引进12个0-1变量，x(i=1，2，12)，x=1表示第i个工件被选ii上,x二0表示第i个工件没有被选上，建立目标函数:MAXU=昱vXxiiii=1v为加工工件j的价值量。约束条件是对工件j加工的开始时间必须小于最迟开iii工时间，而工件的开始加工时间等于加工工件j到j所用的时间，对于工件j的1i-1i开始加工时间应该等于迟Qxx，所以可以得到12个约束条件：kkk=1s.t.(迟QL(i=1,2,12)。kkiik=1这样就建立了一个0-1规划问题。问题二：该题目所求的总时间即为各个零件的加工时间和加工其他零件时它们等待时间

12、之和，由于对每一个工件的加工都必须经过2台机器的加工，即他们的加工时间为：T=茧cp。pijj=1i=1所以对于任一种工件的加工次序，他们的加工时间总和是不变的。该题是求加工次序使得加工工件的总时间最小，即求min:T=T+T，而T是一定的，因此pwp问题等价于求工件的等待时间T最小。w分析任一种加工次序的等待时间如下：第一个工件的等待时间为0，因为该工件从第一台机器加工完立刻进入第二台机器加工，直到该工件加工完成。所以有：W=g=0121第二个工件的等待时间为第一个工件在第一台机器的加工时间，加上工件在第一台机器加工完成后在第二台机器的加工时间减去第二个工件在第一台机器的时间于0的最大值，即

13、：W=q+Max0,q一q+g11122111如果q12-q210则第二台机器存在机器的等待时间:g21=1x(qq+g)122111否则g21=021即g=max0,1x(qq+g)22122111第三个工件的等待时间为：W二q+q+Max0,q+qqq+g+g1121122221312122此时的机器等待时间为：g二max0,1x(q+qqq+g+g)23122221312122第四个工件的等待时间为：W二q+q+q+Max0,q+q+qqqq+g+g+g112131122232213141212223机器等待时间为：24一q41+g21+g22+g23)=Max0,一1x(q+q+q一q

14、一q1222322131第五个工件的等待时间为：W二q+q+q+q+Max0,q+q+q+qqqqq+g+g+g+g11213141122232422131415121222324机器等待时间为：g=Max0,1x(q+q+q+qqqqq+g+g+g+g)25122232422131415121222324第i个工件的等待时间为：W=艺qik1k=1+Max0,艺qk2k=1工qk1k=2-迟g2kk=1此时的机器等待时间为：g=Max0,1x(EqYq迟g)TOC o 1-5 h z2ik2k12kk=1k=2k=1 HYPERLINK l bookmark62 从而建立目标函数：min:T

15、=T+T=p+EWpwijkj=1i=1k=1问题三：相对第二问，该问只是增加了机器的台数，其他条件不变，因此这里的机器等待时间有两个，即第二台机器的等待时间和第三台机器的等待时间。分析任一种加工次序的等待时间如下：第一个工件的等待时间为0，因为该工件从第一台机器加工完立刻进入第二台机器加工，再到第三台机器，直到该工件加工完成。所以有：W=g=g=012131第二个工件的等待时间为W=q+Max0,qq+g+Max0,qq+gg1112212113223121此时第二台机器的等待时间为：g=Max0,1x(qq+g)122121第三台机器的等待时间为：g=Max0,1x(qq+gg)32132

16、23121第三个工件的等待时间为：W=q+q+Max0,q+qqq+g+gTOC o 1-5 h z1121122221312122 HYPERLINK l bookmark44 +Max0,q+qqq+g+ggg1323223231322122此时第二台机器的等待时间为：g=Max0,1x(q+qqq+g+g)122221312122第三台机器的等待时间为：g=Max0,1x(q+qqq+g+ggg)331323223231322122第四个工件的等待时间为：23g+22g+112g+114q31q112q23q+22q+2W二q+q+q+Max0,4112131+Max0,33q+32q+

17、333g+23g+g+q32g此时第二台机器的等待时间为：g二Max0,1x(q+q+qqqq+g+g+g)24122232213141212223第三台机器的等待时间为：g34=Max0,1x(q+q+qqqq+g+g+g132333223242313233g21g22g23)第i个工件的等待时间为:W=Sq+Max0,Sq_工q+ik1k2k1k=1k=1k=2迟g+Max02kk=1,Sq3_Sq2+Sg3_Sg2k23k2kk=2k=1k=1k3k=1_Sq+Sgk1k=2k=12k)此时第二台机器的等待时间为：g=Max0,_1x(SqTOC o 1-5 h zik2k=1第三台机器

18、的等待时间为：g=Max0,_1x(Sq_Sq+Sg_Sg)3ik3k23k2kk=1k=2k=1k=1同理建立目标函数：min:T=T+T=SSp+SWpwijkj=1i=1k=1模型求解问题一：工件加工时间（h）完工时间（h）工件价值12.89823.27.5431.215164423352.710760.9222072.5171783.3331191.777102.51812113.6255124.71118解：（1）12种工件的排序分析过程如下：F=St=33.1加工周期maxi，这是一定的，与工件的加工顺序无关。按照上述的SPT规则，加工顺序为J_J_J_J_J_J_J_J_J_J_J_J39710512811412或为J6_J3_J9_J10_J7_J5_J1_J2_J8_J11_J4_J12，平均流程时间最小完成这批工件加工任务所需的总时间最小为：Cmin=171.9。（2）为了利用数学软件LINGO求解，我们简化约束条件的形式:k=1Xx+100XxT进入第四步，否则T=T,进入第一步0第四步，交换回第i个位置和第i+j个位置上的工件，i+,如果i=13-j,则i=l,j+,进入第五步第五