改善算法課程設(shè)計(jì)

Matlab課程設(shè)計(jì)實(shí)驗(yàn)報(bào)告組另U：第7組題 目：利用改善法求解工件加工問(wèn)題業(yè)：自動(dòng)化長(zhǎng)：王繼亮員：孫帥于潤(rùn)超于松

1305410121130541010413054101251305410115算法介紹改善算法基于啟發(fā)式策略的改進(jìn)解策略，即從一個(gè)初始解開(kāi)始，通過(guò)一系列的替換.分解和合并的過(guò)程來(lái)逐步修正，以提高解的可接受性。在這個(gè)過(guò)程中，運(yùn)用的是迭代改進(jìn)的方法。每次迭代都從當(dāng)前點(diǎn)出發(fā)，在當(dāng)前點(diǎn)的鄰域內(nèi)選取一個(gè)新點(diǎn)，如果這個(gè)新點(diǎn)的評(píng)價(jià)值優(yōu)于當(dāng)前點(diǎn)，則它就變成當(dāng)前點(diǎn)。否則就選取當(dāng)前點(diǎn)鄰域內(nèi)的其他點(diǎn)來(lái)進(jìn)行比較，直到?jīng)]有改進(jìn)的可能或者計(jì)算時(shí)間與成本變得不可忍受為止。改善法又稱(chēng)為局部探索法，俗稱(chēng)爬山法。改善法的核心環(huán)節(jié)在于當(dāng)前點(diǎn)鄰域的選擇問(wèn)題。一種極端的情形是隨機(jī)的從可行解空間中選擇一個(gè)潛在解，相當(dāng)于完全隨機(jī)探索，另一個(gè)極端的情形是將整個(gè)可行解空間作為當(dāng)前點(diǎn)的鄰域，相當(dāng)于窮舉搜索，解決現(xiàn)實(shí)問(wèn)題應(yīng)該避免上述兩種極端情形。其折中情形就是在當(dāng)前點(diǎn)的周?chē)哪硞€(gè)合適大小的范圍內(nèi)進(jìn)行搜索。如果鄰域的范圍較小，那么就可以快速搜索該鄰域，但也可能陷入局部最優(yōu)，相反，如果鄰域的范圍較大，就不容易陷入局部最優(yōu)，但探索的效率會(huì)受到影響。因此，鄰域的定義就變得十分重要。有兩種鄰域探索策略，其一是最初改善策略，即對(duì)鄰域內(nèi)隨機(jī)探索，一旦發(fā)現(xiàn)改善解，就將現(xiàn)行解進(jìn)行更新。其二是最大改善策略，即在對(duì)鄰域內(nèi)的所有解進(jìn)行探索后，在選擇最大的一個(gè)改善解，并用其對(duì)現(xiàn)行解。它是啟發(fā)式算法的一種。鄰域搜索算法，介紹了鄰域搜索在工件加工調(diào)度問(wèn)題中的應(yīng)用.問(wèn)題的啟發(fā)式策略，針對(duì)現(xiàn)有的鄰域搜索算法的缺點(diǎn)，研究如何改進(jìn)鄰域搜索的有關(guān)技術(shù)，提出了基于鄰域搜索的，結(jié)合單機(jī)調(diào)度和擬物擬人思想的快速的啟發(fā)式算法.為了說(shuō)清楚所提算法的思想,提出了一些定義和定理，并嚴(yán)格證明了定理.提出了一調(diào)度規(guī)則以生成初始解，作為鄰域搜索和回溯算法的出發(fā)點(diǎn).利用擬物擬人的思想，構(gòu)造出新的鄰域.分析了移動(dòng)瓶頸過(guò)程的子算法Schrage算法的優(yōu)缺點(diǎn)，提出了一種改進(jìn)的單機(jī)針對(duì)鄰域搜索在計(jì)算的過(guò)程中經(jīng)常會(huì)陷入局部極小值陷阱中提出的新鄰域結(jié)構(gòu)為基礎(chǔ),結(jié)合單機(jī)調(diào)度策略得到一個(gè)基于混合式鄰域結(jié)構(gòu)的搜索算法HNLS.混合鄰域結(jié)構(gòu)與單一鄰域結(jié)構(gòu)相比，有助于計(jì)算跳出局部極小值的陷阱，走向前景更好的區(qū)域，搜索到更好的解.啟發(fā)式算法(heuristicalgorithm)是相對(duì)于最優(yōu)化算法提出的。一個(gè)問(wèn)題的最優(yōu)算法求得該問(wèn)題每個(gè)實(shí)例的最優(yōu)解。啟發(fā)式算法可以這樣定義：一個(gè)基于直觀或經(jīng)驗(yàn)構(gòu)造的算法，在可接受的花費(fèi)(指計(jì)算時(shí)間和空間)下給出待解決組合優(yōu)化問(wèn)題每一個(gè)實(shí)例的一個(gè)可行解，該可行解與最優(yōu)解的偏離程度不一定事先可以預(yù)計(jì).計(jì)算機(jī)科學(xué)的兩大基礎(chǔ)日標(biāo)，就是發(fā)現(xiàn)可證明其執(zhí)行效率良好且可得最佳解或次佳解的算法。而啟發(fā)式算法則試圖一次提供一或全部日標(biāo)。例如它常能發(fā)現(xiàn)很不錯(cuò)的解，但也沒(méi)辦法證明它不會(huì)得到較壞的解；它通?？稍诤侠頃r(shí)間解出答案，但也沒(méi)辦法知道它是否每次都可以這樣的速度求解。有時(shí)候人們會(huì)發(fā)現(xiàn)在某些特殊情況下，啟發(fā)式算法會(huì)得到很壞的答案或效率極差，然而造成那些特殊情況的數(shù)據(jù)組合，也許永遠(yuǎn)不會(huì)在現(xiàn)實(shí)世界出現(xiàn)。因此現(xiàn)實(shí)世界中啟發(fā)式算法常用來(lái)解決問(wèn)題。啟發(fā)式算法處理許多實(shí)際問(wèn)題時(shí)通常可以在合理時(shí)間內(nèi)得到不錯(cuò)的答案。有一類(lèi)的通用啟發(fā)式策略稱(chēng)為元啟發(fā)式算法(metaheuristic)，通常使用亂數(shù)搜尋技巧。他們可以應(yīng)用在非常廣泛的問(wèn)題上，但不能保證效率。近年來(lái)隨著智能計(jì)算領(lǐng)域的發(fā)展，出現(xiàn)了一類(lèi)被稱(chēng)為超啟發(fā)式算法(Hyper-HeuristicAlgorithm)的新算法類(lèi)型。最近幾年，智能計(jì)算領(lǐng)域的著名國(guó)際會(huì)議(GECCO2009,CEC2010PPSN2010)[1]分別舉辦了專(zhuān)門(mén)針對(duì)超啟發(fā)式算法的workshop或session。從GECCO2011開(kāi)始，超啟發(fā)式算法的相關(guān)研究正式成為該會(huì)議的一個(gè)領(lǐng)域(self*search-newfrontiertrack)。國(guó)際智能計(jì)算領(lǐng)域的兩大著名期刊JournalofHeuristics和EvolutionaryComputation也在2010年和2012年分別安排了專(zhuān)刊，著重介紹與超啟發(fā)式算法有關(guān)的研究進(jìn)展。所謂的最短路徑問(wèn)題有很多種意思，在這里啟發(fā)式指的是一個(gè)在一個(gè)搜尋樹(shù)的節(jié)點(diǎn)上定義的函數(shù)h(n)，用于評(píng)估從此節(jié)點(diǎn)到日標(biāo)節(jié)點(diǎn)最便宜的路徑。啟發(fā)式通常用于資訊充分的搜尋算法，例如最好優(yōu)先貪婪算法與A*。最好優(yōu)先貪婪算法會(huì)為啟發(fā)式函數(shù)選擇最低代價(jià)的節(jié)點(diǎn)；A*則會(huì)為g(n)+h(n)選擇最低代價(jià)的節(jié)點(diǎn)，此g(n)是從起始節(jié)點(diǎn)到日前節(jié)點(diǎn)的路徑的確實(shí)代價(jià)。如果 h(n)是可接受的(admissible)意即h(n)未曾付出超過(guò)達(dá)到目標(biāo)的代價(jià)，則A*一定會(huì)找出最佳解。最能感受到啟發(fā)式算法好處的經(jīng)典問(wèn)題是n-puzzle。此問(wèn)題在計(jì)算錯(cuò)誤的拼圖圖形，與計(jì)算任兩塊拼圖的的總和以及它距離日的有多遠(yuǎn)時(shí)，使用了本算法。注意，上述兩條件都必須在可接受的范圍內(nèi)。作為經(jīng)典排序問(wèn)題的推廣，處理機(jī)的排序問(wèn)題具有廣泛的實(shí)際背景.對(duì)于日標(biāo)函數(shù)是極小化排序時(shí)間表長(zhǎng)度的情況,可以采用啟發(fā)性的搜索方法。此文中根據(jù)所提的問(wèn)題采用了局部搜索方法，對(duì)問(wèn)題進(jìn)行描述與解答，力求通過(guò)局部搜索問(wèn)題的最優(yōu)解或近似最優(yōu)解。第一問(wèn)的第（1）小問(wèn)，為單機(jī)排序問(wèn)題，利用SPT規(guī)則，按工件加工時(shí)間長(zhǎng)短，從短到長(zhǎng)順序排列，可使平均流程時(shí)間最小。這種方法又稱(chēng)“最短加工時(shí)間規(guī)則”。應(yīng)用SPT規(guī)則，可減少加工其它零件時(shí)它們的等待時(shí)間的和。得到的最優(yōu)總時(shí)間為171.9h，加工次序?yàn)椋篔-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第一問(wèn)的第（2）小問(wèn)，要求規(guī)定的完工時(shí)間內(nèi)，選擇完成工件，使獲得的價(jià)值量最大。很容易可以得到，最優(yōu)解的加工次序必然可以通過(guò)調(diào)換得到工件的完工時(shí)間先后的順序一致。從而建立一個(gè)0—1規(guī)劃模型，求得最優(yōu)解MAXU=117，選擇的工件和加工次序?yàn)椋篔-J-J-J-J-J-J-J-J-J9 1 12 3 7 10 6 4 11 8第二，三問(wèn)中要求工件的加工順序使得加工工件的總時(shí)間最短。加工工件的總時(shí)間等于每個(gè)工件的加工時(shí)間與加工其他工件時(shí)它的等待時(shí)間的和。而問(wèn)題中的工件的加工時(shí)間是一定的，因此問(wèn)題可以轉(zhuǎn)化為求等待時(shí)間的最小。建立等待時(shí)間的目標(biāo)函數(shù)，把工件按在第一臺(tái)機(jī)器的加工時(shí)間的升序進(jìn)行一個(gè)重新排列，得到的新序列，通過(guò)局部的交換工件的次序，再比較等待時(shí)間，若時(shí)間段則繼續(xù)進(jìn)行迭代，否則繼續(xù)交換工件的加工次序，直到所有的工件的順序交換完為止。這樣可以得到第二問(wèn)的總加工時(shí)間的最優(yōu)值為：225.6h。工件加工的總周期為：35h。加工次序?yàn)椋篔-J-J-J-J-J-J-J-J-J-J-J6 2 7 3 10 5 1 4 9 8 11 12第三問(wèn)的總加工時(shí)間的最優(yōu)值為：242.5h。工件加工的總周期為：35.7h。加工次序?yàn)椋簀-j-j-j-j-j-j-j-j-j-j-j。3 6 2 7 10 5 1 8 11 9 4 12計(jì)劃排序問(wèn)題中的車(chē)間作業(yè)問(wèn)題，研究n個(gè)工件在m臺(tái)機(jī)器上有序的加工問(wèn)題，每個(gè)工件都有完工的日期（DD，Duedate），加工的時(shí)間（PT，Processingtime）和工件的價(jià)值（VAL，Valueifjobisselected）.車(chē)間作業(yè)計(jì)劃研究一個(gè)工廠生產(chǎn)工序的計(jì)劃和安排，需要計(jì)劃與合理安排各個(gè)工件在這些機(jī)器上加工的先后次序，即擬訂加工工序，通過(guò)各個(gè)工件在各種機(jī)器上加工次序的合理安排，使得完成這批工件加工任務(wù)所需的總時(shí)間最省（注：總時(shí)間即為各個(gè)零件的加工時(shí)間和加工其他零件時(shí)它們等待時(shí)間之和）或要求整個(gè)選擇加工的工件價(jià)值最大。有一個(gè)工廠現(xiàn)在有12種工件（編號(hào)為工件1，工件2，…，工件12）需要在車(chē)床，鉆床，銑床幾種不同的設(shè)備上加工。考慮下面的工件加工的排序問(wèn)題：（一）這12種工件都要求在車(chē)床上加工，車(chē)床一次只能加工一種工件，這12種工件加工所需時(shí)間，每個(gè)工件的完工時(shí)間和每個(gè)工件的價(jià)值如表（1）所示：1） 不考慮工件的完工時(shí)間和工件的價(jià)值，建立數(shù)學(xué)模型，為該工廠安排工件加工的次序，使得完成這批工件加工任務(wù)所需的總時(shí)間最省。2） 由于工件必須在它們要求的時(shí)間內(nèi)完工，按照表（1）的數(shù)據(jù)，建立數(shù)學(xué)模型，為該工廠安排選擇加工工件的種類(lèi)及加工的次序，使得整個(gè)選擇加工的工件價(jià)值最大。（二）如果這12種工件都要求先在車(chē)床上加工，然后再在鉆床上加工（即工件在鉆床加工之前必須先在車(chē)床上加工過(guò)），每種機(jī)器一次只能加工一種工件，這12種工件加工所需時(shí)間如表（2）所示：建立數(shù)學(xué)模型，為該工廠安排工件加工的次序，使得完成這批工件加工任務(wù)所需的總時(shí)間最省。（三）如果這12種工件都要求先在車(chē)床上加工，然后再在鉆床上加工，最后再在銑床上加工，每種機(jī)器一次只能加工一種工件，這12種工件加工所需時(shí)間如表（三）所示：建立數(shù)學(xué)模型，為該工廠安排工件加工的次序，使得完成這批工件加工任務(wù)所需的總時(shí)間最省。1、 是在工作過(guò)程中是不會(huì)出現(xiàn)故障的，且第一個(gè)機(jī)器為連續(xù)作業(yè)安排，無(wú)需等待時(shí)間，故閑置時(shí)間為零；2、 作業(yè)系列已知，處理過(guò)程開(kāi)始后不再有新作業(yè)，作業(yè)不會(huì)被撤消，不存在加工過(guò)程的中斷，如機(jī)器故障、意外事故等；3、 工件在每一臺(tái)機(jī)器上的加工次序是不變的，即在第一臺(tái)機(jī)器上加工的第i個(gè)工件排在第j個(gè)工件前，則在第二臺(tái)機(jī)器上加工，第i個(gè)工件也排在第j個(gè)工件前。4、 對(duì)加工任務(wù)所需總時(shí)間的理解有兩種：①總時(shí)間即為各個(gè)零件的加工時(shí)間和加工其他零件時(shí)它們等待時(shí)間之和；②從第一個(gè)工件加工開(kāi)始算起到最后一個(gè)工件加工完成所用的時(shí)間。這里對(duì)問(wèn)題的求解都采用第一種理解。符號(hào)說(shuō)明P——是一個(gè)mxn矩陣，其元素pj表示工件J?在機(jī)器吃上加工的時(shí)間；pj——表示工件，?在機(jī)器吃上加工的時(shí)間；c 工件的數(shù)量t^——工件i完工時(shí)間L^——最遲加工時(shí)間，表示工件i的完工時(shí)間減去工件i的加工時(shí)間MAXU 最大工件價(jià)值量x=1 表示第i個(gè)工件被選上x(chóng)^=0——表示第i個(gè)工件沒(méi)有被選上v?——表示加工工件j的價(jià)值量Q——表示按完工時(shí)間先后排列后工件k的加工時(shí)間T——工件的總加工時(shí)間q?——工件的一個(gè)重新排序后工件J在機(jī)器心/上加工的間Tp——工件的加工時(shí)間之和T——工件的等待時(shí)間之和g——第i臺(tái)機(jī)器在加工第j個(gè)工件時(shí)的機(jī)器等待時(shí)間w——第i個(gè)工件的等待時(shí)間i問(wèn)題一：N個(gè)工件在一臺(tái)設(shè)備上的加工的作業(yè)排序。單一設(shè)備（單工序）排序是作業(yè)的排序最簡(jiǎn)單,最基本的問(wèn)題。顯然，當(dāng)N個(gè)工件在一臺(tái)設(shè)備上進(jìn)行加工時(shí)，可能有N！種排序方案。但是，不管是哪種方案，N個(gè)工件的最大流程時(shí)間是固定值，即與工件的加工先后排序無(wú)關(guān)。所以，單一設(shè)備的優(yōu)化排序評(píng)價(jià)標(biāo)準(zhǔn)，通常是平均流程時(shí)間最小，最大拖期量最小或者為零。⑴單一機(jī)床的零件加工排序問(wèn)題可按以下規(guī)則進(jìn)行。SPT規(guī)則按工件加工時(shí)間長(zhǎng)短，從短到長(zhǎng)順序排列，可使平均流程時(shí)間最小。這種方法又稱(chēng)“最短加工時(shí)間規(guī)則”。應(yīng)用SPT規(guī)則，可減少在制品占用量，節(jié)省流動(dòng)資金。由于未考慮交貨期，有可能產(chǎn)生交貨延遲現(xiàn)象。同時(shí)也可以考慮建立目標(biāo)函數(shù)，MinC=史kx七其中七為J*k=1的一個(gè)排列。(2)由于工件都有各自的完工時(shí)間限制，和不同的加工時(shí)間，顯然，主要的約束條件是完工時(shí)間。工件的加工順序是于完工時(shí)間的排列順序一致。若不一致我們可以調(diào)換其中不一致的工件加工順序。TOC\o"1-5"\h\z在j,j都能在規(guī)定的完工時(shí)間內(nèi)完成時(shí)，假如工件j的完工時(shí)間ii+1 i為t,j的完工時(shí)間為t,j排在j之前且t>t,那么此時(shí)調(diào)換ii+1 i+1i i+1 ii+1j,j的順序，將不會(huì)造成j無(wú)法在規(guī)定的時(shí)間完成。因?yàn)橛袟l件ii+1 it>t+1保證。因此，可以肯定工件的加工順序于完工時(shí)間的排列順序一致。這只是充分條件，不是必要條件。引進(jìn)最遲加工時(shí)間L=t—p所以我們對(duì)數(shù)據(jù)做了一個(gè)按完工時(shí)間先后的重新排列的處理并對(duì)其重新編號(hào)，得到下表：新序號(hào)工件加工時(shí)間(h)完工時(shí)間(h)工件價(jià)值最遲加工時(shí)間191.7775.3223.27.544.3312.8986.2452.71077.35124.711186.3631.2151613.8772.5171714.58102.5181215.5960.9222021.110442331911113.625521.41283.3331129.7模型的建立：引進(jìn)12個(gè)0-1變量，尤(i=1,2,???，12),x=1表示第i個(gè)工件被選上,x=0表示第i個(gè)工件沒(méi)有被選上，建立目標(biāo)函數(shù):MAXU=Z七Xx,i=1u為加工工件/.的價(jià)值量。約束條件是對(duì)工件/加工的開(kāi)始時(shí)間必須小于最遲開(kāi)工時(shí)間，而工件的開(kāi)始加工時(shí)間等于加工工件七到j(luò)所用的時(shí)間，對(duì)于工件j的開(kāi)始加工時(shí)間應(yīng)該等于如Qxx，所i-1 i kkk=1以可以得到12個(gè)約束條件：s.t.(EQXx)Xx<L(i=1,2,???，12)。kkiik=1這樣就建立了一個(gè)0-1規(guī)劃問(wèn)題.該題目所求的總時(shí)間即為各個(gè)零件的加工時(shí)間和加工其他零件時(shí)它們等待時(shí)間之和，由于對(duì)每一個(gè)工件的加工都必須經(jīng)過(guò)2臺(tái)機(jī)器的加工，即他們的加工時(shí)間為：T=EE。p「。Pj=1i=1j所以對(duì)于任一種工件的加工次序，他們的加工時(shí)間總和是不變的。該題是求加工次序使得加工工件的總時(shí)間最小，即求

