基于改進鯨魚優化算法的車間作業調度問題研究

中圖分類號：TP301 文獻標志碼：A

0 引言

車間作業調度（Job Shop SchedulingProblem，JSP）問題是經典的組合優化問題。調度問題是在實際工作中廣泛應用的運籌學問題，可以定義為“在一定的約束條件下，把有限的資源在時間上分配給若干個任務，以滿足或優化一個或多個性能指標”。在應用層面，可以將調度和其他一些先進概念相結合，比如智能制造、大數據、物聯網、數字孿生、云制造、多智能體系統、嵌入式技術、邊緣計算、工業4.0、物聯制造、網絡物理系統、區塊鏈、制造執行系統等。

近年來，車間作業調度的研究方法偏向于智能優化算法，目前研究較多的是基于群智能算法生成的調度方案，常見的群智能算法有蟻群算法、鯨魚優化算法、灰狼優化算法等。鯨魚優化算法具有良好的通用性、魯棒性以及很好的泛化能力，極大地提高了計算的效率。

針對鯨魚優化算法易陷入局部最優的缺點，本文在鯨魚優化算法的基礎上進行了改進，增加了變異擾動操作，能跳出局部最優，提高了調度方案的可行性。

1車間作業調度現狀

1.1 國內研究現狀

閆旭等[]為了克服作業車間調度問題存在收斂精度低、容易陷入局部最優的缺陷，利用量子計算與優化思想提出了一種量子鯨魚優化算法并對其進行了仿真實驗。肖裕峰等2針對工業洗滌設備多品種、小批量的生產特點，以最大加工時間最小化為目標，提出一種改進的遺傳算法。王朋朋[3對深度強化學習在作業車間調度問題上的應用展開研究，提出了基于完工時間注意力機制的異質動態圖神經網絡和基于超網絡的多目標Q學習算法分別解決單目標和多目標作業車間調度問題，實驗結果表明所提出的方法具有效性和優越性。

1.2 國外研究現狀

Samsuria等[4]使用柔性制造系統中具有最短持續時間的移動機器人為調度生成最佳方案。Momenikorbekandi等[5]回顧了基于AI的智能系統算法在制造業中的工業應用，強調了最新的技術，對其在該領域的實際應用進行了系統和結構化的評估。Usman等[介紹了具有人體工程學考慮的靈活作業車間調度問題的創新類比，以安排船舶系統中的維護活動，解決優化生產力和促進人體工程學緩解的雙重目標。實驗結果表明，改進后的算法提供了更好的解決方案。

2車間作業調度研究方法及問題

2.1精確法

2.1.1分支定界法

分支定界法是一種常用的求解整數規劃問題的算法，被廣泛應用于求解純整數規劃和混合整數規劃等問題。分支：在解空間中分割子集。定界：劃分上下界后排除非目標區域并縮小目標范圍，能達到最優解，平均速度在小規模問題上較快，需要內存空間存儲分支的上下界界限值和對應矩陣，在定界不好的情況下和窮舉搜索沒有區別。定界是關鍵，上下界如果范圍不合理則和窮舉法的效率一樣低。

2.1.2拉格朗日松弛法

拉格朗日松弛法對已經定義好的函數問題搜索最優解，把有約束條件的問題變為無約束條件的數學方法，在定義函數中加人線性概念。函數的最優解和拉格朗日函數最優乘子解相同。

2.1. 3 動態規劃

動態規劃原理是將大規模問題劃分為多個相同的小規模問題，定義數據結構存放每個小規模問題的解，防止多次計算相同問題，實現原理簡單，但對計算機性能要求較高，很少用于實際解決問題，是解決問題的一種思路。

2.2 近似法

2.2.1 進化算法

進化算法是從生物進化過程中發展學習演化而來，通過獨立個體的初始化、競爭和信息傳輸得到更優的群體。算法的底層邏輯是搜索最優解，主要以遺傳算法、協同進化算法、差分算法的研究為主。

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

2.2.2群智能算法

群智能算法包括粒子群算法和蟻群算法。粒子群算法把鳥群中的鳥設計為隨機粒子，具有速度和位置2個屬性，在解空間中移動搜索最優解，記為本粒子極值并共享信息給種群中其他粒子。比較得到最優的粒子極值即為全局最優解，所有粒子更新速度和位置。

蟻群算法基于對自然界真實蟻群集體覓食行為的研究模擬真實的蟻群協作過程。算法由若干個螞蟻共同構造解路徑，通過在解路徑上遺留并交換信息素的方法反饋信息，提高解的質量，進而找到最短路徑，達到優化目的。

2.2.3智能搜索算法

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

模擬退火算法由解空間、目標函數、初始解和溫度參數初值組成，核心步驟是判斷解空間中的新解是否符合條件。模擬退火算法在組合優化問題和調度領域能取得令人滿意的最優解。

禁忌搜索算法中禁忌搜索不是采用所有局部最優解，而是避開一部分以此獲得更多的搜索空間。禁忌表中記錄搜索到的局部最優解，在一定時間后重新進入搜索隊列，防止循環記錄重復解。在搜索過程中禁忌長度的選取是算法是否高效的關鍵，后續搜索時找不到比禁忌表中更優的解則考慮最好的劣解。

2.3存在問題

對于車間作業調度而言，使用智能優化算法為大勢所趨，但智能優化算法屬于近似法，易陷入局部最優。近似法能在初始化參數后進行種群或者生物進化增加種群質量，在搜索過程中會在局部進行最優值的查找，在無干預的情況下，找出的值為局部最優值，這樣不能實現使用智能優化算法的目標，因此，要增加一定的變異擾動才能在搜索過程中找到一個局部最優值時跳出搜索區域并在其他區域找到局部最優值進行比較，確定最優值。變異擾動是當前解決陷入局部最優較好的方法之一。

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

3鯨魚優化算法及其流程

鯨魚優化算法（WhaleOptimizationAlgorithm，WOA）是2016年SeyedaliMirjalili教授帶領團隊提出的一種元啟發式優化算法，模擬了座頭鯨的社會行為。算法的核心是氣泡網狩獵策略，通過在一個圈內制造獨特的氣泡螺旋來完成覓食。

3.1 包圍獵物

WOA假設當前最佳候選方案是目標或接近目標最佳，數學模型為：

其中， Φ_t 為當前迭代， X* 是最佳位置向量， X 為當前位置向量，A和 c 是系數向量， γ 為[0，1]中的隨機向量， α 從2開始遞減，最小值為 0 。

3.2 螺旋更新

座頭鯨在獵物周圍游泳同時沿著螺旋形路徑收縮，對此行為進行建模，在收縮和環繞之間做出選擇的概率是 50% ，數學模型為：

其中， b 是常數 ?，l 為[-1，1]之間的隨機數。

3.3尋找獵物

對包圍圈進行隨機搜索，數學模型為：

其中， 為個體中選擇的隨機位置向量，WOA機制當 時，隨機選擇并向遠處搜尋，進行全局最優解探索。

4改進方法及實驗

4.1改進方法

目前WOA仍存在易陷入局部最優的問題，迭代到后期時就是在進行局部搜索，如果在此前基礎上包圍獵物操作時偏離了最優解，在局部搜索都是無效的。為了確保在后期尋找最優解時可以跳出一次當前搜索范圍，可以將第一步操作的位置跳轉到離當前位置相對較遠的新范圍，來檢查是否有更優解，達到全局搜索的效果，這是變異擾動的改進原理[]。本文選取的改進方法為柯西變異。柯西分布函數[8如下：

柯西變異對個體的變異用公式表示為：

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

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

表1CWOA算法流程

4.2算法實驗

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

表2算法最優值

從實驗結果中可以看出，CWOA得到的結果更加接近函數理論值，需要較少的迭代次數就可以達到全局最小，在收斂速度和算法最優值上優于MVO、MFO、SCA，證明改進后的算法可以解決局部最優問題。

4.3甘特圖實驗

對于CWOA求解經典JSP問題，通過甘特圖來進行測試，表3為部分數據，調度甘特圖如圖2所示。

圖1測試函數收斂

表3數據（部分）

在調度甘特圖中，不同機器編號的前2個任務是數據表的實現，說明CWOA的柯西變異可以跳出局部，找到最優解。

5結語

本研究針對鯨魚優算法在求解作業調度問題中易陷人局部最優的問題，提出了改進算法并用實驗仿真和調度方案驗證，通過增加變異擾動達到跳出最優的目的。研究結果表明，本算法可以在實際問題中找到最優調度甘特圖，為現代作業調度問題目標解決提供了研究思路。

圖2調度甘特圖

參考文獻

[1]閆旭，葉春明，姚遠遠.量子鯨魚優化算法求解作業車間調度問題[J].計算機應用研究，2019（4）：975-979.

[2]肖裕峰，唐文獻，李欽奉.基于改進遺傳算法的工業洗滌設備操作生產調度研究[J].機械設計與制造工程，2025（3）：122-127.

[3]王朋朋.基于深度強化學習的作業車間調度問題 研究及應用[D].成都：四川大學，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]李汶娟.阿奎拉鷹優化算法的改進及在碳排放預 測上的應用[D]．蘭州：甘肅農業大學，2024.

[8]李靜，黃明，李志峰.基于柯西-高斯分布ACODWA導盲路徑優化[J].自動化與儀表，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