李志林

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

1 引言(Introduction)

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

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

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

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

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

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

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

3 遺傳算法的設(shè)計(jì)(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)生初始種群時(shí)，并不能夠保證種群中的解是可行的，因此本文相對(duì)于其他遺傳算法產(chǎn)生初始種群過程，多了可行性判定過程，初始種群的每個(gè)可行解都要滿足本文資源約束的條件。這對(duì)于算法的運(yùn)行時(shí)間有著重要的影響。同時(shí)在每次產(chǎn)生交叉種群與變異種群的過程中，也加入判別可行性的步驟，選取滿足條件的解加入新種群，每次迭代，選取種群中最優(yōu)的解進(jìn)行輸出。

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

3.1 編碼方式

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

表2 100 個(gè)工件的實(shí)驗(yàn)結(jié)果Tab.2 Experimental results of 100 workpieces

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

5 結(jié)論(Conclusion)