min:T=Tp+「，而氣是一定的，因此問(wèn)題等價(jià)于求工件的等待時(shí)間\最小。分析任一種加工次序的等待時(shí)間如下：第一個(gè)工件的等待時(shí)間為0，因?yàn)樵摴ぜ牡谝慌_(tái)機(jī)器加工完立刻進(jìn)入第二臺(tái)機(jī)器加工，直到該工件加工完成。所以有：?jiǎn)?g21=0第二個(gè)工件的等待時(shí)間為第一個(gè)工件在第一臺(tái)機(jī)器的加工時(shí)間，加上工件在第一臺(tái)機(jī)器加工完成后在第二臺(tái)機(jī)器的加工時(shí)間減去第二個(gè)工件在第一臺(tái)機(jī)器的時(shí)間于0的最大值，即：W=q+Max{0,q一q+g}2 11 12 21 11如果q12一q21<0則第二臺(tái)機(jī)器存在機(jī)器的等待時(shí)間:21-1X(q12-q21+g11)21否則即第三個(gè)工件的等待時(shí)間為: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此時(shí)的機(jī)器等待時(shí)間為：g=max{0,—1x(q+q—q—q+g+g)}23 12 22 21 31 21 22

第四個(gè)工件的等待時(shí)間為: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機(jī)器等待時(shí)間為：g=Max{0,—1x(q+q+q—q—q—q+g+g+g)}

