中圖分類號(hào)：TP301 文獻(xiàn)標(biāo)志碼：A

0 引言

車間作業(yè)調(diào)度（Job Shop SchedulingProblem，JSP）問(wèn)題是經(jīng)典的組合優(yōu)化問(wèn)題。調(diào)度問(wèn)題是在實(shí)際工作中廣泛應(yīng)用的運(yùn)籌學(xué)問(wèn)題，可以定義為“在一定的約束條件下，把有限的資源在時(shí)間上分配給若干個(gè)任務(wù)，以滿足或優(yōu)化一個(gè)或多個(gè)性能指標(biāo)”。在應(yīng)用層面，可以將調(diào)度和其他一些先進(jìn)概念相結(jié)合，比如智能制造、大數(shù)據(jù)、物聯(lián)網(wǎng)、數(shù)字孿生、云制造、多智能體系統(tǒng)、嵌入式技術(shù)、邊緣計(jì)算、工業(yè)4.0、物聯(lián)制造、網(wǎng)絡(luò)物理系統(tǒng)、區(qū)塊鏈、制造執(zhí)行系統(tǒng)等。

近年來(lái)，車間作業(yè)調(diào)度的研究方法偏向于智能優(yōu)化算法，目前研究較多的是基于群智能算法生成的調(diào)度方案，常見(jiàn)的群智能算法有蟻群算法、鯨魚(yú)優(yōu)化算法、灰狼優(yōu)化算法等。鯨魚(yú)優(yōu)化算法具有良好的通用性、魯棒性以及很好的泛化能力，極大地提高了計(jì)算的效率。

針對(duì)鯨魚(yú)優(yōu)化算法易陷入局部最優(yōu)的缺點(diǎn)，本文在鯨魚(yú)優(yōu)化算法的基礎(chǔ)上進(jìn)行了改進(jìn)，增加了變異擾動(dòng)操作，能跳出局部最優(yōu)，提高了調(diào)度方案的可行性。

1車間作業(yè)調(diào)度現(xiàn)狀

1.1 國(guó)內(nèi)研究現(xiàn)狀

