摘要：為優(yōu)化生產(chǎn)要素配置提高資源利用率，構(gòu)建了以最小化最大完工時間為目標(biāo)的調(diào)度模型，提出了一種自調(diào)整搜索域的改進(jìn)遺傳算法求解柔性作業(yè)車間調(diào)度問題（Flexible Job-shop Scheduling Problem， FJSP） 。算法采用基于工序排列和機(jī)器選擇的雙層染色體編碼的設(shè)計方案。設(shè)計了新的種群初始化方法，在交叉和變異階段，引入自適應(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)整搜索域；染色體多樣性

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

文章編號：1009-3044（2024）27-0079-04

0 引言

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

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

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

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

1 問題描述

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

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

2 算法設(shè)計

2.1 染色體表示

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

本研究闡述的算法使用Matlab 2020a編寫，實(shí)驗(yàn)環(huán)境為配置搭有Intel Core i5處理器、8GB內(nèi)存的Win?dows 10操作系統(tǒng)。為驗(yàn)證算法的有效性，選用了兩組廣受認(rèn)可的FJSP基準(zhǔn)測試數(shù)據(jù)。其中一組是規(guī)模相對較小的Kacem 數(shù)據(jù)集[12]，另一組是更為復(fù)雜的Brandimarte數(shù)據(jù)集[13]。對于每個測試實(shí)例，都進(jìn)行20 次的運(yùn)行試驗(yàn)。算法種群數(shù)設(shè)置為5*m*n（m， n為實(shí)例規(guī)模），最大的迭代次數(shù)設(shè)為10*m*n，交叉變異概率動態(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)行了比較，以評估SAGA的整體表現(xiàn)。表1展示了Kacem數(shù)據(jù)集上各算法的對比結(jié)果。由于未找到Kcaem05原始數(shù)據(jù)集，在剩余的四個實(shí)例中，SAGA在三個實(shí)例中都達(dá)到了問題實(shí)例的下界（LB） 結(jié)果。這一數(shù)據(jù)表明，在處理較小規(guī)模的問題時，SAGA算法擁有良好的性能和效果。

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

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

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

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

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

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

4 結(jié)論

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

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

參考文獻(xiàn)：

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

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

[3] 余斌煌.柔性流水車間調(diào)度問題綜述[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)度問題的改進(jìn)混合灰狼優(yōu)化算法[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)度問題[J].制造業(yè)自動化，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)編輯：梁書】

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