李志林

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

1 引言(Introduction)

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

遺傳算法在函數(shù)優(yōu)化、組合優(yōu)化、生產(chǎn)調(diào)度以及機(jī)器學(xué)習(xí)領(lǐng)域有著廣泛的應(yīng)用。該算法基于對生物遺傳和進(jìn)化過程中選擇、交叉、變異機(jī)理的模仿，來完成對問題最優(yōu)解的自適應(yīng)搜索過程。關(guān)于遺傳算法在車間調(diào)度中的應(yīng)用，陳金廣等以最小化最大完工時間為優(yōu)化目標(biāo)，初始化時將種群規(guī)模擴(kuò)大以增加種群多樣性，同時使用新的適應(yīng)度函數(shù)讓染色體間更易區(qū)分。對于平行機(jī)調(diào)度的問題，孫超平研究了一類考慮外包的平行機(jī)調(diào)度問題，目標(biāo)是使作業(yè)外包總成本與最大完工時間同時最小化。

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

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

2.1 的相關(guān)符號介紹

2.2 問題的相關(guān)描述

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

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

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

通過上述性質(zhì)可知，遺傳算法以群體搜索為特性，優(yōu)化結(jié)果與初始條件無關(guān)，這將使得優(yōu)化結(jié)果更好。下面給出具體的遺傳算法設(shè)計。

3.1 編碼方式

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

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

3.2 初始種群的設(shè)計

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

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

3.3 交叉變異以及選擇策略的設(shè)計

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

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

3.4 算法的具體設(shè)計

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

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

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

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

表1 小規(guī)模實例運(yùn)行20 次的 αavg數(shù)據(jù)結(jié)果Tab.1 αavg data results of a small-scale instance running for 20 times

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

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

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

5 結(jié)論(Conclusion)