閆旭等[]為了克服作業(yè)車間調(diào)度問(wèn)題存在收斂精度低、容易陷入局部最優(yōu)的缺陷，利用量子計(jì)算與優(yōu)化思想提出了一種量子鯨魚(yú)優(yōu)化算法并對(duì)其進(jìn)行了仿真實(shí)驗(yàn)。肖裕峰等2針對(duì)工業(yè)洗滌設(shè)備多品種、小批量的生產(chǎn)特點(diǎn)，以最大加工時(shí)間最小化為目標(biāo)，提出一種改進(jìn)的遺傳算法。王朋朋[3對(duì)深度強(qiáng)化學(xué)習(xí)在作業(yè)車間調(diào)度問(wèn)題上的應(yīng)用展開(kāi)研究，提出了基于完工時(shí)間注意力機(jī)制的異質(zhì)動(dòng)態(tài)圖神經(jīng)網(wǎng)絡(luò)和基于超網(wǎng)絡(luò)的多目標(biāo)Q學(xué)習(xí)算法分別解決單目標(biāo)和多目標(biāo)作業(yè)車間調(diào)度問(wèn)題，實(shí)驗(yàn)結(jié)果表明所提出的方法具有效性和優(yōu)越性。

1.2 國(guó)外研究現(xiàn)狀

Samsuria等[4]使用柔性制造系統(tǒng)中具有最短持續(xù)時(shí)間的移動(dòng)機(jī)器人為調(diào)度生成最佳方案。Momenikorbekandi等[5]回顧了基于AI的智能系統(tǒng)算法在制造業(yè)中的工業(yè)應(yīng)用，強(qiáng)調(diào)了最新的技術(shù)，對(duì)其在該領(lǐng)域的實(shí)際應(yīng)用進(jìn)行了系統(tǒng)和結(jié)構(gòu)化的評(píng)估。Usman等[介紹了具有人體工程學(xué)考慮的靈活作業(yè)車間調(diào)度問(wèn)題的創(chuàng)新類比，以安排船舶系統(tǒng)中的維護(hù)活動(dòng)，解決優(yōu)化生產(chǎn)力和促進(jìn)人體工程學(xué)緩解的雙重目標(biāo)。實(shí)驗(yàn)結(jié)果表明，改進(jìn)后的算法提供了更好的解決方案。

2車間作業(yè)調(diào)度研究方法及問(wèn)題

2.1精確法

2.1.1分支定界法

分支定界法是一種常用的求解整數(shù)規(guī)劃問(wèn)題的算法，被廣泛應(yīng)用于求解純整數(shù)規(guī)劃和混合整數(shù)規(guī)劃等問(wèn)題。分支：在解空間中分割子集。定界：劃分上下界后排除非目標(biāo)區(qū)域并縮小目標(biāo)范圍，能達(dá)到最優(yōu)解，平均速度在小規(guī)模問(wèn)題上較快，需要內(nèi)存空間存儲(chǔ)分支的上下界界限值和對(duì)應(yīng)矩陣，在定界不好的情況下和窮舉搜索沒(méi)有區(qū)別。定界是關(guān)鍵，上下界如果范圍不合理則和窮舉法的效率一樣低。

2.1.2拉格朗日松弛法

拉格朗日松弛法對(duì)已經(jīng)定義好的函數(shù)問(wèn)題搜索最優(yōu)解，把有約束條件的問(wèn)題變?yōu)闊o(wú)約束條件的數(shù)學(xué)方法，在定義函數(shù)中加人線性概念。函數(shù)的最優(yōu)解和拉格朗日函數(shù)最優(yōu)乘子解相同。

2.1. 3 動(dòng)態(tài)規(guī)劃

動(dòng)態(tài)規(guī)劃原理是將大規(guī)模問(wèn)題劃分為多個(gè)相同的小規(guī)模問(wèn)題，定義數(shù)據(jù)結(jié)構(gòu)存放每個(gè)小規(guī)模問(wèn)題的解，防止多次計(jì)算相同問(wèn)題，實(shí)現(xiàn)原理簡(jiǎn)單，但對(duì)計(jì)算機(jī)性能要求較高，很少用于實(shí)際解決問(wèn)題，是解決問(wèn)題的一種思路。

2.2 近似法

2.2.1 進(jìn)化算法

進(jìn)化算法是從生物進(jìn)化過(guò)程中發(fā)展學(xué)習(xí)演化而來(lái)，通過(guò)獨(dú)立個(gè)體的初始化、競(jìng)爭(zhēng)和信息傳輸?shù)玫礁鼉?yōu)的群體。算法的底層邏輯是搜索最優(yōu)解，主要以遺傳算法、協(xié)同進(jìn)化算法、差分算法的研究為主。

遺傳算法的原理為：算子高的選中概率高，但算子排名較后的也會(huì)被選中，在此基礎(chǔ)上進(jìn)化為更優(yōu)的種群，被選中的獨(dú)立個(gè)體如果進(jìn)行交叉操作則更新原有個(gè)體，不變異則保持原個(gè)體。變異操作類似，經(jīng)過(guò)初始化、交叉和變異后，每代的種群算子都會(huì)進(jìn)化，在設(shè)置遺傳算法參數(shù)時(shí)，確定進(jìn)化次數(shù)，計(jì)算資源耗盡和算子飽和后就不再進(jìn)化，找到了全局最優(yōu)解。

2.2.2群智能算法

群智能算法包括粒子群算法和蟻群算法。粒子群算法把鳥(niǎo)群中的鳥(niǎo)設(shè)計(jì)為隨機(jī)粒子，具有速度和位置2個(gè)屬性，在解空間中移動(dòng)搜索最優(yōu)解，記為本粒子極值并共享信息給種群中其他粒子。比較得到最優(yōu)的粒子極值即為全局最優(yōu)解，所有粒子更新速度和位置。