24 12 22 32 21 31 41 21 22 23第五個(gè)工件的等待時(shí)間為：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機(jī)器等待時(shí)間為：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個(gè)工件的等待時(shí)間為:W=2q+Max{0劃q—￡q-Eg}i k1 k2 k1 2kk=1 k=1 k=2 k=1g,.2i此時(shí)的機(jī)器等待時(shí)間為：g2=Max{0,-1x（Eqk廣工九一歸g次）}k=1 k=2 k=1g,.2i從而建立目標(biāo)函數(shù)：min:從而建立目標(biāo)函數(shù)：min:T=T+T=EEp.+Ewk.j=1i=1 k=1相對(duì)第二問(wèn)，該問(wèn)只是增加了機(jī)器的臺(tái)數(shù)，其他條件不變，因此這里的機(jī)器等待時(shí)間有兩個(gè)，即第二臺(tái)機(jī)器的等待時(shí)間和第三臺(tái)機(jī)器的等待時(shí)間。分析任一種加工次序的等待時(shí)間如下：第一個(gè)工件的等待時(shí)間為0，因?yàn)樵摴ぜ牡谝慌_(tái)機(jī)器加工完立刻進(jìn)入第二臺(tái)機(jī)器加工，再到第三臺(tái)機(jī)器，直到該工件加工完成。所以有：W]=g21=g31=0第二個(gè)工件的等待時(shí)間為T(mén)OC\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此時(shí)第二臺(tái)機(jī)器的等待時(shí)間為：g=Max{0,-1x(q—q+g)}22 12 21 21第三臺(tái)機(jī)器的等待時(shí)間為：g=Max{0,-1x(q—q+g—g)}32 13 22 31 21第三個(gè)工件的等待時(shí)間為：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此時(shí)第二臺(tái)機(jī)器的等待時(shí)間為：g=Max{0,—1x(q+q—q—q+g+g)}

