金 秋 王清巖 原博文

（天津科技大學(xué)經(jīng)濟(jì)與管理學(xué)院，天津 300457）

柔性作業(yè)車間調(diào)度問題（FJSP）是柔性制造系統(tǒng)中的一項(xiàng)關(guān)鍵調(diào)度問題，有效的生產(chǎn)調(diào)度對(duì)于提高工業(yè)生產(chǎn)效率和資源利用率具有重要意義。在FJSP 中，每個(gè)作業(yè)都可以在不同的機(jī)器上完成，并且每個(gè)作業(yè)在每臺(tái)機(jī)器上的加工時(shí)間可能存在差異。此外，每個(gè)作業(yè)的工序順序也可能不同，使得FJSP 成為一個(gè)復(fù)雜的NP-Hard 問題[1]。

在解決FJSP 問題時(shí)，Brucker P 和Schlie R 提出了一種多項(xiàng)式圖算法[2]，然而該算法在處理多工件、多機(jī)床、大規(guī)模和多約束調(diào)度問題時(shí)效果不佳。因此，研究人員開始嘗試采用啟發(fā)式優(yōu)化算法來(lái)解決這些問題。

粒子群算法[3]、遺傳算法[4]、貪婪算法[5]和蟻群算法[6]等是常見的啟發(fā)式算法，在學(xué)術(shù)研究中被廣泛應(yīng)用。相較于其他算法，遺傳算法具有過程簡(jiǎn)單、搜索能力快和魯棒性好等優(yōu)點(diǎn)。因此，在解決柔性作業(yè)車間調(diào)度問題時(shí)，遺傳算法被廣泛采用[7-10]。然而，傳統(tǒng)的遺傳算法存在收斂速度慢和容易陷入局部最優(yōu)等問題。因此，近年來(lái)國(guó)內(nèi)外研究人員對(duì)傳統(tǒng)的遺傳算法進(jìn)行了改進(jìn)，以克服其不足之處。王佳怡等[11]構(gòu)建了一個(gè)多目標(biāo)混合整數(shù)線性規(guī)劃模型，設(shè)計(jì)了一種改進(jìn)的遺傳算法，引入了基于多父代的交叉算子和多種變異算子，并結(jié)合了精英保留和輪盤賭選擇策略。姜一嘯等[12]提出了一種低碳調(diào)度模型，采用改進(jìn)的帶精英策略的非支配遺傳算法（NSGA-II）來(lái)優(yōu)化該模型。唐藝軍等[13]提出了一種改進(jìn)的混合遺傳算法，結(jié)合了模擬退火算法和萊維飛行擾動(dòng)策略，以提高算法性能。趙慧娟等[14]提出了一種方法，考慮不同情境下目標(biāo)權(quán)重系數(shù)的變化，并采用改進(jìn)的遺傳算法來(lái)優(yōu)化完工時(shí)間、能耗和質(zhì)量的權(quán)衡模型。Chen R 等[15]提出了一種自學(xué)習(xí)遺傳算法（SLGA），其中采用遺傳算法（GA）作為基本優(yōu)化方法，并基于強(qiáng)化學(xué)習(xí)（RL）對(duì)其關(guān)鍵參數(shù)進(jìn)行智能調(diào)整。

根據(jù)國(guó)內(nèi)外學(xué)者們對(duì)FJSP 的相關(guān)研究現(xiàn)狀，存在以下幾個(gè)問題：（1）使用的優(yōu)化算法的尋優(yōu)能力一般，主要是算法的反應(yīng)時(shí)間太長(zhǎng)，容易進(jìn)入局部最優(yōu)解，并且關(guān)鍵參數(shù)無(wú)法進(jìn)行有效的動(dòng)態(tài)調(diào)整，導(dǎo)致求解效率和質(zhì)量無(wú)法滿足生產(chǎn)要求；（2）優(yōu)化的目標(biāo)過于單一，優(yōu)化目標(biāo)往往只考慮了最大完工時(shí)間，沒有反映車間的實(shí)際生產(chǎn)情況。