蟻群算法基于對(duì)自然界真實(shí)蟻群集體覓食行為的研究模擬真實(shí)的蟻群協(xié)作過(guò)程。算法由若干個(gè)螞蟻共同構(gòu)造解路徑，通過(guò)在解路徑上遺留并交換信息素的方法反饋信息，提高解的質(zhì)量，進(jìn)而找到最短路徑，達(dá)到優(yōu)化目的。

2.2.3智能搜索算法

智能搜索算法包括模擬退火算法、禁忌搜索算法、變鄰域搜索算法等。

模擬退火算法由解空間、目標(biāo)函數(shù)、初始解和溫度參數(shù)初值組成，核心步驟是判斷解空間中的新解是否符合條件。模擬退火算法在組合優(yōu)化問(wèn)題和調(diào)度領(lǐng)域能取得令人滿意的最優(yōu)解。

禁忌搜索算法中禁忌搜索不是采用所有局部最優(yōu)解，而是避開(kāi)一部分以此獲得更多的搜索空間。禁忌表中記錄搜索到的局部最優(yōu)解，在一定時(shí)間后重新進(jìn)入搜索隊(duì)列，防止循環(huán)記錄重復(fù)解。在搜索過(guò)程中禁忌長(zhǎng)度的選取是算法是否高效的關(guān)鍵，后續(xù)搜索時(shí)找不到比禁忌表中更優(yōu)的解則考慮最好的劣解。

2.3存在問(wèn)題

對(duì)于車間作業(yè)調(diào)度而言，使用智能優(yōu)化算法為大勢(shì)所趨，但智能優(yōu)化算法屬于近似法，易陷入局部最優(yōu)。近似法能在初始化參數(shù)后進(jìn)行種群或者生物進(jìn)化增加種群質(zhì)量，在搜索過(guò)程中會(huì)在局部進(jìn)行最優(yōu)值的查找，在無(wú)干預(yù)的情況下，找出的值為局部最優(yōu)值，這樣不能實(shí)現(xiàn)使用智能優(yōu)化算法的目標(biāo)，因此，要增加一定的變異擾動(dòng)才能在搜索過(guò)程中找到一個(gè)局部最優(yōu)值時(shí)跳出搜索區(qū)域并在其他區(qū)域找到局部最優(yōu)值進(jìn)行比較，確定最優(yōu)值。變異擾動(dòng)是當(dāng)前解決陷入局部最優(yōu)較好的方法之一。

綜上所述，解決JSP問(wèn)題的方法由精確法重心逐漸移到近似法?；窘品ú贿m用于實(shí)際情況，往往會(huì)混合或者增加操作。針對(duì)實(shí)際問(wèn)題，本文提出不同的改進(jìn)方法進(jìn)行解決，具有一定的實(shí)用價(jià)值。

3鯨魚(yú)優(yōu)化算法及其流程

鯨魚(yú)優(yōu)化算法（WhaleOptimizationAlgorithm，WOA）是2016年SeyedaliMirjalili教授帶領(lǐng)團(tuán)隊(duì)提出的一種元啟發(fā)式優(yōu)化算法，模擬了座頭鯨的社會(huì)行為。算法的核心是氣泡網(wǎng)狩獵策略，通過(guò)在一個(gè)圈內(nèi)制造獨(dú)特的氣泡螺旋來(lái)完成覓食。

3.1 包圍獵物

WOA假設(shè)當(dāng)前最佳候選方案是目標(biāo)或接近目標(biāo)最佳，數(shù)學(xué)模型為：

其中， Φ_t 為當(dāng)前迭代， X* 是最佳位置向量， X 為當(dāng)前位置向量，A和 c 是系數(shù)向量， γ 為[0，1]中的隨機(jī)向量， α 從2開(kāi)始遞減，最小值為 0 。

3.2 螺旋更新

