改進(jìn)遺傳算法求解柔性作業(yè)車間調(diào)度問(wèn)題

摘要：為優(yōu)化生產(chǎn)要素配置提高資源利用率，構(gòu)建了以最小化最大完工時(shí)間為目標(biāo)的調(diào)度模型，提出了一種自調(diào)整搜索域的改進(jìn)遺傳算法求解柔性作業(yè)車間調(diào)度問(wèn)題（Flexible Job-shop Scheduling Problem， FJSP） 。算法采用基于工序排列和機(jī)器選擇的雙層染色體編碼的設(shè)計(jì)方案。設(shè)計(jì)了新的種群初始化方法，在交叉和變異階段，引入自適應(yīng)參數(shù)，優(yōu)化遺傳操作流程。在進(jìn)化后期引入新種群增加染色體的多樣性，自調(diào)整算法搜索域，幫助種群跳出局部最優(yōu)，找到更好的全局解。實(shí)驗(yàn)結(jié)果表明提出的改進(jìn)遺傳算法在優(yōu)化精度和收斂能力方面表現(xiàn)良好。

關(guān)鍵詞：作業(yè)車間調(diào)度；柔性；遺傳算法；自調(diào)整搜索域；染色體多樣性

中圖分類號(hào)：TP18;TH165 文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1009-3044（2024）27-0079-04

0 引言

柔性作業(yè)車間調(diào)度問(wèn)題（Flexible Job-shop Sched?uling Problem， FJSP） 是作業(yè)車間調(diào)度問(wèn)題（Job-shopScheduling Problem，JSP） 模型的擴(kuò)展[1]，更緊密地貼合了現(xiàn)實(shí)生產(chǎn)場(chǎng)景[2]。FJSP賦予了在機(jī)器選擇上的更大自由度，能夠應(yīng)對(duì)涉及眾多機(jī)器、多重工序及任務(wù)的復(fù)雜調(diào)度需求[3]，從而更好地適應(yīng)多變且復(fù)雜的生產(chǎn)環(huán)境，也因此備受學(xué)界及業(yè)界的關(guān)注。

通過(guò)國(guó)內(nèi)外學(xué)者的深入探索，智能優(yōu)化算法在處理FJSP時(shí)顯示出比傳統(tǒng)方法更強(qiáng)的適應(yīng)性和靈活性。特別是面對(duì)大型復(fù)雜的FJSP時(shí)，智能優(yōu)化算法展現(xiàn)出了卓越的性能，能夠在廣闊的解空間中迅速鎖定全局最優(yōu)解，優(yōu)化資源的使用效率。龍等人[4] 通過(guò)結(jié)合強(qiáng)化學(xué)習(xí)算法，強(qiáng)化了人工蜂群算法的全局搜索能力和收斂精確性。賈等人[5]提出了一種改進(jìn)的粒子群優(yōu)化算法，通過(guò)自適應(yīng)調(diào)整參數(shù)和采用混沌局部?jī)?yōu)化器，顯著提升搜索精確性和收斂速度。李星宇等[6]提出了一種創(chuàng)新的混合算法，該算法融合了遺傳算法和禁忌搜索兩種策略來(lái)求解，在實(shí)現(xiàn)全局尋優(yōu)的同時(shí)，也能進(jìn)行精細(xì)的局部調(diào)整。邢麗玲等[7]提出了一種基于知識(shí)的蟻群優(yōu)化求解FJSP。此模型從蟻群優(yōu)化中學(xué)習(xí)，并將獲得的知識(shí)應(yīng)用到當(dāng)前的搜索過(guò)程中。張國(guó)輝[8]提出了一種混合粒子群和禁忌搜索來(lái)解決包含多個(gè)沖突和不可通約因素的FJSP，算法在處理復(fù)雜、多沖突的FJSP時(shí)表現(xiàn)出更高的效率和準(zhǔn)確性。

遺傳算法（Genetic Algorithm，GA） 作為智能優(yōu)化算法的代表，在解決FJSP中展現(xiàn)出卓越的性能。GA基于候選解的種群，通過(guò)交叉、變異等遺傳操作不斷生成新的解決方案。此外，GA還具備強(qiáng)大的并行處理能力，能夠同時(shí)優(yōu)化多個(gè)目標(biāo)，如機(jī)器配置、時(shí)間分配等，從而實(shí)現(xiàn)資源的高效利用和生產(chǎn)效率的提升。

