遺傳算法在車間調度中的研究

李志林

(浙江理工大學理學院，浙江 杭州 310000)

1 引言(Introduction)

工件的加工需要資源，資源也是優化目標的一個重要因素。資源的定義很廣泛，例如加工工件所需的設備、員工、原材料等。我們把一般的資源，例如加工設備等統稱為機器，把除了加工設備以外的其他資源稱為額外資源。額外資源對調度的影響是多樣化的，例如額外資源使用的數量往往可以決定工件的加工速度；額外資源有時需要不斷損耗，有時又可以部分回收等。

遺傳算法在函數優化、組合優化、生產調度以及機器學習領域有著廣泛的應用。該算法基于對生物遺傳和進化過程中選擇、交叉、變異機理的模仿，來完成對問題最優解的自適應搜索過程。關于遺傳算法在車間調度中的應用，陳金廣等以最小化最大完工時間為優化目標，初始化時將種群規模擴大以增加種群多樣性，同時使用新的適應度函數讓染色體間更易區分。對于平行機調度的問題，孫超平研究了一類考慮外包的平行機調度問題，目標是使作業外包總成本與最大完工時間同時最小化。

對于目標函數為極小化最大完工時間的有資源約束的平行機調度問題||，該問題已經在很多文獻中進行了研究。特別地，當工件的加工時間均為單位時間時，GAREY等證明問題|???,p=1|在多項式時間()內可解；EDIS等在前人的基礎上，介紹了在工件的加工時間都是單位時間的前提下，對于問題當工件具有到達時間情況下的模型|1?1,r ,p=1|、問題|，=1|和問題|1?1,p=1|∑C都是多項式時間可解的。

2 問題的符號介紹及相關描述(Symbol introduction of the problem and its related description)

2.1 的相關符號介紹

2.2 問題的相關描述

問題的可行性條件：設有可行解的目標函數值，為對于某一資源，在任意時刻∈[0,]，最多有1臺機器正在使用。

3 遺傳算法的設計(Design of genetic algorithm)

遺傳算法在函數優化、組合優化、生產調度以及機器學習領域有著廣泛的應用。不同于其他調度問題，本文隨機產生初始種群時，并不能夠保證種群中的解是可行的，因此本文相對于其他遺傳算法產生初始種群過程，多了可行性判定過程，初始種群的每個可行解都要滿足本文資源約束的條件。這對于算法的運行時間有著重要的影響。同時在每次產生交叉種群與變異種群的過程中，也加入判別可行性的步驟，選取滿足條件的解加入新種群，每次迭代，選取種群中最優的解進行輸出。

通過上述性質可知，遺傳算法以群體搜索為特性，優化結果與初始條件無關，這將使得優化結果更好。下面給出具體的遺傳算法設計。

3.1 編碼方式

例如：對工件集合=(,,,,,,)，機器為,,的實例，如若其編碼串表述如下：(1,2,1,2,3,1,3)，第一個數字1表示工件在第一臺機器上的第一個位置，第二個數字2表示工件在第二臺機器上的第一個位置，第三個數字1表示工件在第一臺機器上的第二個位置，第四個數字2表示工件在第二臺機器上的第二個位置加工，其他定義類似。則可知工件在機器上的順序為(,,)，機器上加工順序為(,)，機器上的順序為(,)。

由此，編碼表的定義已經說明完成，任意解根據編碼都可以準確地刻畫出其具體排序方式，方便問題求解。

3.2 初始種群的設計

遺傳算法的初始種群采取隨機生成原則。根據本文問題和編碼的特點，采取如下產生初始種群方法。

對于個工件的集合，按照工件的順序，對每個工件，在滿足資源約束的條件下任意選取一臺機器進行加工，本文設置初始種群為15 個可行解?？尚薪猱a生的方法如下所述。

3.3 交叉變異以及選擇策略的設計

交叉與變異運算是遺傳算法的核心，它決定了算法的收斂速度以及優化結果。本文用目標函數值來衡量個體的適應度，針對本文的問題，目標函數為最小化最大完工時間min，即：目標函數越小，適應度越高。同時對于交叉變異個體的選取方式如下所述。

(4)遺傳算子的選取。針對本文特點，交叉變異后的個體，并不一定能夠滿足本文的資源約束條件，則對交叉變異后的新個體，進行可行性判定，若滿足可行性判定，則令其=，若不滿足，則令其適應度的較大數值=10。由此來篩選下一代的個體，同時為了避免原種群較優的個體丟失，融合新舊種群，對種群中所有個體的適應度由小到大排序，選取適應度最優的前15 個個體作為下一次迭代的父代。

3.4 算法的具體設計

步驟1：參數初始化。設定種群規模=15,最大迭代次數，交叉概率 P和變異概率 P。

步驟4：同時對于步驟3產生的新個體，隨機產生的變異概率P，判斷其是否滿足P＜0.1，若滿足，則繼續隨機選取節點的方式進行單點變異，產生新的個體，加入種群；若無需交叉，直接加入新種群。

4 數值模擬及結果分析(Numerical simulation and result analysis)

采用數值計算的方式來驗證所設計的遺傳算法，算法采用了Python 3.10.1來實現算法和對數值實驗的模擬，電腦的運行環境為Intel(R) Core(TM) i5-8250U CPU @ 1.60 GHz 1.80 GHz和8GB Ram。本文的數值模擬實例通過隨機產生，分別對小規模實例和大規模實例進行分析，目的是更好地證明該算法的有效性。

表1 小規模實例運行20 次的 αavg數據結果Tab.1 αavg data results of a small-scale instance running for 20 times

同樣需要驗證算法對大規模實例的效果。增加工件數為100，資源種類數為20，迭代次數為50進行分析。工件大小分別從[0,30]、[0,50]、[0,100]中隨機取數的不同類型進行分析，每類問題中工件的大小隨機產生20 個實例進行實驗，對、和進行對比，可以看到，當工件個數和大小持續增加時，穩定在1.05以內，而最壞情況，也在1.2范圍內，該遺傳算法對于求解本文問題有著較好的優化作用。如表2所示。

表2 100 個工件的實驗結果Tab.2 Experimental results of 100 workpieces

圖1 遺傳算法迭代收斂圖Fig.1 Iterative convergence diagram of genetic algorithm

5 結論(Conclusion)