座頭鯨在獵物周圍游泳同時(shí)沿著螺旋形路徑收縮，對(duì)此行為進(jìn)行建模，在收縮和環(huán)繞之間做出選擇的概率是 50% ，數(shù)學(xué)模型為：

其中， b 是常數(shù) ?，l 為[-1，1]之間的隨機(jī)數(shù)。

3.3尋找獵物

對(duì)包圍圈進(jìn)行隨機(jī)搜索，數(shù)學(xué)模型為：

其中， 為個(gè)體中選擇的隨機(jī)位置向量，WOA機(jī)制當(dāng) 時(shí)，隨機(jī)選擇并向遠(yuǎn)處搜尋，進(jìn)行全局最優(yōu)解探索。

4改進(jìn)方法及實(shí)驗(yàn)

4.1改進(jìn)方法

目前WOA仍存在易陷入局部最優(yōu)的問(wèn)題，迭代到后期時(shí)就是在進(jìn)行局部搜索，如果在此前基礎(chǔ)上包圍獵物操作時(shí)偏離了最優(yōu)解，在局部搜索都是無(wú)效的。為了確保在后期尋找最優(yōu)解時(shí)可以跳出一次當(dāng)前搜索范圍，可以將第一步操作的位置跳轉(zhuǎn)到離當(dāng)前位置相對(duì)較遠(yuǎn)的新范圍，來(lái)檢查是否有更優(yōu)解，達(dá)到全局搜索的效果，這是變異擾動(dòng)的改進(jìn)原理[]。本文選取的改進(jìn)方法為柯西變異?？挛鞣植己瘮?shù)[8如下：

柯西變異對(duì)個(gè)體的變異用公式表示為：

其中， C（0，1） 是代替原最佳位置向量的服從柯西分布的隨機(jī)數(shù)， η 是常數(shù)。

增加了柯西變異后，最佳位置向量和上一步相比有較大的差異，變異范圍廣，由于柯西分布函數(shù)步長(zhǎng)更長(zhǎng)，兩端分布較長(zhǎng)也能讓變異擾動(dòng)過(guò)程中跳出局部最優(yōu)。改進(jìn)后的算法記為CWOA，算法流程如表1所示。

表1CWOA算法流程

4.2算法實(shí)驗(yàn)

實(shí)驗(yàn)將多元宇宙優(yōu)化算法（Multi-VerseOptimizer，MVO）、飛蛾火焰優(yōu)化算法（Moth-FlameOptimization，MFO）、連續(xù)凸近似算法（SuccessiveConvexApproximation，SCA）和CWOA進(jìn)行最優(yōu)值的對(duì)比分析，最大迭代次數(shù)60，基準(zhǔn)測(cè)試函數(shù)維度為30，變量數(shù)4，上下界為（-100，100），比較算法在其他測(cè)試函數(shù)上的收斂性，算法最優(yōu)值如表2所示，測(cè)試函數(shù)收斂性能如圖1所示。

表2算法最優(yōu)值

從實(shí)驗(yàn)結(jié)果中可以看出，CWOA得到的結(jié)果更加接近函數(shù)理論值，需要較少的迭代次數(shù)就可以達(dá)到全局最小，在收斂速度和算法最優(yōu)值上優(yōu)于MVO、MFO、SCA，證明改進(jìn)后的算法可以解決局部最優(yōu)問(wèn)題。

4.3甘特圖實(shí)驗(yàn)

對(duì)于CWOA求解經(jīng)典JSP問(wèn)題，通過(guò)甘特圖來(lái)進(jìn)行測(cè)試，表3為部分?jǐn)?shù)據(jù)，調(diào)度甘特圖如圖2所示。

圖1測(cè)試函數(shù)收斂

表3數(shù)據(jù)（部分）

在調(diào)度甘特圖中，不同機(jī)器編號(hào)的前2個(gè)任務(wù)是數(shù)據(jù)表的實(shí)現(xiàn)，說(shuō)明CWOA的柯西變異可以跳出局部，找到最優(yōu)解。