本研究以遺傳算法為核心，致力于以最小化最大完工時(shí)間為主要優(yōu)化目標(biāo)。提出了一種自調(diào)整搜索域的改進(jìn)遺傳算法（Self-adjusting Search Domain GA，SAGA）。通過(guò)深入探索求解FJSP的理論和方法，期望能夠在實(shí)際生產(chǎn)環(huán)境中實(shí)現(xiàn)效率的提升，推動(dòng)智能優(yōu)化算法在生產(chǎn)調(diào)度領(lǐng)域的應(yīng)用，為實(shí)際生產(chǎn)過(guò)程中的資源配置和效率提升提供有力支持。

1 問(wèn)題描述

FJSP被定義為在具備多樣化機(jī)器集群和不同類型工件的車間中，確定最優(yōu)的工序順序以及每道工序的執(zhí)行機(jī)器的任務(wù)。具體數(shù)學(xué)模型描述為：一組相互獨(dú)立數(shù)量為n 的工件（J1，J2，…，Jn） ，這些工件需要在m臺(tái)不同的機(jī)器（M1，M2，…，Mm） 上進(jìn)行加工處理。對(duì)于每個(gè)工件Ji，由u 個(gè)加工工序（u=1，2，…，3） 組成。每個(gè)加工步驟都需要一定的時(shí)間來(lái)完成，時(shí)間大于0，且每個(gè)步驟都至少可以在一臺(tái)機(jī)器上完成。在任意給定的時(shí)刻，一臺(tái)機(jī)器只能處理一個(gè)加工步驟，不能同時(shí)處理多個(gè)任務(wù)。此外，一旦一個(gè)加工步驟開(kāi)始，必須直到完成加工，中間不能有中斷。同時(shí)，不考慮工件在不同機(jī)器之間的運(yùn)輸時(shí)間。該調(diào)度模型的核心目標(biāo)是實(shí)現(xiàn)所有加工步驟完成時(shí)間的最小化，可以通過(guò)以下的目標(biāo)函數(shù)來(lái)表達(dá)：

其中，Si，j，k表示工序Oij在機(jī)器k 上加工開(kāi)始時(shí)間。ti，j，k表示工序Oij在機(jī)器k 上所需加工時(shí)間。

2 算法設(shè)計(jì)

2.1 染色體表示

FJSP的關(guān)鍵在于處理兩個(gè)核心子問(wèn)題，即工序排列（Operation Sequence， OS） 和機(jī)器選擇（Machine Selec?tion， MS） [9]，采用雙層染色體表示法能夠較好地解決這兩個(gè)子問(wèn)題。以圖1為參考，在OS 部分中，首個(gè)數(shù)字“2”指代的是第二個(gè)作業(yè)的首個(gè)加工工序，標(biāo)記為O21。接下來(lái)的數(shù)字“1”則代表第一個(gè)工件的第一個(gè)操作，表示為O11。當(dāng)數(shù)字“2”再次出現(xiàn)時(shí)，它表示的是第二個(gè)作業(yè)的第二個(gè)步驟，記作O22。后續(xù)的數(shù)字遵循相同的編碼規(guī)則，且染色體的長(zhǎng)度與操作的總數(shù)相匹配。因此，操作序列“2-1-2-3-1”可以對(duì)應(yīng)地解讀操作序列：“ O21-O11-O22-O31-O12”。

與OS部分相似， MS部分的染色體長(zhǎng)度等同于全部操作的總數(shù)量。以圖1中的MS部分為例，若某個(gè)操作，如O22，對(duì)應(yīng)位置的數(shù)字是3，表示選用第三臺(tái)機(jī)器來(lái)執(zhí)行此操作。具體可用的機(jī)器數(shù)量取決于具體問(wèn)題的實(shí)際情況。因此在MS部分，每個(gè)數(shù)值都被特別設(shè)定為代表執(zhí)行當(dāng)前操作的機(jī)器編號(hào)。

2.2 種群初始化與進(jìn)化算子

種群初始化是GA的關(guān)鍵一環(huán)。當(dāng)前廣泛采用的初始化MS部分策略是張國(guó)輝等[10]提出的全局與局部選擇相結(jié)合的方法，本研究在MS部分也采用此策略。鑒于現(xiàn)有研究在OS部分的初始化方面缺乏完善方案，提出了一種優(yōu)先選取剩余操作最多的工件法（Pri?oritize Selection of Most Remaining Operations，PSMRO） 為染色體的OS部分進(jìn)行初始化：

（1） 設(shè)置一個(gè)記錄每個(gè)工件被選中次數(shù)的數(shù)組，并將所有元素預(yù)設(shè)為0。