為此，本文建立以最大完工時(shí)間和能耗為目標(biāo)的數(shù)學(xué)模型，提出了一種改進(jìn)算法。該算法針對(duì)無(wú)法動(dòng)態(tài)調(diào)整參數(shù)的問題，對(duì)交叉變異算子進(jìn)行了非均勻改進(jìn)，并引入了基于鄰域的變異算子，以提高算法的搜索能力和穩(wěn)定性。

1 問題描述及數(shù)學(xué)模型

1.1 問題描述

FJSP 是對(duì)經(jīng)典JSP 的擴(kuò)展，用于描述N個(gè)待加工工件在M臺(tái)機(jī)器上進(jìn)行加工。每個(gè)工件由S道工序組成，F(xiàn)JSP 問題的主要參數(shù)見表1。

1.2 柔性作業(yè)車間調(diào)度模型

對(duì)于FJSP，每個(gè)作業(yè)由一系列優(yōu)先級(jí)受限的操作組成，這些操作的加工時(shí)間在不同分配的機(jī)器之間是不同的。本文旨在建立一個(gè)多目標(biāo)柔性作業(yè)車間調(diào)度模型，目標(biāo)函數(shù)是將歸一化的最大完工時(shí)間和能耗加權(quán)最小化，見式（7），并給出一些約束條件。

約束條件：

對(duì)目標(biāo)函數(shù)的處理、加權(quán)：

最小化最大完工時(shí)間用式（1）表示；通過式（2）可以實(shí)現(xiàn)最小化加工能耗；式（3）描述了同一工件工序的先后約束關(guān)系；任一工序的完工時(shí)間均需滿足式（4）的約束；式（5）表示工序的加工時(shí)間大于零；式（6）表示所有工件在0 時(shí)刻開始加工。式（7）為目標(biāo)函數(shù)，其中 φ為權(quán)重系數(shù)，0＜ φ＜1。

2 改進(jìn)遺傳算法

2.1 改進(jìn)遺傳算法流程

改進(jìn)后算法流程圖如圖1 所示，具體步驟如下。

圖1 改進(jìn)后的遺傳算法流程圖

步驟一：設(shè)置相關(guān)參數(shù)，隨機(jī)生成一組初始種群。

步驟二：編碼與解碼。

步驟三：采用輪盤賭策略，選擇優(yōu)秀個(gè)體。

步驟四：計(jì)算種群個(gè)體適應(yīng)度值。

步驟五：對(duì)選中父代進(jìn)行均勻交叉操作，改變個(gè)體的編碼，再經(jīng)過非均勻交叉率篩選。

步驟六：對(duì)工件編碼進(jìn)行鄰域搜索變異操作，對(duì)機(jī)器編碼采用單點(diǎn)變異，再經(jīng)過非均勻變異率，以此提高算法的搜索能力和穩(wěn)定性。

步驟七：判斷是否滿足終止條件，如果達(dá)到最大迭代次數(shù)或達(dá)到停止條件時(shí)，終止迭代過程，否則返回步驟四。

步驟八：輸出結(jié)果。

2.2 編碼與解碼

FJSP 的染色體由操作順序部分和機(jī)器分配部分組成，這種編碼方式可簡(jiǎn)化解碼過程，降低成本。圖2 展示表2 中的一個(gè)FJSP 實(shí)例的編碼示例，它表示優(yōu)化問題的解決方案，其中操作的機(jī)器分配用粗體表示。染色體的長(zhǎng)度是操作次數(shù)的兩倍，在該實(shí)例中共有8 個(gè)操作，因此染色體的長(zhǎng)度為16。掃描操作順序時(shí)，工件層按照從左到右的順序，第一個(gè)“l(fā)”是指在機(jī)器M3上處理的作業(yè)J1的第一個(gè)操作，對(duì)應(yīng)機(jī)器分配部分的“3”；第二個(gè)“1”表示將在機(jī)器M2上處理的工件1 的第二個(gè)操作，對(duì)應(yīng)機(jī)器分配部分中的“2”。根據(jù)上述說明，機(jī)器M1的操作順序?yàn)镺41→O21→O32，機(jī)器M2為O31→O42→O12，機(jī)器M3為O11→O22。求解的操作順序和機(jī)器分配可以解釋為：{(O11,M3),(O41,M1),(O31,M2),(O21,M1),(O42,M2),(O32,M1),(O12,M2),(O22,M3)}。

