基于遺傳算法的多資源平衡工序排序優(yōu)化決策

付宗仁

（海軍91832部隊(duì)裝備部，廣西 北海 536000）

生產(chǎn)過(guò)程中工序編排是生產(chǎn)管理中極其重要的一個(gè)環(huán)節(jié)，處理得好與壞，直接影響產(chǎn)品的生產(chǎn)周期及經(jīng)濟(jì)效益，對(duì)此人們已有充分的認(rèn)識(shí)。但工序排序?qū)貼-P完備問(wèn)題，至今尚無(wú)特別簡(jiǎn)便、有效的方法加以解決，人們一般沿襲傳統(tǒng)作法憑經(jīng)驗(yàn)辦事，或用一粗糙的近似算法，效果都不理想。隨著計(jì)算機(jī)在生產(chǎn)過(guò)程中的廣泛應(yīng)用，使用它們解決排序問(wèn)題，已成為一種快捷、有效的途徑。

工序編排有兩類問(wèn)題，一是基于資源約束，通過(guò)合理安排工序?qū)で笞疃痰纳a(chǎn)周期，從而盡快完成任務(wù)；一是在總工期不變即固定工期的情況下，通過(guò)工序編排，使各資源需求數(shù)量盡可能達(dá)到平衡使用，以減少資源儲(chǔ)備或使工程物資供應(yīng)有保障，從而增強(qiáng)實(shí)現(xiàn)計(jì)劃的可能性，并通過(guò)資源平衡，達(dá)到減少資源閑置與浪費(fèi)、降低工程成本的目的。

目前，人們對(duì)上述第一類問(wèn)題研究的較多、較為深入，對(duì)于多資源平衡優(yōu)化的問(wèn)題研究并不多。文獻(xiàn)[1]通過(guò)確定各資源對(duì)平衡效果的相對(duì)貢獻(xiàn)率，分析了時(shí)差對(duì)工序調(diào)整的影響，構(gòu)造了綜合判斷數(shù)量指標(biāo)，比較符合工程施工對(duì)資源量的需求情況，但并沒(méi)有應(yīng)用有效的算法進(jìn)行計(jì)算，難以高效的實(shí)現(xiàn)。文獻(xiàn)[2]應(yīng)用改進(jìn)的混合遺傳算法求解了第一類問(wèn)題。文獻(xiàn)[3]對(duì)活動(dòng)網(wǎng)絡(luò)資源均衡問(wèn)題的建模和算法分別進(jìn)行了討論，提出了資源均衡的遺傳算法。文獻(xiàn)[4]使用聚類分析優(yōu)化遺傳算法對(duì)資源平衡進(jìn)行了研究。同時(shí)較多文獻(xiàn)只是對(duì)簡(jiǎn)單的總工期固定多資源進(jìn)行描述和建模，而且對(duì)于目標(biāo)值及適應(yīng)度函數(shù)的表達(dá)不直接，顯得較為煩瑣。

本文建立了典型的網(wǎng)絡(luò)計(jì)劃多資源平衡工序優(yōu)化的數(shù)學(xué)模型，應(yīng)用MATLAB遺傳算法工具箱函數(shù)及改進(jìn)的遺傳算法對(duì)其進(jìn)行了研究，設(shè)計(jì)了可直接求解出最佳工序編排及其對(duì)應(yīng)的目標(biāo)函數(shù)值的功能函數(shù)，使建模過(guò)程及結(jié)果簡(jiǎn)潔明了，并獲得了滿意的計(jì)算效果。

1 多資源平衡工序排序優(yōu)化決策

1.1 多資源工序平衡優(yōu)化設(shè)計(jì)數(shù)學(xué)模型

對(duì)于多資源工序平衡問(wèn)題，前提假設(shè)是總工期為固定工期，設(shè)為T(mén)，即在時(shí)間T內(nèi)完成任務(wù)。由于是尋求資源平衡利用，故不需提前完成。

針對(duì)一般的問(wèn)題，設(shè)有n 道工序P1、P2、…Pn，各工序之間的邏輯關(guān)系、持續(xù)時(shí)間LT(Pi)、每道工序所需資源量Zj(Pi)為已知。那么根據(jù)各工序之間的邏輯關(guān)系和持續(xù)時(shí)間就可制訂出網(wǎng)絡(luò)計(jì)劃圖，計(jì)算出各工序最早/最晚開(kāi)工時(shí)間、最早/最晚完工時(shí)間（其分別記為ES(Pi)、LS(Pi)、EF(Pi)、LF(Pi)），并得出可進(jìn)行調(diào)整的工序名稱及其可調(diào)整量，進(jìn)而得出設(shè)計(jì)變量的維數(shù)及變量范圍。多資源平衡工序的優(yōu)化目標(biāo)是：