（2） 構(gòu)建一個(gè)長(zhǎng)度為n 的數(shù)組，其中每個(gè)元素代表各工件的操作數(shù)。

（3） 在上述創(chuàng)建的數(shù)組中，挑選出剩余操作最多的工件。若存在多個(gè)工件剩余操作數(shù)相同，則隨機(jī)選取一個(gè)。

（4） 將所選工件的編號(hào)記錄到步驟1中創(chuàng)建的數(shù)組里，并相應(yīng)減少步驟2中數(shù)組對(duì)應(yīng)位置的操作數(shù)。

（5） 不斷重復(fù)步驟3和4，直至步驟2中數(shù)組的所有元素歸零。

GA核心在于通過(guò)個(gè)體選擇操作來(lái)模擬自然選擇過(guò)程。在選擇過(guò)程中，使用三元錦標(biāo)賽進(jìn)行選擇，旨在從種群中篩選出表現(xiàn)優(yōu)異的個(gè)體，并將其保留在基因庫(kù)中。在經(jīng)過(guò)一輪或多輪的繁衍后，這些優(yōu)秀的個(gè)體可以為后續(xù)的進(jìn)化過(guò)程提供高質(zhì)量的遺傳基因。

鑒于雙層染色體結(jié)構(gòu)特點(diǎn)，針對(duì)OS和MS部分分別實(shí)施了兩種不同的交叉操作策略。在OS部分，采用了改進(jìn)的優(yōu)先順序交叉（Improved Precedence OrderCrossover， IPOX） 方法。具體步驟為：首先，將作業(yè)集隨機(jī)劃分為J1和J2兩個(gè)子集，并隨機(jī)選擇兩條父代染色體P1和P2。接著，將P1中隸屬于J1集合中的基因以及P2中隸屬于J2集合的基因分別復(fù)制到子代個(gè)體C1和C2中，同時(shí)確保這些基因在C1和C2中的位置與原染色體保持一致。然后，依次從P1中復(fù)制屬于J1集合的基因到C2中的空缺位置，從P2中復(fù)制屬于J2集合的基因到C1的空缺位置，完成基因的交叉過(guò)程。如圖2。

MS部分由一系列代表加工機(jī)器的元素構(gòu)成，每個(gè)元素都對(duì)應(yīng)一個(gè)具體的操作。在MS部分進(jìn)行交叉操作時(shí)，涉及在染色體的兩個(gè)不同點(diǎn)交換基因，從而創(chuàng)造出兩個(gè)全新的MS序列。當(dāng)兩條染色體上的同一位置出現(xiàn)相同的數(shù)字時(shí)，這表明該位置的機(jī)器是可選機(jī)器集合中的一員。通過(guò)等位基因交叉產(chǎn)生的新染色體依然滿足原有的約束條件，因此交叉操作后得到的新個(gè)體仍然是有效的解決方案[11]。本研究采用的是兩點(diǎn)交叉法來(lái)進(jìn)行這一操作。

為了避免算法過(guò)快地陷入局部最優(yōu)解，需要引入變異操作。在染色體的OS部分，實(shí)行兩點(diǎn)變異操作。而當(dāng)MS部分發(fā)生變異時(shí)，從可用的機(jī)器集合中隨機(jī)選取一臺(tái)新的加工機(jī)器替換原有的機(jī)器，以增加種群的多樣性。

2.3 搜索域自調(diào)整策略

為了應(yīng)對(duì)算法早熟收斂現(xiàn)象，采取了一種新策略，當(dāng)算法檢測(cè)到種群陷入局部最優(yōu)時(shí)，初始化一小部分種群參與后續(xù)的進(jìn)化過(guò)程中。這一策略通過(guò)生成全新的染色體，并隨機(jī)替換除當(dāng)前最優(yōu)染色體外的相同數(shù)量的其他個(gè)體，以此來(lái)調(diào)整解空間的搜索范圍，進(jìn)而增強(qiáng)基因的多樣性。引入新種群的頻率根據(jù)當(dāng)前的進(jìn)化狀況進(jìn)行自適應(yīng)調(diào)整，在搜索速度和搜索精度之間找到一個(gè)更好的平衡點(diǎn)。通過(guò)這種自適應(yīng)機(jī)制，算法能夠隨著種群的進(jìn)化自動(dòng)調(diào)整其搜索范圍，從而更有效地探索整個(gè)解空間。圖3展示了染色體初始化的決策判定邏輯與操作步驟。

2.4 改進(jìn)GA 的框架

基于前述討論，構(gòu)建了如圖4所示的算法框架。