圖2 表1 染色體的編碼圖

表2 一個(gè)4×3 的部分FJSP 實(shí)例

2.3 適應(yīng)度函數(shù)

適應(yīng)度函數(shù)是評(píng)估個(gè)體質(zhì)量、篩選方案和確定群體中優(yōu)秀個(gè)體的方法。通常，適應(yīng)度函數(shù)通過計(jì)算個(gè)體的適應(yīng)度來(lái)實(shí)現(xiàn)，該適應(yīng)度基于目標(biāo)函數(shù)值的倒數(shù)。在遺傳算法中，適應(yīng)度函數(shù)起著重要作用，能夠量化個(gè)體的適應(yīng)程度，并作為選擇和進(jìn)化的依據(jù)。通過適應(yīng)度函數(shù)的評(píng)估，遺傳算法能夠優(yōu)化搜索過程，保留和發(fā)展群體中更優(yōu)秀的個(gè)體。適應(yīng)度函數(shù)為

式中：fit(f(x)) 為適應(yīng)度值；Cmax為最大完工時(shí)間；E為機(jī)器加工的總負(fù)荷；φ為權(quán)重系數(shù)。

2.4 選擇操作

為了使遺傳算法在迭代早期朝著更好、更有優(yōu)勢(shì)的方向發(fā)展，選擇操作用于從群體中選出優(yōu)秀的個(gè)體。常用的基于適應(yīng)度值進(jìn)行選擇的方法是輪盤賭選擇法。該方法根據(jù)個(gè)體的適應(yīng)度值來(lái)確定選擇概率，適應(yīng)度值越高的個(gè)體被選中的概率也越高，這樣可以確保優(yōu)秀的個(gè)體在群體中得到更多被選擇的機(jī)會(huì)，記為Pa。

Pa的計(jì)算公式為

式中：fa為群體中每個(gè)個(gè)體的適應(yīng)度值；F為種群的總適應(yīng)度。

2.5 交叉操作

本文采用了均勻交叉方式來(lái)生成新個(gè)體。具體實(shí)現(xiàn)是隨機(jī)選擇兩個(gè)個(gè)體的基因位，并以相等的概率交換這些基因位，從而產(chǎn)生兩個(gè)新的個(gè)體。這種交叉方式的目的是增加遺傳算法的多樣性，提高全局搜索的效果。為解決這個(gè)問題，引入了非均勻交叉概率Pc：

式中：Pc0表示初始交叉率；gen表示當(dāng)前迭代次數(shù)；MAXGEN表示總的迭代次數(shù)；γ為(0,1)的常數(shù)。

在遺傳算法中，交叉操作采用了多種不同的方式，包括均勻交叉、多點(diǎn)交叉、局部均勻交叉、順序交叉和周期交叉等方法。這些方法提供了多樣的策略，用于在遺傳算法的進(jìn)化過程中實(shí)現(xiàn)基因的交換和組合。本文采用了均勻交叉方式，其具體實(shí)現(xiàn)是隨機(jī)選擇兩個(gè)個(gè)體的基因位，并以相等的概率交換這些基因位，從而生成兩個(gè)新的個(gè)體。均勻交叉是一種常見的遺傳算法交叉操作方式，能夠幫助算法更好地搜索解空間，增強(qiáng)全局搜索能力。均勻交叉的示例圖如圖3 所示。

圖3 染色體工序編碼交叉示例圖

被選擇進(jìn)行交叉操作的基因位在圖3 和圖4 中為陰影部分，而每一個(gè)基因位被選擇的概率都是隨機(jī)的，不是確定的。