5結(jié)語(yǔ)

本研究針對(duì)鯨魚(yú)優(yōu)算法在求解作業(yè)調(diào)度問(wèn)題中易陷人局部最優(yōu)的問(wèn)題，提出了改進(jìn)算法并用實(shí)驗(yàn)仿真和調(diào)度方案驗(yàn)證，通過(guò)增加變異擾動(dòng)達(dá)到跳出最優(yōu)的目的。研究結(jié)果表明，本算法可以在實(shí)際問(wèn)題中找到最優(yōu)調(diào)度甘特圖，為現(xiàn)代作業(yè)調(diào)度問(wèn)題目標(biāo)解決提供了研究思路。

圖2調(diào)度甘特圖

參考文獻(xiàn)

[1]閆旭，葉春明，姚遠(yuǎn)遠(yuǎn).量子鯨魚(yú)優(yōu)化算法求解作業(yè)車間調(diào)度問(wèn)題[J].計(jì)算機(jī)應(yīng)用研究，2019（4）：975-979.

[2]肖裕峰，唐文獻(xiàn)，李欽奉.基于改進(jìn)遺傳算法的工業(yè)洗滌設(shè)備操作生產(chǎn)調(diào)度研究[J].機(jī)械設(shè)計(jì)與制造工程，2025（3）：122-127.

[3]王朋朋.基于深度強(qiáng)化學(xué)習(xí)的作業(yè)車間調(diào)度問(wèn)題 研究及應(yīng)用[D].成都：四川大學(xué)，2023.

[4]SAMSURIAE，MAHMUDMSA，WAHABNA. Animproved adaptive fuzzy-genetic algorithm based on local search for integrated production and mobile robot scheduling in job-shop flexible manufacturing system [J].Computersamp;Industrial Engineering，2025， 204：111093.

[5]MOMENIKORBEKANDI A， KALGANOVA T. Intelligent scheduling methods for optimization of job shop scheduling problems in the manufacturing sector： a systematic review[J]. Electronics，2025（8） ：1663.

[6]USMAN S，LU C. Ergonomic conscious scheduling of maintenance activities in marine vehiclesusingan optimized non-dominated sorting genetic algorithm-II-An application of job-shop scheduling[J].Engineering ApplicationsofArtificialIntelligence，2025，149：110491.

[7]李汶娟.阿奎拉鷹優(yōu)化算法的改進(jìn)及在碳排放預(yù) 測(cè)上的應(yīng)用[D]．蘭州：甘肅農(nóng)業(yè)大學(xué)，2024.

[8]李靜，黃明，李志峰.基于柯西-高斯分布ACODWA導(dǎo)盲路徑優(yōu)化[J].自動(dòng)化與儀表，2025（3）： 48-53.

（編輯 王雪芬）

Research on workshop job scheduling based on the improved whale optimization algorithm

WEI Xin （Xi’an Innovation College Yan’ an University，Xi'an 71O1Oo，China）

Abstract：Workshop job scheduling isone of the hot isues insocial research，whichcan be solved byapproximation methodandexact method，this paper selects thewhaleoptimizationalgorithmof swarm intellgence algorithmin the approximation method，and thewhaleoptimizationalgorithm has limitations inthe solution，inorder to improve this problem，itis proposed toadd Cauchyvariation to the whaleoptimization algorithm，andthecharacteristicsof Cauchy distribution functionatboth endscan jumpoutof thelocaloptimal inthe mutation perturbation.The CauchymutationWhale Optimization Algorithm （CWOA）algorithm proposed in this paper has been improved in convergence speed and algorithm accuracy after experimental verification，which can effectively improve the problem of job scheduling falling into local optimum，and use Gant charttoobtaintheoptimal actual scheduling.It provides aresearch idea forthe goal solving of modern job scheduling problems

Key words： job scheduling problems; whale optimization algorithm; Cauchy mutation