3 仿真實(shí)驗(yàn)及分析

本研究闡述的算法使用Matlab 2020a編寫(xiě)，實(shí)驗(yàn)環(huán)境為配置搭有Intel Core i5處理器、8GB內(nèi)存的Win?dows 10操作系統(tǒng)。為驗(yàn)證算法的有效性，選用了兩組廣受認(rèn)可的FJSP基準(zhǔn)測(cè)試數(shù)據(jù)。其中一組是規(guī)模相對(duì)較小的Kacem 數(shù)據(jù)集[12]，另一組是更為復(fù)雜的Brandimarte數(shù)據(jù)集[13]。對(duì)于每個(gè)測(cè)試實(shí)例，都進(jìn)行20 次的運(yùn)行試驗(yàn)。算法種群數(shù)設(shè)置為5*m*n（m， n為實(shí)例規(guī)模），最大的迭代次數(shù)設(shè)為10*m*n，交叉變異概率動(dòng)態(tài)自適應(yīng)，公式如下：

Pc =-Ft - minFt／ maxFt - minFt （2）

Pm = minFt ／maxFt （3）

其中，-Ft 為平均適應(yīng)度，minFt和maxFt分別為最小、最大適應(yīng)度。

本節(jié)將SAGA與SLGA[14]、edPSO[15]、GWO[16]三種算法進(jìn)行了比較，以評(píng)估SAGA的整體表現(xiàn)。表1展示了Kacem數(shù)據(jù)集上各算法的對(duì)比結(jié)果。由于未找到Kcaem05原始數(shù)據(jù)集，在剩余的四個(gè)實(shí)例中，SAGA在三個(gè)實(shí)例中都達(dá)到了問(wèn)題實(shí)例的下界（LB） 結(jié)果。這一數(shù)據(jù)表明，在處理較小規(guī)模的問(wèn)題時(shí)，SAGA算法擁有良好的性能和效果。

表2呈現(xiàn)了幾種算法在中等至大規(guī)模的10個(gè)BR 數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果。由表中數(shù)據(jù)可以看出，SAGA、edPSO和SLGA均取得了 5次最優(yōu)表現(xiàn)。盡管GWO 在Kacem數(shù)據(jù)集上表現(xiàn)出色，但在此次測(cè)試中，它僅在2個(gè)實(shí)例上達(dá)到最右。這些實(shí)驗(yàn)結(jié)果表明，SAGA 在處理大規(guī)模問(wèn)題時(shí)展現(xiàn)出更高的適應(yīng)性。

表3給出了按相對(duì)百分比偏差（RPDB） 衡量的比較結(jié)果。其計(jì)算式為：

根據(jù)表格數(shù)據(jù)，SAGA算法在MK01、03、04、08和MK10上找到最佳解。同時(shí)，在其余的三個(gè)實(shí)例中，按照RPDB的衡量標(biāo)準(zhǔn)，SAGA也取得了次優(yōu)的結(jié)果。

修正RPD （CRPD） 是通過(guò)對(duì)算法求解結(jié)果與最優(yōu)解或已知下界進(jìn)行比較，進(jìn)一步衡量算法性能的一種指標(biāo)。具體的計(jì)算方法是，先求出算法求解結(jié)果與最優(yōu)解（Best） 和下界的差值，再除以最優(yōu)解或下界，最后將得到的比值乘以100，以此表示算法求解結(jié)果與理論值的偏差程度。公式如下：

表4詳細(xì)展示了所有參與比較的算法的實(shí)際求解數(shù)（ASI） 以及每種算法的修正相對(duì)百分比偏差（CRPD） 。在該表中，“提升”這一列特指SAGA算法相較于兩組基準(zhǔn)測(cè)試中的其他算法，在CRPD方面所取得的減少值。

從數(shù)據(jù)中可以明顯看出，除了SLGA算法之外，SAGA 在CRPD 上均實(shí)現(xiàn)了不同程度的提升。盡管SAGA的CRPD相比SLGA只是略有優(yōu)勢(shì)，但這仍然顯示了SAGA在優(yōu)化FJSP的最大完工時(shí)間方面，表現(xiàn)出了更加卓越的性能和效率。

4 結(jié)論

為求解FJSP，提出了一種自調(diào)整搜索域的改進(jìn)遺傳算法（SAGA） 。采用雙層基因鏈染色體表示方法獨(dú)立地在操作序列和機(jī)器選擇上進(jìn)行遺傳操作。同時(shí)，為了提高搜索效率，將提出的PSMRO方法應(yīng)用于初始化操作順序部分。當(dāng)種群陷入局部最優(yōu)時(shí)，部分種群被重新初始化，自調(diào)整搜索域，以提高染色體的多樣性，豐富種群的基因庫(kù)。

