多目標(biāo)柔性作業(yè)車(chē)間調(diào)度問(wèn)題研究多目標(biāo)柔性作業(yè)車(chē)間調(diào)度問(wèn)題綜合考慮了實(shí)際生產(chǎn)中的多個(gè)性能指標(biāo)*比如交貨期、單個(gè)機(jī)器最人負(fù)荷、拖延時(shí)間、機(jī)器總負(fù)荷等，比対單一目標(biāo)進(jìn)行優(yōu)化更能滿足實(shí)際生產(chǎn)的需要。多目標(biāo)柔性作業(yè)車(chē)間調(diào)度問(wèn)題研究應(yīng)用于實(shí)際生產(chǎn)，提高了企業(yè)生產(chǎn)的靈活性，抓快了對(duì)市場(chǎng)變化的響應(yīng)速度,捉高了七產(chǎn)能丿J,縮短了供筋時(shí)I譏主產(chǎn)屮不同的牛產(chǎn)任務(wù)無(wú)石改裝機(jī)器*僅在牛產(chǎn)調(diào)度屮做一兆變動(dòng)即可進(jìn)行牛產(chǎn);在牛一產(chǎn)中某臺(tái)機(jī)器岀現(xiàn)故障后，可以通過(guò)生產(chǎn)調(diào)度快速的找到其他設(shè)備替代，生產(chǎn)不受單臺(tái)機(jī)器的影響：可以對(duì)復(fù)雜零件的各種要求進(jìn)行綜合加工，無(wú)需按照傳統(tǒng)的單一匚序的加T-方達(dá)；討以減少單臺(tái)機(jī)器負(fù)荷率過(guò)低的問(wèn)題,提高了機(jī)器的使川率,從而人人降低了企業(yè)的牛產(chǎn)成本」早在1772年Franklin^1就對(duì)多目標(biāo)矛盾提出過(guò)探究，也是第一個(gè)提出怎樣對(duì)多r［標(biāo)進(jìn)行優(yōu)化.Zfu乂在19箝年法國(guó)經(jīng)濟(jì)學(xué)家Paretop71±政治經(jīng)濟(jì)學(xué)的去面丄也同樣提出過(guò)多目標(biāo)優(yōu)化問(wèn)題的探究?，F(xiàn)在多目標(biāo)優(yōu)化已經(jīng)成為數(shù)學(xué)上的一個(gè)分支進(jìn)行系統(tǒng)的研究,在理論上取得了報(bào)多偉人的成果’在很多領(lǐng)域都冇應(yīng)-川。一般多目標(biāo)問(wèn)題可以描述為有￡個(gè)目標(biāo)函數(shù)，同時(shí)決策變量工必須滿足*個(gè)約束條件，具體可以表述為：約束條杵分為兩類(lèi)，不等式約束和等式約束：輕=P/=L2n設(shè)有占個(gè)憂化目標(biāo)，目標(biāo)函數(shù)表示為：卩⑴二(川門(mén)/⑴—.<(-0H.J)r［標(biāo)函數(shù)屮仃的子II標(biāo)是求極人值,仃的口標(biāo)函數(shù)是求極小111,但是f(X)的極小值丿廠廣(X)極大值在—心取繪優(yōu)值*所以可以轉(zhuǎn)化為同-啖形式的口標(biāo)函數(shù)°與多目標(biāo)憂化的主要幾個(gè)相關(guān)定義【徊有：可行解集若工滿足H標(biāo)函數(shù)的約束條杵,則稱(chēng)工為H標(biāo)函數(shù)的I叮it解,所仃聽(tīng)亍解的集合為可行解集X,其屮Pareto最優(yōu)解集在可行解集屮，對(duì)于給定的兩個(gè)可行解T比*有效，則可廳解T為Pareto最優(yōu)解，目標(biāo)函數(shù)有多個(gè)可行解，Pareto最優(yōu)解也有多個(gè)解，組成的集合為Pareto最優(yōu)解集，汜為｛"｝。Pareto前沿Pareto最優(yōu)解集XT屮的解對(duì)應(yīng)的目標(biāo)函數(shù)值組成的集合比」，稱(chēng)為Pareto前沿。3.2生產(chǎn)調(diào)度問(wèn)題數(shù)學(xué)建模實(shí)際的制造生產(chǎn)過(guò)程需要同時(shí)考慮多個(gè)性能指標(biāo)，生產(chǎn)調(diào)度問(wèn)題通常需要考慮加工成本、交貨期、設(shè)備負(fù)荷最等多個(gè)性能指標(biāo)。不同丁?單目標(biāo)作業(yè)車(chē)間調(diào)度，多目標(biāo)車(chē)間凋度和不同的目標(biāo)范吊I內(nèi)的不同取值和駅綱存在沖突，一個(gè)目標(biāo)性能的改善可能惡化其他目標(biāo)性能。3.2.1柔性作業(yè)車(chē)間調(diào)度問(wèn)題的基本描述柔性作業(yè)車(chē)間有路徑和排序兩個(gè)子問(wèn)題㈤】，為工序選擇機(jī)器路徑，對(duì)每臺(tái)機(jī)器加工的工序進(jìn)行排序，在生產(chǎn)制造過(guò)程屮柔性作業(yè)車(chē)間調(diào)度問(wèn)題一般可描述如卜：有/個(gè)工件｛外▲，???&｝,可用丁?工件加工的機(jī)器有〃臺(tái)仏02，??〃"｝,每個(gè)工件有〃道工序，工件有多條工藝路線可以選擇，每道工序可以在一臺(tái)或者多臺(tái)機(jī)器上加工，每臺(tái)機(jī)器是不相同的，所以工序的加工時(shí)間隨加工時(shí)選擇的機(jī)器的不同而不同。生產(chǎn)調(diào)度的目標(biāo)是為每個(gè)工件選擇合適的加工工藝路線，工件的每道工序選擇最合適的機(jī)器，確定每個(gè)工件的每道工序的最佳加工順序，從而使生產(chǎn)過(guò)程屮的某些性能指標(biāo)達(dá)到最優(yōu)。目前，生產(chǎn)調(diào)度屮應(yīng)用最廣的一個(gè)調(diào)度性能評(píng)價(jià)指標(biāo)是最人完工時(shí)間（人席）最小。此外，在加工制造過(guò)程受許多約束條件的限制，需要滿足卜?面的假設(shè)條件。（1）某一IN刻在冋一臺(tái)機(jī)器上只能加工一個(gè)工件的一道工序；（2）某一時(shí)刻同一個(gè)工件的相同工序只能在一臺(tái)機(jī)器上加工；（3）工件的每道工序的加工都是連續(xù)的，加工過(guò)程不能被中斷；（4）工件與工件Z間沒(méi)有先后關(guān)系；（5）所有工件的優(yōu)先級(jí)相同；（6）每個(gè)工件的每道工序都有可能在零時(shí)刻被加工；（7）所有工件加工完都是合格品，不存在次品。3.2.2多目標(biāo)柔性作業(yè)車(chē)間調(diào)度問(wèn)題描述和模型柔性作業(yè)車(chē)間調(diào)度問(wèn)題是一種組合的優(yōu)化問(wèn)題，為了適應(yīng)市場(chǎng)的多變性，需要有柔性的調(diào)度系統(tǒng)，生產(chǎn)過(guò)程屮為工件的每道工序選定加工機(jī)器，并對(duì)指定機(jī)器上加工的工序排序，多目標(biāo)柔性作業(yè)車(chē)|iU調(diào)度問(wèn)題是指同時(shí)優(yōu)化生產(chǎn)過(guò)程屮的多個(gè)評(píng)價(jià)指標(biāo)。文章對(duì)工件的完工時(shí)間最小、機(jī)器負(fù)荷最小以及總的機(jī)器負(fù)荷最小為優(yōu)化目標(biāo)對(duì)問(wèn)題進(jìn)行研究。多目標(biāo)柔性作業(yè)車(chē)間調(diào)度問(wèn)題在很多關(guān)多目標(biāo)調(diào)度的文獻(xiàn)里都何描述，一般可以描述如卜?：有〃個(gè)工序加工路線不同的工件，可以選擇在加臺(tái)機(jī)器上加工,機(jī)器的加工功能不同，相同的工序可以在同一臺(tái)機(jī)器上加工，有的機(jī)器具有多種功能，可以加工兩道或者多道工序，工序可以選擇加工的機(jī)器也是柔性的，相同工件的工序可以選擇加工的機(jī)器有多臺(tái)，一臺(tái)機(jī)器在任意相同的時(shí)間里只能有一個(gè)工件在上面加工，一個(gè)工件在任意相同的時(shí)間里只能選擇一臺(tái)機(jī)器加工。對(duì)丁?多目標(biāo)柔性作業(yè)問(wèn)題需要從兩個(gè)角度來(lái)分析問(wèn)題：（1）給每道工序選擇最合適的加工機(jī)器，就是考慮機(jī)器如何達(dá)到最優(yōu)分配；（2）給每臺(tái)機(jī)器上的加工工序選擇最優(yōu)加工時(shí)間，同時(shí)將目標(biāo)函數(shù)的多個(gè)性能函數(shù)考慮進(jìn)去。在加工過(guò)程受到一約束條件的制約。定義文章涉及的符號(hào)以及變最的含義：〃:需要加工的工件數(shù)量；加：工件的加丁機(jī)器總數(shù)量；譏:機(jī)器序號(hào),「，"1，2,3,…,”；j，k:工序序號(hào),丿1,2,3,...,〃；4:工件,所包含的工序數(shù)；Qijk:在機(jī)器&上加工待加工工件：的第丿道工序需要加工的時(shí)間；%:在機(jī)器'上加工待加工工件°的第丿道工序起始加工時(shí)fHj：Eijk:在機(jī)器k上加工待加工工件'的第丿道工序完工時(shí)間；BPk:所有工件在機(jī)器2上的完工時(shí)間；%：工件'在工序丿上的結(jié)束加工時(shí)間；人曲：工件總完工時(shí)間；第丿個(gè)工件的完工時(shí)間；1,工件，的第丿道工序和工件e的第g道工序RljeKk=在同一機(jī)器R上執(zhí)行，若工序/先于工序g[o,其他3.3建立多目標(biāo)柔性作業(yè)車(chē)間調(diào)度的模型0工件i未被安排在第w個(gè)位置加工X.?=*”1「件i被安排在第W個(gè)位置加丁y_JO工件味在工序j上的第k臺(tái)機(jī)器上加工ijk=}1工件i在工序j上的第k臺(tái)機(jī)器上加工_]0工件i未在工序j上的第k臺(tái)機(jī)器上第1順位加工乙閔科]工件：在工序j上的第k臺(tái)機(jī)器上第1順位加工多目標(biāo)柔性作業(yè)車(chē)間調(diào)度評(píng)價(jià)指標(biāo)一般有交貨期和機(jī)器使用率。論文同時(shí)優(yōu)化生產(chǎn)過(guò)程屮較常用的三個(gè)評(píng)價(jià)指標(biāo)：最人完工時(shí)間、最人機(jī)器總負(fù)荷和單臺(tái)機(jī)器最人負(fù)荷。（1）最人完工時(shí)間最小人際，最人完工時(shí)間是指所有工件都加丁完所需要的時(shí)間，直接關(guān)系到產(chǎn)品能否在交貨期內(nèi)按時(shí)交貨，最人完工時(shí)間越小說(shuō)明調(diào)度方案越優(yōu)。/=min（max（d,））（3.2）\<j<n（2）單臺(tái)機(jī)器最人負(fù)荷最小BPk,生產(chǎn)過(guò)程中選擇的調(diào)度方案不同，每臺(tái)機(jī)器的負(fù)荷就不同，在選取調(diào)度方案屮要盡駅滿足機(jī)器負(fù)荷的均衡。nkjfi=min（max工工Oijk切）（3.3）7=11=1（3）最人機(jī)器總負(fù)荷聶小代”，同一工件的相同工序選擇的機(jī)器不同，加工時(shí)間不同，在滿足產(chǎn)品交貨期，即最人完工時(shí)間最小，機(jī)器使用均衡的條件卜?，同IM也需要優(yōu)化機(jī)器的總負(fù)荷。(3.4)fi=min(max工工工Qiikxijk)(3.4)/=!j-\h=\優(yōu)化目標(biāo)函數(shù)時(shí)也有一定約束條件：（1）每個(gè)排序位置只能分配一個(gè)工件;n工X=1w=1,2,ni=liw每個(gè)工件只能有一個(gè)排序位置；=1i=l,2,...,nW=1⑶任意一個(gè)工件在任何一個(gè)階段只能由一臺(tái)機(jī)器加工;N,YZjk=11―1,2,...,n；j—1,2,...,itik=l⑷加工階段至少為1：m>l(5)至少有一個(gè)階段的機(jī)器數(shù)目人于1臺(tái)；m工7Vj>m,N->1j=1,2,...,mj=>⑹工件在某臺(tái)機(jī)器上的加工順序唯一；k=l1=1(7)工件d在階段,/+1±的開(kāi)始加工時(shí)間不應(yīng)早丁?在階段j上的結(jié)束加工時(shí)間；C.<Si=1,2,...,n；j=1,2,...,m；r=j4-13.4基于”SGA-II算法的多目標(biāo)柔性作業(yè)車(chē)間調(diào)度3.4.1NSGA-II算法非劣前沿分級(jí)遺傳算法"5(NondominatedSortingGeneticAlgorithmNSGA)是基J：Goldberg的非支配排序的思想設(shè)計(jì)的，通過(guò)共享非支配解的虛擬適應(yīng)度，從而維持了種群在進(jìn)化過(guò)程的多樣性。但是NSGA算法的計(jì)算要求多，復(fù)雜程度高，并且在計(jì)算前還必須對(duì)參數(shù)共享。2002年Deb刖等改進(jìn)了NSGA算法的不足，提出了NSGA-II算法，該算法被很多學(xué)者引用，是目前最優(yōu)秀的多目標(biāo)算法Z—。與NSGA相比，NSGA?II具有卜?面的優(yōu)勢(shì)：①為了降低算法計(jì)算過(guò)程屮的復(fù)雜度，使用了一種新的排序方法，基J'-分級(jí)的快速非支配解的排序；②采用的擁擠距離比較算子可以快速的標(biāo)定非支配，排序后的非支配解的同級(jí)屮不同元素的適應(yīng)度值，并使Pareto-前端個(gè)體可以均勻的分布；③引入了精英保留機(jī)制，父代與其繁殖產(chǎn)生的后代通過(guò)共同競(jìng)爭(zhēng),選擇出優(yōu)良個(gè)體來(lái)繁殖卜?一代，維持了種群的優(yōu)良性。3.4.2NSGA-II算法基本流程N(yùn)SGA-II算法的基本操作流程為：首先初始化種群，隨機(jī)產(chǎn)生一個(gè)規(guī)模為N的種群，Pareto排序選擇非支配解集Z,通過(guò)種群的遺傳進(jìn)化產(chǎn)生種群第一代子代；然后將產(chǎn)生的后代與父代種群組成新的種群，標(biāo)定快速非支配排序后同級(jí)中的適應(yīng)度值，采用擁擠距離比較算子選取遺傳進(jìn)化中優(yōu)良的父代個(gè)體;最后通過(guò)遺傳進(jìn)化產(chǎn)生新的子代種群，反復(fù)循環(huán)，直到得到滿足要求的解。算法流程圖陀】如圖3-1所不:初始種群N,遺傳進(jìn)化第一代rPareto排序組成的非支配集z—▼i=l111?口召放入#代種群|廠子代與父代結(jié)〒合成的新的種群Rt,種群規(guī)〔廠子代與父代結(jié)〒合成的新的種群Rt,種群規(guī)〔I模為2NI＜腫.群Pt+i個(gè)圾＞「x7尸Zi+1+.?ZiJ＞1等于N*"遺傳操作（交叉，變異）新的后代種群Qt+i進(jìn)儲(chǔ)弋?dāng)?shù)Gen=Gcn+l遺傳操作（交叉，變異）新的后代種群Qt+i進(jìn)儲(chǔ)弋?dāng)?shù)Gen=Gcn+l圖圖3-1NSGA-II算法的基本流程圖3.4.3算法的設(shè)計(jì)（1）建立初始種群初始種群的建立是遺傳進(jìn)化中的一個(gè)關(guān)鍵步驟，如果初始種群的平均適用度值偏低，初始種群的進(jìn)化速度會(huì)降低，為了收斂得到最優(yōu)解迭代過(guò)程需要很長(zhǎng)時(shí)間，共至無(wú)法收斂到最優(yōu)解；如果選擇較高的平均適應(yīng)度值,算法可以在較短的時(shí)間內(nèi)收斂到問(wèn)題的最優(yōu)解，有效的提高了進(jìn)化的速度。因此，初始種群對(duì)算法求解的速度和質(zhì)最有很人的影響。本文為了建立較好的初始種群，采用的隨機(jī)初始化方法隨機(jī)選擇規(guī)模為N的初始種群。編碼解碼設(shè)計(jì)編碼即通過(guò)對(duì)問(wèn)題的染色體編碼，將具體的調(diào)度方案用一定的代碼表示，車(chē)iiu調(diào)度問(wèn)題常見(jiàn)的編碼依據(jù)方式有:基j'-待工件的編碼，基r工件待加工工序的編碼，基丁?工序先后表的編碼，基丁?工件z間対應(yīng)關(guān)系的編碼，基丁?工件加工優(yōu)先規(guī)則的編碼，基r析取圖的編碼，基丁?工件完工時(shí)間的編碼，基丁?機(jī)器及隨機(jī)鍵編碼,基『?生產(chǎn)中優(yōu)先調(diào)度權(quán)值的編碼等。結(jié)合柔性車(chē)間作業(yè)調(diào)度問(wèn)題的特點(diǎn),米用基J-待加工工序的編碼方式，并用陰層編碼［43］的方式，先確定各道工序的優(yōu)先權(quán)，由于不同工件的工序Z間沒(méi)有約束，而同一個(gè)工件每次只能加工一道工序,有前后約束，第一層編碼為工序的隨機(jī)數(shù)，第二層編碼為各工序確定加工機(jī)器。柔性作業(yè)車(chē)間調(diào)度問(wèn)題解碼是為所有工序選擇一臺(tái)合適的機(jī)器，先把工件排序串轉(zhuǎn)化為有序的工序表，然后依次為有序工序表屮的所有工序安排加工開(kāi)始時(shí)間，工序表中的所有工序都安排完解碼停止。設(shè)計(jì)適應(yīng)度函數(shù)遺傳進(jìn)化過(guò)程屮適應(yīng)度值(①)是評(píng)價(jià)個(gè)體優(yōu)劣程度的標(biāo)準(zhǔn)，適應(yīng)度值越人的個(gè)體繁殖后代的能力就越強(qiáng)，父代的優(yōu)良特性更能得以遺傳。本文建立的多目標(biāo)柔性車(chē)間作業(yè)調(diào)度模型的目標(biāo)函數(shù)為適應(yīng)度函數(shù)，即以最人完工時(shí)間最小，最人負(fù)荷機(jī)器最小和總機(jī)器負(fù)荷最小為目標(biāo)，調(diào)度方案中的工序排序受到機(jī)器負(fù)荷約束的同時(shí)受到工件的約束，調(diào)度目標(biāo)是求人、厶和人三個(gè)目標(biāo)函數(shù)的最小值。遺傳算子的設(shè)計(jì)遺傳算子的設(shè)計(jì)是遺傳算法屮較為關(guān)鍵的一步，每個(gè)染色體對(duì)應(yīng)一個(gè)問(wèn)題的解決方案，執(zhí)行復(fù)制、交叉、變異算子的操作。A復(fù)制從種群中選擇優(yōu)良的個(gè)體進(jìn)行進(jìn)化繁殖，比較種群的個(gè)體的適應(yīng)度，選擇適應(yīng)度高的個(gè)體直接復(fù)制到卜?一代。一般情況卜?，個(gè)體的適應(yīng)度值越人，被選擇直接將染色體復(fù)制到卜?一代的機(jī)會(huì)也就越人，其中選擇概率P為:c=4/￡厲k=\

其中〃是種群規(guī)模數(shù)，①是第，個(gè)染色體的適應(yīng)度值，這樣適應(yīng)度值低r平均值的個(gè)體在選擇過(guò)程中被淘汰了，選取適應(yīng)度高的個(gè)體組成一個(gè)新的群體。B交叉按照給定的交叉概率（'）隨機(jī)選擇兩個(gè)編碼的染色體交叉操作，產(chǎn)生新的基因組合。所有染色體重復(fù)如卜?的迭代過(guò)程：在區(qū)間［°」］內(nèi)取隨機(jī)數(shù)廠；若廠則選擇交叉的染色體數(shù)最為"X'。交叉是將父母的基因在染色體相互交換后隨機(jī)遺傳給卜?一代，在基丁?二序編碼的交叉屮，本文采用兩點(diǎn)交叉法，隨機(jī)選擇兩個(gè)交叉點(diǎn)，將兩點(diǎn)Z間的基因?qū)Q，產(chǎn)生新子代。這個(gè)過(guò)程與自然界的交配過(guò)程類(lèi)似，父代如果將優(yōu)良基因傳給了后代，就能得到更優(yōu)的一代。兩點(diǎn)交義的選擇點(diǎn)（串屮的第3個(gè)和第6個(gè)點(diǎn)基因?qū)Q）100111101011001010011110101100101011101010010110圖3-2交叉算子（兩點(diǎn)交叉）C變異以較小的概率改變?nèi)旧w屮的基因位，進(jìn)化產(chǎn)生新的個(gè)體，保證了群體的多樣性，確定變異概產(chǎn)為化。本文采用基本位變異算子作變異運(yùn)算，遺傳操作屮二進(jìn)制編碼符號(hào)串屮基因位屮的0變?yōu)?,或者1變異為0。（5）染色體的選擇機(jī)制用賭輪法確定種群個(gè)體數(shù)，用精英保留策略保留迭代過(guò)程中的精英個(gè)體。子代通過(guò)精英策略產(chǎn)生的種群與父代的精英種群組合成新的種群°，人小為2N，月非支配排序的方法対新產(chǎn)生的種群°進(jìn)行排序，得到非支配解集川，計(jì)算非支配解集的擁擠度，經(jīng)過(guò)支配排序后得到優(yōu)良的個(gè)體，然后進(jìn)行遺傳操作（選擇、交叉、變異）選擇新的子代種群°呵，循環(huán)迭代。A非劣前沿分層非劣解指該解的各個(gè)目標(biāo)函數(shù)值都是最優(yōu)的解,即Pareto解，Pareto解指在求解多目標(biāo)問(wèn)題時(shí)，rl3F目標(biāo)函數(shù)Z間是相互沖突的，某個(gè)可能是其中一個(gè)目標(biāo)的最優(yōu)解，但是在其他目標(biāo)上較差，任何目標(biāo)函數(shù)的改進(jìn)都可能導(dǎo)致其他目標(biāo)函數(shù)的解的削弱,Pareto解又稱(chēng)非支配解。如下圖，點(diǎn)A,B,C是非支配解,APareto支配解點(diǎn)X,CPareto支配解點(diǎn)Y。▲flXkf2圖3-3Pareto支配解示意圖在解空間里Pareto最優(yōu)解是沖突最小的解，染色體群初始化后根據(jù)適應(yīng)度值的人小進(jìn)行非劣前沿等級(jí)分層，具體操作如卜?：將染色體群。內(nèi)的所有染色體個(gè)體°實(shí)行卜?面操作：I.初始化一個(gè)存放相對(duì)染色體°所有非劣染色體的集合；II?初始化一個(gè)表示相對(duì)染色體。所有非劣染色體的變帚N=°：III?對(duì)比染色體°與。，若°相對(duì)。非劣，則將。添加到集合紜內(nèi)，即島=氏丫｛0」；反乙則增加支配解S即+IV.如沒(méi)有染色體相對(duì)°非劣，則將染色體°」歸到第一級(jí)的非劣前沿層，記°”認(rèn)i,同時(shí)將Q放到第一級(jí)非劣前沿集合,fi,fi"iyQ｝。將群體°內(nèi)的所有染色體按照步驟（1）的方法劃分非劣等級(jí)；初始化非劣前沿層內(nèi)的等級(jí)計(jì)數(shù)器，設(shè)為/“：若非劣前