（1）總工期中的單位時(shí)間內(nèi)某種關(guān)鍵性資源需求的最大量應(yīng)盡可能小，即min{max(g(z))}，(g(z))為單位時(shí)間里資源占用量。該類優(yōu)化問(wèn)題計(jì)算出每個(gè)排序方案單位時(shí)間內(nèi)關(guān)鍵性資源需求量，并將各方案總工期T內(nèi)單位時(shí)間關(guān)鍵性資源需求量的最大值進(jìn)行比較，找出最小者對(duì)應(yīng)的工序編排即為最佳方案。

（2）總工期中關(guān)鍵性資源需求的波動(dòng)幅度盡可能小，即minσ2，σ2為資源占用量的標(biāo)準(zhǔn)方差。該類優(yōu)化問(wèn)題計(jì)算出每個(gè)排序方案總工期內(nèi)關(guān)鍵性資源需求量的標(biāo)準(zhǔn)方差，找出最小者對(duì)應(yīng)的工序編排即為最佳方案。

（3）綜合考慮所需各種資源對(duì)完成任務(wù)及成本的影響，使之最易實(shí)現(xiàn)。該類優(yōu)化問(wèn)題實(shí)質(zhì)上是一個(gè)多目標(biāo)優(yōu)化問(wèn)題，可通過(guò)多資源平衡的歸一化處理方法，將其等效為單目標(biāo)優(yōu)化問(wèn)題加以求解。

1.2 求解方法

本文應(yīng)用MATLAB遺傳算法工具箱函數(shù)及改進(jìn)的遺傳算法進(jìn)行求解。

（1）遺傳算法的改進(jìn)策略

在遺傳算法中，由于交叉產(chǎn)生的個(gè)體是隨機(jī)的，雖然這種隨機(jī)化的雜交形式在尋優(yōu)的初級(jí)階段保持了群體的多樣性，但在進(jìn)化的后期，大量個(gè)體集中于某一極值點(diǎn)上時(shí)，便造成了近親繁殖現(xiàn)象。尤其在用遺傳算法求解生產(chǎn)調(diào)度問(wèn)題時(shí)，經(jīng)常只能找到個(gè)別最優(yōu)解，甚至是局部最優(yōu)解。針對(duì)這一問(wèn)題，本文在遺傳算法中引入改進(jìn)策略，有助于查找到更多最優(yōu)解。

（2）引入最優(yōu)保存策略

最優(yōu)保存算法的基本思想是:在計(jì)算過(guò)程中始終保持所產(chǎn)生的最優(yōu)點(diǎn)，它不參與交叉運(yùn)算和變異運(yùn)算。如果當(dāng)前代的極優(yōu)點(diǎn)優(yōu)于保留的極優(yōu)點(diǎn)，則用此極優(yōu)點(diǎn)替換保留的極優(yōu)點(diǎn)，如果當(dāng)前代極優(yōu)點(diǎn)與保留的極優(yōu)點(diǎn)相同，但是個(gè)體不同，則認(rèn)為多解出現(xiàn)，將此極優(yōu)點(diǎn)同樣保留。

（3）引入子種群遷移策略

多種群遺傳算法的個(gè)體在種群之間以相同間隔遷移。選擇子種群最適應(yīng)的一部分個(gè)體遷移至鄰近的子種群中，即最鄰近的子種群在他們之間交換個(gè)體，均勻地重插入移民個(gè)體。這是提高收斂速度的有效方法。

2 計(jì)算實(shí)例

現(xiàn)有一工程計(jì)劃，其邏輯關(guān)系、工序時(shí)間及各工序所需資源如表1所示，要求在工期不改變的情況下，進(jìn)行如下多資源平衡優(yōu)化：

（1）施工周期中單位時(shí)間內(nèi)Q資源占用的最大值最小的計(jì)劃工序（Q資源計(jì)劃）；

（2）施工周期中單位時(shí)間內(nèi)Q資源波動(dòng)量最小的計(jì)劃工序（以標(biāo)準(zhǔn)差最小為準(zhǔn)）；

（3）假設(shè)Q、R、S資源對(duì)工序的權(quán)重分別為0.5，0.2，0.3，求此時(shí)單位時(shí)間所需資源波動(dòng)量最小的平衡工序計(jì)劃。