最后在選定的基準(zhǔn)測(cè)試集上對(duì)SAGA進(jìn)行了測(cè)試。實(shí)驗(yàn)驗(yàn)證發(fā)現(xiàn)SAGA在處理FJSP時(shí)展現(xiàn)出了良好的性能。本研究不僅為FJSP的求解提供了新的有效方法，還為實(shí)際生產(chǎn)調(diào)度中的優(yōu)化問(wèn)題提供了有價(jià)值的參考。

參考文獻(xiàn)：

[1] 屠軍權(quán).智能制造時(shí)代機(jī)械設(shè)計(jì)制造及其自動(dòng)化技術(shù)研究[J].工程施工新技術(shù)，2022，1（2）：153-155.

[2] 魏巍，譚建榮，馮毅雄，等.柔性工作車間調(diào)度問(wèn)題的多目標(biāo)優(yōu)化方法研究[J]. 計(jì)算機(jī)集成制造系統(tǒng)，2009，15（8）：1592-1598.

[3] 余斌煌.柔性流水車間調(diào)度問(wèn)題綜述[J].現(xiàn)代制造工程，2022（9）：154-162，71.

[4] LONG X J，ZHANG J T，QI X，et al.A self-learning artificial bee colony algorithm based on reinforcement learning for a flexible job-shop scheduling problem[J].Concurrency and Computation：Practice and Experience，2022，34（4）：e6658.

[5] JIA Z H，CHEN H P，TANG J.An improved particle swarm opti?mization for multi-objective flexible job-shop scheduling prob?lem[C]//2007 IEEE International Conference on Grey Systems and Intelligent Services.November 18-20，2007，Nanjing，China.IEEE，2007：1587-1592.

[6] LI X Y，GAO L.An effective hybrid genetic algorithm and tabu search for flexible job shop scheduling problem[J].International Journal of Production Economics，2016，174：93-110.

[7] XING L N，CHEN Y W，WANG P，et al.A knowledge-based ant colony optimization for flexible job shop scheduling problems[J].Applied Soft Computing，2010，10（3）：888-896.

[8] ZHANG G H，SHAO X Y，LI P G，et al.An effective hybrid par?ticle swarm optimization algorithm for multi-objective flexible job-shop scheduling problem[J].Computers & Industrial Engi?neering，2009，56（4）：1309-1318.

[9] 姚遠(yuǎn)遠(yuǎn)，葉春明.求解作業(yè)車間調(diào)度問(wèn)題的改進(jìn)混合灰狼優(yōu)化算法[J].計(jì)算機(jī)應(yīng)用研究，2018，35（5）：1310-1314.

[10] ZHANG G H，GAO L，SHI Y.An effective genetic algorithm for the flexible job-shop scheduling problem[J].Expert Systems with Applications，2011，38（4）：3563-3573.

[11] 王佳怡，潘瑞林，秦飛.改進(jìn)遺傳算法求解柔性作業(yè)車間調(diào)度問(wèn)題[J].制造業(yè)自動(dòng)化，2022，44（12）：91-94，106.

[12] KACEM I，HAMMADI S，BORNE P.Approach by localization and multiobjective evolutionary optimization for flexible jobshop scheduling problems[J].IEEE Transactions on Systems，Man，and Cybernetics，Part C （Applications and Reviews），2002，32（1）：1-13.

[13] BRANDIMARTE P.Routing and scheduling in a flexible job shop by tabu search[J].Annals of Operations Research，1993，41（3）：157-183.

[14] CHEN R H，YANG B，LI S，et al.A self-learning genetic algo?rithm based on reinforcement learning for flexible job-shop scheduling problem[J]. Computers & Industrial Engineering，2020，149：106778.

[15] NOURI H E，BELKAHLA DRISS O，GHéDIRA K.Solving the flexible job shop problem by hybrid metaheuristics-based multiagent model[J].Journal of Industrial Engineering Interna?tional，2018，14（1）：1-14.

[16] JIANG T H，ZHANG C.Application of grey wolf optimization for solving combinatorial problems：job shop and flexible job shop scheduling cases[J].IEEE Access，2018，6：26231-26240.

【通聯(lián)編輯：梁書(shū)】

基金項(xiàng)目“：基于進(jìn)化算法求解柔性作業(yè)車間調(diào)度問(wèn)題的研究”（ 編號(hào)：KJYB2024011）