基于遺傳算法的多資源平衡工序排序優化決策

付宗仁

（海軍91832部隊裝備部，廣西 北海 536000）

生產過程中工序編排是生產管理中極其重要的一個環節，處理得好與壞，直接影響產品的生產周期及經濟效益，對此人們已有充分的認識。但工序排序屬N-P完備問題，至今尚無特別簡便、有效的方法加以解決，人們一般沿襲傳統作法憑經驗辦事，或用一粗糙的近似算法，效果都不理想。隨著計算機在生產過程中的廣泛應用，使用它們解決排序問題，已成為一種快捷、有效的途徑。

工序編排有兩類問題，一是基于資源約束，通過合理安排工序尋求最短的生產周期，從而盡快完成任務；一是在總工期不變即固定工期的情況下，通過工序編排，使各資源需求數量盡可能達到平衡使用，以減少資源儲備或使工程物資供應有保障，從而增強實現計劃的可能性，并通過資源平衡，達到減少資源閑置與浪費、降低工程成本的目的。

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

本文建立了典型的網絡計劃多資源平衡工序優化的數學模型，應用MATLAB遺傳算法工具箱函數及改進的遺傳算法對其進行了研究，設計了可直接求解出最佳工序編排及其對應的目標函數值的功能函數，使建模過程及結果簡潔明了，并獲得了滿意的計算效果。

1 多資源平衡工序排序優化決策

1.1 多資源工序平衡優化設計數學模型

對于多資源工序平衡問題，前提假設是總工期為固定工期，設為T，即在時間T內完成任務。由于是尋求資源平衡利用，故不需提前完成。

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

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

（2）總工期中關鍵性資源需求的波動幅度盡可能小，即minσ2，σ2為資源占用量的標準方差。該類優化問題計算出每個排序方案總工期內關鍵性資源需求量的標準方差，找出最小者對應的工序編排即為最佳方案。

（3）綜合考慮所需各種資源對完成任務及成本的影響，使之最易實現。該類優化問題實質上是一個多目標優化問題，可通過多資源平衡的歸一化處理方法，將其等效為單目標優化問題加以求解。

1.2 求解方法

本文應用MATLAB遺傳算法工具箱函數及改進的遺傳算法進行求解。

（1）遺傳算法的改進策略

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

（2）引入最優保存策略

最優保存算法的基本思想是:在計算過程中始終保持所產生的最優點，它不參與交叉運算和變異運算。如果當前代的極優點優于保留的極優點，則用此極優點替換保留的極優點，如果當前代極優點與保留的極優點相同，但是個體不同，則認為多解出現，將此極優點同樣保留。

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

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

2 計算實例

現有一工程計劃，其邏輯關系、工序時間及各工序所需資源如表1所示，要求在工期不改變的情況下，進行如下多資源平衡優化：

（1）施工周期中單位時間內Q資源占用的最大值最小的計劃工序（Q資源計劃）；

（2）施工周期中單位時間內Q資源波動量最小的計劃工序（以標準差最小為準）；

（3）假設Q、R、S資源對工序的權重分別為0.5，0.2，0.3，求此時單位時間所需資源波動量最小的平衡工序計劃。

表1 工序邏輯關系及時間表

2.1 此工序問題模型分析

（1）繪制網絡圖

根據工序邏輯關系及時間表1繪制的網絡計劃如圖1所示。

圖1 網絡計劃圖

（2）計算時間參數

根據表1及圖1計算出的時間參數明細表如表2所示。

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

表2 工序邏輯關系及時間參數明細表

2.2 遺傳算法的應用

MATLAB遺傳算法工具箱提供了廣泛多樣的有用函數，它使用MATLAB矩陣函數為實現廣泛領域的遺傳算法建立了一套通用工具，用戶可以通過這些命令行函數，根據實際分析的需要，編寫出功能強大的應用程序。

（1）初始種群的生成

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

（2）適應度值評價檢測

本文在進行個體適應度評價時，直接用目標函數值作為適應度函數值。MATLAB遺傳算法工具箱總是查找適應度函數的最小值，因此一個種群的最佳適應度值就是該種群中任何個體的最小適應度值。

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

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

（4）改進策略

采用前面設計的最優保存策略和子種群遷移策略。

2.3 求解及結果

根據所采用的策略編程計算，得出如下結果，均有多解，只列出各自其中3個。

問題①對應的工序B、C、E、G、J、L、M、O開工時間 為：1-8-5-11-17-20-25-29；4-1-10-10-17-20-25-30；1-15-5-10-19-20-25-30；目標值為13。

問題②對應的工序B、C、E、G、J、L、M、O開工時間 為 ：1-8-5-12-17-21-23-29；1-8-6-13-17-21-23-30；1-8-5-12-17-21-23-31；目標值為2.325。

問題③對應的工序B、C、E、G、J、L、M、O開工時間 為 ：1-8-5-12-19-11-25-29；1-8-5-13-19-11-25-31；1-8-5-12-19-11-25-30；目標值為3.645。問題③的計算迭代過程如圖2所示。

圖2 目標值與迭代過程關系圖

上述結果①表示采用此種工序編排策略時，施工周期中單位時間內Q資源占用的最大值為13，其他排序方案單位時間內Q資源占用的最大值均不小于13。結果②表示施工周期中單位時間內Q資源的波動量即標準方差最小為2.325；結果③表示按題設權重對Q、R、S三種資源進行歸一化處理后，此時求得單位時間內所需資源量標準方差的最小值為3.645。所考慮的優化問題均有多解也從另一個方面說明了大量工序排序問題方案的不唯一性。

3 結論

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

[1]楊永清.網絡計劃多資源平衡優化工序排序方法研究[J].湖南輕工業高等專科學校學報，2003，15(3):5-7.

[2]何文章，宋 維.基于改進混合遺傳算法安排生產調度[J].數學的實踐與認識，2007，37(4):1-4.

[3]戴建國.活動網絡資源均衡問題及其遺傳算法[J].系統工程學報，1996，11(2):29-36.

[4]牛東曉，乞建勛.工程網絡資源平衡的改進型遺傳算法研究[J].華北電力大學學報，2000，27(3):1-5.

[5]周國華.遺傳算法及其在生產調度中的應用[J].西南交通大學學報，2000，1(2):36-39.

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