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

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

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

min:T=Tp+「，而氣是一定的，因此問題等價于求工件的等待時間\最小。分析任一種加工次序的等待時間如下：第一個工件的等待時間為0，因?yàn)樵摴ぜ牡谝慌_機(jī)器加工完立刻進(jìn)入第二臺機(jī)器加工，直到該工件加工完成。所以有：嗎=g21=0第二個工件的等待時間為第一個工件在第一臺機(jī)器的加工時間，加上工件在第一臺機(jī)器加工完成后在第二臺機(jī)器的加工時間減去第二個工件在第一臺機(jī)器的時間于0的最大值，即：W=q+Max{0,q一q+g}2 11 12 21 11如果q12一q21<0則第二臺機(jī)器存在機(jī)器的等待時間: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此時的機(jī)器等待時間為：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機(jī)器等待時間為：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機(jī)器等待時間為：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此時的機(jī)器等待時間為：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相對第二問，該問只是增加了機(jī)器的臺數(shù)，其他條件不變，因此這里的機(jī)器等待時間有兩個，即第二臺機(jī)器的等待時間和第三臺機(jī)器的等待時間。分析任一種加工次序的等待時間如下：第一個工件的等待時間為0，因?yàn)樵摴ぜ牡谝慌_機(jī)器加工完立刻進(jìn)入第二臺機(jī)器加工，再到第三臺機(jī)器，直到該工件加工完成。所以有：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此時第二臺機(jī)器的等待時間為：g=Max{0,-1x(q—q+g)}22 12 21 21第三臺機(jī)器的等待時間為：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此時第二臺機(jī)器的等待時間為：g=Max{0,—1x(q+q—q—q+g+g)}

23 12 22 21 31 21 22第三臺機(jī)器的等待時間為：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此時第二臺機(jī)器的等待時間為：g=Max{0,—1x(q+q+q—q—q—q+g+g+g)}

24 12 22 32 21 31 41 21 22 23第三臺機(jī)器的等待時間為：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習(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此時第二臺機(jī)器的等待時間為:g=Max{0,-1x(Eqk=1-Eqk1+Eg2k)}k=2 k=1第三臺機(jī)器的等待時間為: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模型求解問題一:工件加工時間(h)完工時間(h)工件價值12.89823.27.5431.215164423352.710760.9222072.5171783.3331191.777102.51812113.6255124.71118解：（1）12種工件的排序分析過程如下:加工周期lax=''=33.1，這是一定的，與工件的加工順序無關(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 禾呈日寸問3 9 10 7 5 1 2 8 11 4 12，平均流程時間最小。完成這批工件加工任務(wù)所需的總時間最小為：Cmin=171.9。（2）為了利用數(shù)學(xué)軟件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，即加工的次序?yàn)椋篔-J-J-J-J-J-J-J-J-J

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

問題二，二:對二三問，我們采取相同的方法解決，首先對Tw=lLWk進(jìn)行分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(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為了使得總等待時間最小，我們不妨把等待時間分為兩部分:即: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很顯然，后面部分依賴于工件的排列，而前面E(12T)xq、則可i=1以通過第一問的結(jié)論得到最小值，即將工件在第一臺機(jī)器的加工時間按升序排列，就可以使得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然后進(jìn)行工件順序的交換，進(jìn)程如下：第一步，令i=1,j=1第二步，計算此時T的值0第三步，交換第i個位置和第i+j個位置上的工件，計算T的值，若T>T0進(jìn)入第四步，否則T=T0，進(jìn)入第一步第四步，交換回第i個位置和第i+j個位置上的工件，i++,如果i=13-j,則i=1,j++,進(jìn)入第五步第五步，如果j=12,結(jié)束，否則回到第三步第二問的總加工時間的最優(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第三問的總加工時間的最優(yōu)值為：242.5h。