表1 工序邏輯關(guān)系及時(shí)間表

2.1 此工序問(wèn)題模型分析

（1）繪制網(wǎng)絡(luò)圖

根據(jù)工序邏輯關(guān)系及時(shí)間表1繪制的網(wǎng)絡(luò)計(jì)劃如圖1所示。

圖1 網(wǎng)絡(luò)計(jì)劃圖

（2）計(jì)算時(shí)間參數(shù)

根據(jù)表1及圖1計(jì)算出的時(shí)間參數(shù)明細(xì)表如表2所示。

此資源平衡優(yōu)化的前提為總工期T固定，因此，工序調(diào)整只能選擇非關(guān)鍵工序。一般而言，工序Pr(i，j)的時(shí)差越大，該工序調(diào)整的自由度就越大。在平衡優(yōu)化時(shí)，若將工序調(diào)整到時(shí)差為零，實(shí)際上它已變成關(guān)鍵工序，此時(shí)，一旦該工序在施工過(guò)程中發(fā)生意外，造成施工持續(xù)時(shí)間延長(zhǎng)，這時(shí)就會(huì)造成總工期增加，造成不必要的損失。由上述表格及網(wǎng)絡(luò)計(jì)劃，可進(jìn)行調(diào)整的工序?yàn)锽、C、E、G、J、L、M、O。

表2 工序邏輯關(guān)系及時(shí)間參數(shù)明細(xì)表

2.2 遺傳算法的應(yīng)用

MATLAB遺傳算法工具箱提供了廣泛多樣的有用函數(shù)，它使用MATLAB矩陣函數(shù)為實(shí)現(xiàn)廣泛領(lǐng)域的遺傳算法建立了一套通用工具，用戶可以通過(guò)這些命令行函數(shù)，根據(jù)實(shí)際分析的需要，編寫(xiě)出功能強(qiáng)大的應(yīng)用程序。

（1）初始種群的生成

在整個(gè)優(yōu)化策略中，是以每道工序開(kāi)工的時(shí)間作為設(shè)計(jì)變量的，由分析可知，實(shí)際上的設(shè)計(jì)變量只有8個(gè)，即工序B、C、E、G、J、L、M、O的開(kāi)工時(shí)間，其他工序開(kāi)工時(shí)間為定值。由表2可知，變量可以取的離散值個(gè)數(shù)為{4，22，8，6，3，14，6，7}，在此限定范圍內(nèi)隨機(jī)產(chǎn)生初始種群，并將其還原為真實(shí)的日期。

（2）適應(yīng)度值評(píng)價(jià)檢測(cè)

本文在進(jìn)行個(gè)體適應(yīng)度評(píng)價(jià)時(shí)，直接用目標(biāo)函數(shù)值作為適應(yīng)度函數(shù)值。MATLAB遺傳算法工具箱總是查找適應(yīng)度函數(shù)的最小值，因此一個(gè)種群的最佳適應(yīng)度值就是該種群中任何個(gè)體的最小適應(yīng)度值。

（3）控制參數(shù)(GA算子)選擇

控制參數(shù)的選取對(duì)遺傳算法的影響很大，但目前對(duì)于這些參數(shù)的合理選擇尚無(wú)理論依據(jù)，需要根據(jù)經(jīng)驗(yàn)數(shù)值和實(shí)際計(jì)算進(jìn)行選取。選擇較大的初始種群數(shù)目可以同時(shí)處理更多的解，但是增加了每次迭代的時(shí)間，一般種群數(shù)目取20~100。本例采用單點(diǎn)交叉方法，交叉率的選擇決定了交叉操作的頻率，頻率越高，可以越快收斂到最有希望的最優(yōu)解區(qū)域，一般選取較大的交叉率，但太高的頻率也可導(dǎo)致過(guò)早收斂，一般取0.4~0.9?；蜃儺惐ＷC了群體中個(gè)體的多樣性，較小的變異率不能提供較快的進(jìn)化速度，較難達(dá)到最高的適用度，過(guò)大的變異率雖然有助于全局的最優(yōu)搜索，但也會(huì)破壞基因重組產(chǎn)生的優(yōu)良個(gè)體，而需要更多的搜索代數(shù)，一般變異率取0.0001~0.1，工藝排序中排序的變異率可選為0.05左右。最大進(jìn)化代數(shù)作為模擬終止條件，取50~500。