圖4 染色體機(jī)器編碼交叉示例圖

2.6 變異操作

傳統(tǒng)遺傳算法領(lǐng)域，常見的做法是使用固定的變異概率進(jìn)行操作。然而，這種方式可能使算法陷入局部最優(yōu)解，從而無(wú)法找到更優(yōu)的解決方案。為了解決這個(gè)問題，可以引入非均勻變異率Pm，使得遺傳算法在搜索空間中進(jìn)行更全面的探索。

通常情況下，初始階段的變異率較高，以便快速地探索解空間。隨著迭代次數(shù)的增加，變異率逐漸降低，以便更精確地搜索最優(yōu)解。具體的非均勻變異率可以根據(jù)式（11）來(lái)計(jì)算。

式中：Pm0為初始變異率。這個(gè)函數(shù)的意義是，隨著迭代次數(shù)的增加，變異率會(huì)隨之緩慢降低，ρ的范圍在(0,1)，作用是控制變異率的下降速度，ρ的值接近1 時(shí)，變異率的下降速度會(huì)比較緩慢；ρ的值接近0 時(shí)，變異率的下降速度會(huì)比較快。運(yùn)用非均勻變異使得變異率隨著迭代次數(shù)的增加逐漸降低，以達(dá)到更好的優(yōu)化效果。本文提出了一種改進(jìn)的工件編碼變異方法，旨在提高子代適應(yīng)度并朝著更優(yōu)的方向進(jìn)化，同時(shí)保持種群多樣性。該方法利用基于鄰域搜索的變異算子來(lái)進(jìn)行工件編碼的變異。在機(jī)器編碼中，采用了單點(diǎn)變異法來(lái)替換機(jī)器的選擇操作。具體的操作示意如圖5 和圖6 所示。

圖5 工序?qū)踊卩徲虿僮鞯淖儺惒僮?/p>

圖6 機(jī)器編碼單點(diǎn)變異操作

變鄰域變異操作具體步驟如下：

（1）選出一定數(shù)量的不同位置，代表不同工件的基因。這些位置可以是隨機(jī)選擇或者使用其他策略進(jìn)行選擇。

（2）對(duì)于這些位置進(jìn)行全排列，生成當(dāng)前鄰域中的所有解。對(duì)這些位置進(jìn)行全排列，可以得到鄰域解的不同組合。

（3）計(jì)算每個(gè)鄰域解的適應(yīng)度，根據(jù)具體問題使用適應(yīng)度函數(shù)進(jìn)行評(píng)估。

（4）具有最佳適應(yīng)度的鄰域解被選擇為當(dāng)前解。根據(jù)適應(yīng)度的評(píng)估結(jié)果，選擇適應(yīng)度最高的鄰域解作為當(dāng)前解。

通過以上步驟，可以實(shí)現(xiàn)變鄰域操作，增加搜索空間和多樣性，從而提高算法的收斂性和搜索能力。

3 仿真結(jié)果與分析

為了評(píng)估本文提出的改進(jìn)非均勻交叉和非均勻變異的遺傳算法的性能，選取基準(zhǔn)算例kacem01 和kacem03 進(jìn)行測(cè)試[16]。其中，kacem01 算例表示4個(gè)工件對(duì)應(yīng)5 臺(tái)加工機(jī)器，而kacem03 算例表示10 個(gè)工件對(duì)應(yīng)10 臺(tái)加工設(shè)備。使用Matlab R2023a作為具體的數(shù)據(jù)仿真軟件，并將仿真結(jié)果同傳統(tǒng)遺傳算法進(jìn)行比較。本文相關(guān)參數(shù)設(shè)置為：最大迭代次數(shù)MAXGEN=300，選擇率Ps=0.8，初始交叉率Pc=0.8，初始變異率Pm=0.03。

