改善算法课程设计

Matlab课程设计实验报告组另U：第7组题 目：利用改善法求解工件加工问题业：自动化长：王继亮员：孙帅于润超于松

1305410121130541010413054101251305410115算法介绍改善算法基于启发式策略的改进解策略，即从一个初始解开始，通过一系列的替换.分解和合并的过程来逐步修正，以提高解的可接受性。在这个过程中，运用的是迭代改进的方法。每次迭代都从当前点出发，在当前点的邻域内选取一个新点，如果这个新点的评价值优于当前点，则它就变成当前点。否则就选取当前点邻域内的其他点来进行比较，直到没有改进的可能或者计算时间与成本变得不可忍受为止。改善法又称为局部探索法，俗称爬山法。改善法的核心环节在于当前点邻域的选择问题。一种极端的情形是随机的从可行解空间中选择一个潜在解，相当于完全随机探索，另一个极端的情形是将整个可行解空间作为当前点的邻域，相当于穷举搜索，解决现实问题应该避免上述两种极端情形。其折中情形就是在当前点的周围的某个合适大小的范围内进行搜索。如果邻域的范围较小，那么就可以快速搜索该邻域，但也可能陷入局部最优，相反，如果邻域的范围较大，就不容易陷入局部最优，但探索的效率会受到影响。因此，邻域的定义就变得十分重要。有两种邻域探索策略，其一是最初改善策略，即对邻域内随机探索，一旦发现改善解，就将现行解进行更新。其二是最大改善策略，即在对邻域内的所有解进行探索后，在选择最大的一个改善解，并用其对现行解。它是启发式算法的一种。邻域搜索算法，介绍了邻域搜索在工件加工调度问题中的应用.问题的启发式策略，针对现有的邻域搜索算法的缺点，研究如何改进邻域搜索的有关技术，提出了基于邻域搜索的，结合单机调度和拟物拟人思想的快速的启发式算法.为了说清楚所提算法的思想,提出了一些定义和定理，并严格证明了定理.提出了一调度规则以生成初始解，作为邻域搜索和回溯算法的出发点.利用拟物拟人的思想，构造出新的邻域.分析了移动瓶颈过程的子算法Schrage算法的优缺点，提出了一种改进的单机针对邻域搜索在计算的过程中经常会陷入局部极小值陷阱中提出的新邻域结构为基础,结合单机调度策略得到一个基于混合式邻域结构的搜索算法HNLS.混合邻域结构与单一邻域结构相比，有助于计算跳出局部极小值的陷阱，走向前景更好的区域，搜索到更好的解.启发式算法(heuristicalgorithm)是相对于最优化算法提出的。一个问题的最优算法求得该问题每个实例的最优解。启发式算法可以这样定义：一个基于直观或经验构造的算法，在可接受的花费(指计算时间和空间)下给出待解决组合优化问题每一个实例的一个可行解，该可行解与最优解的偏离程度不一定事先可以预计.计算机科学的两大基础日标，就是发现可证明其执行效率良好且可得最佳解或次佳解的算法。而启发式算法则试图一次提供一或全部日标。例如它常能发现很不错的解，但也没办法证明它不会得到较坏的解；它通常可在合理时间解出答案，但也没办法知道它是否每次都可以这样的速度求解。有时候人们会发现在某些特殊情况下，启发式算法会得到很坏的答案或效率极差，然而造成那些特殊情况的数据组合，也许永远不会在现实世界出现。因此现实世界中启发式算法常用来解决问题。启发式算法处理许多实际问题时通常可以在合理时间内得到不错的答案。有一类的通用启发式策略称为元启发式算法(metaheuristic)，通常使用乱数搜寻技巧。他们可以应用在非常广泛的问题上，但不能保证效率。近年来随着智能计算领域的发展，出现了一类被称为超启发式算法(Hyper-HeuristicAlgorithm)的新算法类型。最近几年，智能计算领域的著名国际会议(GECCO2009,CEC2010PPSN2010)[1]分别举办了专门针对超启发式算法的workshop或session。从GECCO2011开始，超启发式算法的相关研究正式成为该会议的一个领域(self*search-newfrontiertrack)。国际智能计算领域的两大著名期刊JournalofHeuristics和EvolutionaryComputation也在2010年和2012年分别安排了专刊，着重介绍与超启发式算法有关的研究进展。所谓的最短路径问题有很多种意思，在这里启发式指的是一个在一个搜寻树的节点上定义的函数h(n)，用于评估从此节点到日标节点最便宜的路径。启发式通常用于资讯充分的搜寻算法，例如最好优先贪婪算法与A*。最好优先贪婪算法会为启发式函数选择最低代价的节点；A*则会为g(n)+h(n)选择最低代价的节点，此g(n)是从起始节点到日前节点的路径的确实代价。如果 h(n)是可接受的(admissible)意即h(n)未曾付出超过达到目标的代价，则A*一定会找出最佳解。最能感受到启发式算法好处的经典问题是n-puzzle。此问题在计算错误的拼图图形，与计算任两块拼图的的总和以及它距离日的有多远时，使用了本算法。注意，上述两条件都必须在可接受的范围内。作为经典排序问题的推广，处理机的排序问题具有广泛的实际背景.对于日标函数是极小化排序时间表长度的情况,可以采用启发性的搜索方法。此文中根据所提的问题采用了局部搜索方法，对问题进行描述与解答，力求通过局部搜索问题的最优解或近似最优解。第一问的第（1）小问，为单机排序问题，利用SPT规则，按工件加工时间长短，从短到长顺序排列，可使平均流程时间最小。这种方法又称“最短加工时间规则”。应用SPT规则，可减少加工其它零件时它们的等待时间的和。得到的最优总时间为171.9h，加工次序为：J-J-J-J-J-J-J-J-J-J-J-J639710512811412或者J-J-J-J-J-J-J-J-J-J-J-J6 3 9 10 7 5 1 2 8 11 4 12第一问的第（2）小问，要求规定的完工时间内，选择完成工件，使获得的价值量最大。很容易可以得到，最优解的加工次序必然可以通过调换得到工件的完工时间先后的顺序一致。从而建立一个0—1规划模型，求得最优解MAXU=117，选择的工件和加工次序为：J-J-J-J-J-J-J-J-J-J9 1 12 3 7 10 6 4 11 8第二，三问中要求工件的加工顺序使得加工工件的总时间最短。加工工件的总时间等于每个工件的加工时间与加工其他工件时它的等待时间的和。而问题中的工件的加工时间是一定的，因此问题可以转化为求等待时间的最小。建立等待时间的目标函数，把工件按在第一台机器的加工时间的升序进行一个重新排列，得到的新序列，通过局部的交换工件的次序，再比较等待时间，若时间段则继续进行迭代，否则继续交换工件的加工次序，直到所有的工件的顺序交换完为止。这样可以得到第二问的总加工时间的最优值为：225.6h。工件加工的总周期为：35h。加工次序为：J-J-J-J-J-J-J-J-J-J-J-J6 2 7 3 10 5 1 4 9 8 11 12第三问的总加工时间的最优值为：242.5h。工件加工的总周期为：35.7h。加工次序为：j-j-j-j-j-j-j-j-j-j-j-j。3 6 2 7 10 5 1 8 11 9 4 12计划排序问题中的车间作业问题，研究n个工件在m台机器上有序的加工问题，每个工件都有完工的日期（DD，Duedate），加工的时间（PT，Processingtime）和工件的价值（VAL，Valueifjobisselected）.车间作业计划研究一个工厂生产工序的计划和安排，需要计划与合理安排各个工件在这些机器上加工的先后次序，即拟订加工工序，通过各个工件在各种机器上加工次序的合理安排，使得完成这批工件加工任务所需的总时间最省（注：总时间即为各个零件的加工时间和加工其他零件时它们等待时间之和）或要求整个选择加工的工件价值最大。有一个工厂现在有12种工件（编号为工件1，工件2，…，工件12）需要在车床，钻床，铣床几种不同的设备上加工。考虑下面的工件加工的排序问题：（一）这12种工件都要求在车床上加工，车床一次只能加工一种工件，这12种工件加工所需时间，每个工件的完工时间和每个工件的价值如表（1）所示：1） 不考虑工件的完工时间和工件的价值，建立数学模型，为该工厂安排工件加工的次序，使得完成这批工件加工任务所需的总时间最省。2） 由于工件必须在它们要求的时间内完工，按照表（1）的数据，建立数学模型，为该工厂安排选择加工工件的种类及加工的次序，使得整个选择加工的工件价值最大。（二）如果这12种工件都要求先在车床上加工，然后再在钻床上加工（即工件在钻床加工之前必须先在车床上加工过），每种机器一次只能加工一种工件，这12种工件加工所需时间如表（2）所示：建立数学模型，为该工厂安排工件加工的次序，使得完成这批工件加工任务所需的总时间最省。（三）如果这12种工件都要求先在车床上加工，然后再在钻床上加工，最后再在铣床上加工，每种机器一次只能加工一种工件，这12种工件加工所需时间如表（三）所示：建立数学模型，为该工厂安排工件加工的次序，使得完成这批工件加工任务所需的总时间最省。1、 是在工作过程中是不会出现故障的，且第一个机器为连续作业安排，无需等待时间，故闲置时间为零；2、 作业系列已知，处理过程开始后不再有新作业，作业不会被撤消，不存在加工过程的中断，如机器故障、意外事故等；3、 工件在每一台机器上的加工次序是不变的，即在第一台机器上加工的第i个工件排在第j个工件前，则在第二台机器上加工，第i个工件也排在第j个工件前。4、 对加工任务所需总时间的理解有两种：①总时间即为各个零件的加工时间和加工其他零件时它们等待时间之和；②从第一个工件加工开始算起到最后一个工件加工完成所用的时间。这里对问题的求解都采用第一种理解。符号说明P——是一个mxn矩阵，其元素pj表示工件J•在机器吃上加工的时间；pj——表示工件，•在机器吃上加工的时间；c 工件的数量t^——工件i完工时间L^——最迟加工时间，表示工件i的完工时间减去工件i的加工时间MAXU 最大工件价值量x=1 表示第i个工件被选上x^=0——表示第i个工件没有被选上v•——表示加工工件j的价值量Q——表示按完工时间先后排列后工件k的加工时间T——工件的总加工时间q»——工件的一个重新排序后工件J在机器心/上加工的间Tp——工件的加工时间之和T——工件的等待时间之和g——第i台机器在加工第j个工件时的机器等待时间w——第i个工件的等待时间i问题一：N个工件在一台设备上的加工的作业排序。单一设备（单工序）排序是作业的排序最简单,最基本的问题。显然，当N个工件在一台设备上进行加工时，可能有N！种排序方案。但是，不管是哪种方案，N个工件的最大流程时间是固定值，即与工件的加工先后排序无关。所以，单一设备的优化排序评价标准，通常是平均流程时间最小，最大拖期量最小或者为零。⑴单一机床的零件加工排序问题可按以下规则进行。SPT规则按工件加工时间长短，从短到长顺序排列，可使平均流程时间最小。这种方法又称“最短加工时间规则”。应用SPT规则，可减少在制品占用量，节省流动资金。由于未考虑交货期，有可能产生交货延迟现象。同时也可以考虑建立目标函数，MinC=史kx七其中七为J*k=1的一个排列。(2)由于工件都有各自的完工时间限制，和不同的加工时间，显然，主要的约束条件是完工时间。工件的加工顺序是于完工时间的排列顺序一致。若不一致我们可以调换其中不一致的工件加工顺序。TOC\o"1-5"\h\z在j,j都能在规定的完工时间内完成时，假如工件j的完工时间ii+1 i为t,j的完工时间为t,j排在j之前且t>t,那么此时调换ii+1 i+1i i+1 ii+1j,j的顺序，将不会造成j无法在规定的时间完成。因为有条件ii+1 it>t+1保证。因此，可以肯定工件的加工顺序于完工时间的排列顺序一致。这只是充分条件，不是必要条件。引进最迟加工时间L=t—p所以我们对数据做了一个按完工时间先后的重新排列的处理并对其重新编号，得到下表：新序号工件加工时间(h)完工时间(h)工件价值最迟加工时间191.7775.3223.27.544.3312.8986.2452.71077.35124.711186.3631.2151613.8772.5171714.58102.5181215.5960.9222021.110442331911113.625521.41283.3331129.7模型的建立：引进12个0-1变量，尤(i=1,2,・・・，12),x=1表示第i个工件被选上,x=0表示第i个工件没有被选上，建立目标函数:MAXU=Z七Xx,i=1u为加工工件/.的价值量。约束条件是对工件/加工的开始时间必须小于最迟开工时间，而工件的开始加工时间等于加工工件七到j所用的时间，对于工件j的开始加工时间应该等于如Qxx，所i-1 i kkk=1以可以得到12个约束条件：s.t.(EQXx)Xx<L(i=1,2,・・・，12)。kkiik=1这样就建立了一个0-1规划问题.该题目所求的总时间即为各个零件的加工时间和加工其他零件时它们等待时间之和，由于对每一个工件的加工都必须经过2台机器的加工，即他们的加工时间为：T=EE。p「。Pj=1i=1j所以对于任一种工件的加工次序，他们的加工时间总和是不变的。该题是求加工次序使得加工工件的总时间最小，即求