23 12 22 21 31 21 22第三臺(tái)機(jī)器的等待時(shí)間為：g=Max{0,—1x(q+q—q—q+g+g—g—g)}

33 13 23 22 32 31 32 21 22第四個(gè)工件的等待時(shí)間為：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此時(shí)第二臺(tái)機(jī)器的等待時(shí)間為：g=Max{0,—1x(q+q+q—q—q—q+g+g+g)}

24 12 22 32 21 31 41 21 22 23第三臺(tái)機(jī)器的等待時(shí)間為：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個(gè)工件的等待時(shí)間為:,歸qk3習(xí)矣疽歸g疽如g2k}k=1 k=2 k=1 ,歸qk3習(xí)矣疽歸g疽如g2k}k=1 k=2 k=1 k=1i k1 k2 k1 2kk=1 k=1 k=2 k=1此時(shí)第二臺(tái)機(jī)器的等待時(shí)間為:g=Max{0,-1x(Eqk=1-Eqk1+Eg2k)}k=2 k=1第三臺(tái)機(jī)器的等待時(shí)間為: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同理建立目標(biāo)函數(shù)：min:T—T+T=E￡p..+Ewj=1i=1 k=1模型求解問(wèn)題一:工件加工時(shí)間(h)完工時(shí)間(h)工件價(jià)值12.89823.27.5431.215164423352.710760.9222072.5171783.3331191.777102.51812113.6255124.71118解：（1）12種工件的排序分析過(guò)程如下:加工周期lax=''=33.1，這是一定的，與工件的加工順序無(wú)關(guān)。按照上述的SPT規(guī)則，加工順序?yàn)镴—J—J—J—J—J—J—J—J—J—J—J或?yàn)? 3 9 7 10 5 1 2 8 11 4 12 次八J—J—J—J—J—J—J—J—J—J—J—J 禾呈日寸問(wèn)3 9 10 7 5 1 2 8 11 4 12，平均流程時(shí)間最小。完成這批工件加工任務(wù)所需的總時(shí)間最小為：Cmin=171.9。（2）為了利用數(shù)學(xué)軟件LINGO求解，我們簡(jiǎn)化約束條件的形式:(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。對(duì)照8 9 10 11 12重新排列的表格可以得到不選擇加工的工件為：J?和J5，即加工的次序?yàn)椋篔-J-J-J-J-J-J-J-J-J