4×5 和10×10 算例的迭代過程如圖7 和圖8 所示，可以看出，本文提出的改進(jìn)遺傳算法所得到的最優(yōu)解均低于平均值，證明該改進(jìn)算法在尋找最優(yōu)解方面具有更強(qiáng)的能力。

圖7 4×5 迭代過程圖

圖8 10×10 迭代過程圖

對(duì)比圖9 和圖10 可以看出改進(jìn)后遺傳算法與傳統(tǒng)遺傳算法之間的差異。目標(biāo)函數(shù)用于衡量解的優(yōu)劣，如果目標(biāo)函數(shù)是最小化的，適應(yīng)度越低表示解越好。這是因?yàn)檫m應(yīng)度是根據(jù)目標(biāo)函數(shù)的值來(lái)計(jì)算的，而目標(biāo)函數(shù)越小越好。因此，適應(yīng)度越低表示解越接近最優(yōu)解。通過觀察圖9 和圖10 可以發(fā)現(xiàn)，改進(jìn)后的遺傳算法在最優(yōu)適應(yīng)度方面表現(xiàn)更低。

圖9 4×5 改進(jìn)后的遺傳算法與改進(jìn)前遺傳算法的對(duì)比圖

圖10 10×10 改進(jìn)后遺傳算法與改進(jìn)前遺傳算法的對(duì)比圖

本文基于改進(jìn)的遺傳算法所求得的調(diào)度結(jié)果如圖11 和圖12 所示。在遺傳算法等優(yōu)化算法中，通常會(huì)使用適應(yīng)度來(lái)評(píng)估個(gè)體的優(yōu)劣，并根據(jù)適應(yīng)度來(lái)進(jìn)行選擇、交叉和變異等操作，以搜索最優(yōu)解。由圖11 和圖12 可以看出，改進(jìn)后的遺傳算法在獲取解的質(zhì)量上有明顯的提升，在4×5 的經(jīng)典算例中最優(yōu)適應(yīng)度從6.5 優(yōu)化到4，10×10 的算例中則從6優(yōu)化到3，證明了改進(jìn)后算法的優(yōu)越性。

圖11 4×5 改進(jìn)后遺傳算法調(diào)度結(jié)果甘特圖

圖12 10×10 改進(jìn)后遺傳算法調(diào)度結(jié)果甘特圖

4 結(jié)語(yǔ)

本文提出了一個(gè)柔性作業(yè)車間調(diào)度問題模型，目標(biāo)函數(shù)為最小化最大完工時(shí)間和最小化總能耗。為了有效解決該問題，引入了改進(jìn)的遺傳算法方法。

通過引入非均勻改進(jìn)，能夠根據(jù)問題的特點(diǎn)和種群的演化階段動(dòng)態(tài)調(diào)整交叉率和變異率，改進(jìn)的遺傳算法可以提高算法的全局搜索的能力。并且在變異操作中，對(duì)工件編碼使用鄰域變異，對(duì)機(jī)器編碼使用單點(diǎn)變異，以增加解空間的探索能力和多樣性。

通過這種改進(jìn)的遺傳算法，期望能夠找到更好的解決方案，并優(yōu)化算法的性能。該算法能夠在較短的時(shí)間內(nèi)收斂到較優(yōu)的解，從而提高問題的求解效率。

為了驗(yàn)證改進(jìn)遺傳算法的效果，進(jìn)行了改進(jìn)遺傳算法和傳統(tǒng)遺傳算法的對(duì)比實(shí)驗(yàn)，選取經(jīng)典算例kacem。實(shí)驗(yàn)結(jié)果表明，改進(jìn)后的算法的最優(yōu)適應(yīng)度明顯低于傳統(tǒng)遺傳算法。

然而，本研究還存在一些局限性，只考慮了完工時(shí)間和能耗這兩個(gè)目標(biāo)，而實(shí)際生產(chǎn)中可能還存在其他重要目標(biāo)。此外，本研究?jī)H針對(duì)靜態(tài)調(diào)度問題，對(duì)于動(dòng)態(tài)調(diào)度問題仍需進(jìn)一步研究。