min:T=Tp+「，而气是一定的，因此问题等价于求工件的等待时间\最小。分析任一种加工次序的等待时间如下：第一个工件的等待时间为0，因为该工件从第一台机器加工完立刻进入第二台机器加工，直到该工件加工完成。所以有：吗=g21=0第二个工件的等待时间为第一个工件在第一台机器的加工时间，加上工件在第一台机器加工完成后在第二台机器的加工时间减去第二个工件在第一台机器的时间于0的最大值，即：W=q+Max{0,q一q+g}2 11 12 21 11如果q12一q21<0则第二台机器存在机器的等待时间:21-1X(q12-q21+g11)21否则即第三个工件的等待时间为:g21=0g=max{0,—1x(q—q+g)}22 12 21 11W=q+q+Max{0,q+q—q—q+g+g}3 11 21 12 22 21 31 21 22此时的机器等待时间为：g=max{0,—1x(q+q—q—q+g+g)}23 12 22 21 31 21 22

第四个工件的等待时间为:TOC\o"1-5"\h\zW=q+q+q+Max{0,q+q+q—q—q—q+g+g+g}4 11 21 31 12 22 32 21 31 41 21 22 23机器等待时间为：g=Max{0,—1x(q+q+q—q—q—q+g+g+g)}

24 12 22 32 21 31 41 21 22 23第五个工件的等待时间为：W=q+q+q+q+Max{0,q+q+q+q—q—q—q—q+g+g+g+g}11 21 31 41 12 22 32 42 21 31 41 51 21 22 23 24机器等待时间为：g=Max{0,—1x(q+q+q+q—q—q—q—q+g+g+g+g)}25 12 22 32 42 21 31 41 51 21 22 23 24第i个工件的等待时间为:W=2q+Max{0划q—£q-Eg}i k1 k2 k1 2kk=1 k=1 k=2 k=1g,.2i此时的机器等待时间为：g2=Max{0,-1x（Eqk广工九一归g次）}k=1 k=2 k=1g,.2i从而建立目标函数：min:从而建立目标函数：min:T=T+T=EEp.+Ewk.j=1i=1 k=1相对第二问，该问只是增加了机器的台数，其他条件不变，因此这里的机器等待时间有两个，即第二台机器的等待时间和第三台机器的等待时间。分析任一种加工次序的等待时间如下：第一个工件的等待时间为0，因为该工件从第一台机器加工完立刻进入第二台机器加工，再到第三台机器，直到该工件加工完成。所以有：W]=g21=g31=0第二个工件的等待时间为TOC\o"1-5"\h\zW=q+Max{0,q—q+g}+Max{0,q—q+g—g}