9 1 12 3 7 10 6 4 11 8所獲得的最大價(jià)值量為117。

問(wèn)題二，二:對(duì)二三問(wèn)，我們采取相同的方法解決，首先對(duì)Tw=lLWk進(jìn)行分k=1析，問(wèn)題二中：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問(wèn)題二中: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(shù)=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為了使得總等待時(shí)間最小，我們不妨把等待時(shí)間分為兩部分:即:E(12—i)xq和區(qū)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很顯然，后面部分依賴(lài)于工件的排列，而前面E(12T)xq、則可i=1以通過(guò)第一問(wèn)的結(jié)論得到最小值，即將工件在第一臺(tái)機(jī)器的加工時(shí)間按升序排列，就可以使得E(12-i)xq〃最小。加工次序如下:i=1

工件車(chē)床加工時(shí)間(h)鉆床加工時(shí)間(h)60.94.531.21.891.74.572.51.7102.52.552.7312.8423.21.383.32.5113.63.8442.2124.71.9工件車(chē)床加工時(shí)間(h)鉆床加工時(shí)間(h)銑床加工時(shí)間(h)60.94.591.74.51

52.731.812.84323.21.3442.21.3然后進(jìn)行工件順序的交換，進(jìn)程如下：第一步，令i=1,j=1第二步，計(jì)算此時(shí)T的值0第三步，交換第i個(gè)位置和第i+j個(gè)位置上的工件，計(jì)算T的值，若T>T0進(jìn)入第四步，否則T=T0，進(jìn)入第一步第四步，交換回第i個(gè)位置和第i+j個(gè)位置上的工件，i++,如果i=13-j,則i=1,j++,進(jìn)入第五步第五步，如果j=12,結(jié)束，否則回到第三步第二問(wèn)的總加工時(shí)間的最優(yōu)值為：225.6h。工件加工的總周期為：35h。加工次序?yàn)椋篔-J-J-J-J-J-J-J-J-J-J-J6 2 7 3 10 5 1 4 9 8 11 12第三問(wèn)的總加工時(shí)間的最優(yōu)值為：242.5h。