（4）改進(jìn)策略

采用前面設(shè)計(jì)的最優(yōu)保存策略和子種群遷移策略。

2.3 求解及結(jié)果

根據(jù)所采用的策略編程計(jì)算，得出如下結(jié)果，均有多解，只列出各自其中3個(gè)。

問(wèn)題①對(duì)應(yīng)的工序B、C、E、G、J、L、M、O開(kāi)工時(shí)間 為：1-8-5-11-17-20-25-29；4-1-10-10-17-20-25-30；1-15-5-10-19-20-25-30；目標(biāo)值為13。

問(wèn)題②對(duì)應(yīng)的工序B、C、E、G、J、L、M、O開(kāi)工時(shí)間 為 ：1-8-5-12-17-21-23-29；1-8-6-13-17-21-23-30；1-8-5-12-17-21-23-31；目標(biāo)值為2.325。

問(wèn)題③對(duì)應(yīng)的工序B、C、E、G、J、L、M、O開(kāi)工時(shí)間 為 ：1-8-5-12-19-11-25-29；1-8-5-13-19-11-25-31；1-8-5-12-19-11-25-30；目標(biāo)值為3.645。問(wèn)題③的計(jì)算迭代過(guò)程如圖2所示。

圖2 目標(biāo)值與迭代過(guò)程關(guān)系圖

上述結(jié)果①表示采用此種工序編排策略時(shí)，施工周期中單位時(shí)間內(nèi)Q資源占用的最大值為13，其他排序方案單位時(shí)間內(nèi)Q資源占用的最大值均不小于13。結(jié)果②表示施工周期中單位時(shí)間內(nèi)Q資源的波動(dòng)量即標(biāo)準(zhǔn)方差最小為2.325；結(jié)果③表示按題設(shè)權(quán)重對(duì)Q、R、S三種資源進(jìn)行歸一化處理后，此時(shí)求得單位時(shí)間內(nèi)所需資源量標(biāo)準(zhǔn)方差的最小值為3.645。所考慮的優(yōu)化問(wèn)題均有多解也從另一個(gè)方面說(shuō)明了大量工序排序問(wèn)題方案的不唯一性。

3 結(jié)論

本文建立了多資源平衡工序優(yōu)化的數(shù)學(xué)模型，其建模過(guò)程簡(jiǎn)潔、明了。實(shí)例的工序問(wèn)題，每類優(yōu)化決策問(wèn)題就有4*22*8*6*3*14*6*7=7451136種排序方案，采用改進(jìn)的遺傳算法進(jìn)行計(jì)算，不同的問(wèn)題只須對(duì)功能函數(shù)稍作改變很快就可得出結(jié)果。通過(guò)引入最優(yōu)保存策略和子種群遷移策略，本文克服了傳統(tǒng)遺傳算法中的過(guò)早收斂和局部搜索能力差問(wèn)題，大大提高了搜索效率和收斂速度，并且獲得了多組最優(yōu)工序計(jì)劃(也從另一個(gè)方面說(shuō)明了大量工序排序問(wèn)題方案的不唯一性)，這使得生產(chǎn)調(diào)度安排靈活機(jī)動(dòng)，便于智能調(diào)度。

[1]楊永清.網(wǎng)絡(luò)計(jì)劃多資源平衡優(yōu)化工序排序方法研究[J].湖南輕工業(yè)高等專科學(xué)校學(xué)報(bào)，2003，15(3):5-7.

[2]何文章，宋 維.基于改進(jìn)混合遺傳算法安排生產(chǎn)調(diào)度[J].數(shù)學(xué)的實(shí)踐與認(rèn)識(shí)，2007，37(4):1-4.

[3]戴建國(guó).活動(dòng)網(wǎng)絡(luò)資源均衡問(wèn)題及其遺傳算法[J].系統(tǒng)工程學(xué)報(bào)，1996，11(2):29-36.

[4]牛東曉，乞建勛.工程網(wǎng)絡(luò)資源平衡的改進(jìn)型遺傳算法研究[J].華北電力大學(xué)學(xué)報(bào)，2000，27(3):1-5.

[5]周國(guó)華.遺傳算法及其在生產(chǎn)調(diào)度中的應(yīng)用[J].西南交通大學(xué)學(xué)報(bào)，2000，1(2):36-39.

[6]雷英杰，張善文，李續(xù)武等.MATLAB遺傳算法工具箱及應(yīng)用[M].西安電子科技大學(xué)出版社，2005.