2 11 12 21 21 13 22 31 21此时第二台机器的等待时间为：g=Max{0,-1x(q—q+g)}22 12 21 21第三台机器的等待时间为：g=Max{0,-1x(q—q+g—g)}32 13 22 31 21第三个工件的等待时间为：W=q+q+Max{0,q+q—q—q+g+g}

3 11 21 12 22 21 31 21 22+Max{0,q+q—q—q+g+g—g—g}13 23 22 32 31 32 21 22此时第二台机器的等待时间为：g=Max{0,—1x(q+q—q—q+g+g)}

23 12 22 21 31 21 22第三台机器的等待时间为：g=Max{0,—1x(q+q—q—q+g+g—g—g)}

33 13 23 22 32 31 32 21 22第四个工件的等待时间为：W=q+q+q+Max{0,q+q+q—q—q—q+g+g+g}4 11 21 31 12 22 32 21 31 41 21 22 23+Max{0,q+q+q—q—q—q+g+g+g—g—g—g}13 23 33 22 32 42 31 32 33 21 22 23此时第二台机器的等待时间为：g=Max{0,—1x(q+q+q—q—q—q+g+g+g)}

24 12 22 32 21 31 41 21 22 23第三台机器的等待时间为：g=Max{0,—1x(q+q+q—q—q—q+g+g+g—g—g—g)}34 13 23 33 22 32 42 31 32 33 21 22 23第i个工件的等待时间为:,归qk3习矣疽归g疽如g2k}k=1 k=2 k=1 ,归qk3习矣疽归g疽如g2k}k=1 k=2 k=1 k=1i k1 k2 k1 2kk=1 k=1 k=2 k=1此时第二台机器的等待时间为:g=Max{0,-1x(Eqk=1-Eqk1+Eg2k)}k=2 k=1第三台机器的等待时间为:g=Max{0,—1x(Eq—£q+Eg—Eg)}TOC\o"1-5"\h\z3i k3 k2 3k 2kk=1 k=2 k=1 k=1同理建立目标函数：min:T—T+T=E£p..+Ewj=1i=1 k=1模型求解问题一:工件加工时间(h)完工时间(h)工件价值12.89823.27.5431.215164423352.710760.9222072.5171783.3331191.777102.51812113.6255124.71118解：（1）12种工件的排序分析过程如下:加工周期lax=''=33.1，这是一定的，与工件的加工顺序无关。按照上述的SPT规则，加工顺序为J—J—J—J—J—J—J—J—J—J—J—J或为6 3 9 7 10 5 1 2 8 11 4 12 次八J—J—J—J—J—J—J—J—J—J—J—J 禾呈日寸问3 9 10 7 5 1 2 8 11 4 12，平均流程时间最小。完成这批工件加工任务所需的总时间最小为：Cmin=171.9。（2）为了利用数学软件LINGO求解，我们简化约束条件的形式:(i=1,2,・・・，12)尸Qxx+100xx<L+100(i=1,2,・・・，12)TOC\o"1-5"\h\zkk iik=1利用LINGO可以求得x=1，x=0，x=1，x=0，x=1，x=1，x=1，x=1，x=1，x=1，x=1，x=1。MaxU=117。对照8 9 10 11 12重新排列的表格可以得到不选择加工的工件为：J?和J5，即加工的次序为：J-J-J-J-J-J-J-J-J-J

9 1 12 3 7 10 6 4 11 8所获得的最大价值量为117。

问题二，二:对二三问，我们采取相同的方法解决，首先对Tw=lLWk进行分k=1析，问题二中：T=E(12—i)xq+EMax{0,Eq—Eq—Eg}TOC\o"1-5"\h\zw i1 k2 k1 2ki=1 i=2 k=1 k=2 k=1问题二中:T=E(12—i)xq+EMax{0,Eq—Eq—Eg}k=1w i1 k2 kk=1i=1 i=2 k=1 k=2+EMax{0,Eq—Eq+Eg-Eg}i=2 k=1 k=2 k=1 k=1其中g=Max{0,—1x(Eq—Eq+Eg)}其中2i k2 k1 2kk=1 k=2 k=1g=Max{0,—1x(Eq—£q+Eg—Eg)}3i k3 k2 3k 2kk=1 k=2 k=1 k=1为了使得总等待时间最小，我们不妨把等待时间分为两部分:即:E(12—i)xq和区Max{0,Eq—£q-2g}或者i1 k2 k1 2ki=1 i=2 k=1 k=2 k=1EMax{0,如q—Eq—Eg}+EMax{0,Eq—£q+Eg—Eg}k2 k1 2k k3 k2 3k 2ki=2 k=1 k=2 k=1 i=2 k=1 k=2 k=1 k=1很显然，后面部分依赖于工件的排列，而前面E(12T)xq、则可i=1以通过第一问的结论得到最小值，即将工件在第一台机器的加工时间按升序排列，就可以使得E(12-i)xq〃最小。加工次序如下:i=1

工件车床加工时间(h)钻床加工时间(h)60.94.531.21.891.74.572.51.7102.52.552.7312.8423.21.383.32.5113.63.8442.2124.71.9工件车床加工时间(h)钻床加工时间(h)铣床加工时间(h)60.94.591.74.51

52.731.812.84323.21.3442.21.3然后进行工件顺序的交换，进程如下：第一步，令i=1,j=1第二步，计算此时T的值0第三步，交换第i个位置和第i+j个位置上的工件，计算T的值，若T>T0进入第四步，否则T=T0，进入第一步第四步，交换回第i个位置和第i+j个位置上的工件，i++,如果i=13-j,则i=1,j++,进入第五步第五步，如果j=12,结束，否则回到第三步第二问的总加工时间的最优值为：225.6h。工件加工的总周期为：35h。加工次序为：J-J-J-J-J-J-J-J-J-J-J-J6 2 7 3 10 5 1 4 9 8 11 12第三问的总加工时间的最优值为：242.5h。