摘 要：針對(duì)多目標(biāo)柔性作業(yè)車間調(diào)度問題，構(gòu)建了以最小化總能耗、最小化生產(chǎn)成本及最小化懲罰值為優(yōu)化目標(biāo)的數(shù)學(xué)模型，并設(shè)計(jì)改進(jìn)的多目標(biāo)樽海鞘群算法（IMSSA）進(jìn)行求解。改進(jìn)算法主要由樽海鞘領(lǐng)導(dǎo)者和樽海鞘追隨者兩部分構(gòu)成，其中，領(lǐng)導(dǎo)者位置更新結(jié)合正余弦算法來實(shí)現(xiàn)，追隨者位置更新基于線性微分遞減的慣性權(quán)重方法來完成。此外，引入食物源存儲(chǔ)庫(kù)用于保留非支配解。最后通過對(duì)比實(shí)驗(yàn)證明了所提策略及改進(jìn)算法的有效性。

關(guān)鍵詞：柔性作業(yè)車間調(diào)度問題；多目標(biāo)優(yōu)化；樽海鞘群算法

中圖分類號(hào)：TP278;TP391 " 文獻(xiàn)標(biāo)識(shí)碼：A " 文章編號(hào)：1671-9247（2024）03-0017-07

Research on Multi-objective Flexible Job Shop Scheduling ProblemBased on Improved Salp Swarm Algorithm

ZHANG Hongliang1，CAO Hengwan2

（1."School"of"Management"Science"and"Engineering，"AHUT，"Ma’anshan"243032，"Anhui；2."School"of"Mechanical，"Electronic"andControl"Engineering，"Beijing"Jiaotong"University，"Beijing"100044，China）

Abstract：For"the"multi-objective"flexible"job"shop"scheduling"problem，"a"mathematical"model"with"the"optimization"objectivesof"minimizing"total"energy"consumption，"minimizing"productionnbsp;cost，"and"minimizing"penalty"value"is"constructed，"and"an"im-proved"Multi-objective"Salp"Swarm"Algorithm"（IMSSA）"is"designed"to"solve"the"problem."The"improved"algorithm"mainly"consistsof"two"parts："leaders"and"followers，"where"the"leader’s"position"update"is"implemented"in"combination"with"the"sine"cosine"algo-rithm"and"the"follower’s"position"update"is"done"based"on"the"linear"differential"decreasing"inertia"weight"method."In"addition，"thefood"source"repository"is"introduced"to"retain"the"non-dominated"solutions."Finally，"the"comparative"experiments"proved"the"effec-tiveness"of"the"proposed"strategy"and"the"improved"algorithm.

Key words：flexible job shop scheduling problem；multi-objective optimization；salp swarm algorithm

制造業(yè)是國(guó)民經(jīng)濟(jì)重要組成部分之一，發(fā)展制造業(yè)對(duì)于提升國(guó)民經(jīng)濟(jì)有著舉足輕重的影響。2022年制造業(yè)增加值達(dá)33.5萬億元，占我國(guó)GDP比重的27.7%。為加快推進(jìn)制造業(yè)高質(zhì)量發(fā)展、推動(dòng)中國(guó)制造向中國(guó)創(chuàng)造轉(zhuǎn)變，黨的二十大報(bào)告提出，要把發(fā)展經(jīng)濟(jì)的著力點(diǎn)放在實(shí)體經(jīng)濟(jì)上，推進(jìn)新型工業(yè)化，加快建設(shè)制造強(qiáng)國(guó)。在此背景下，制造業(yè)高端化、智能化、綠色化發(fā)展成為制造企業(yè)的發(fā)展重點(diǎn)。與此同時(shí)，伴隨著經(jīng)濟(jì)快速發(fā)展、市場(chǎng)競(jìng)爭(zhēng)激烈，制造企業(yè)生產(chǎn)模式逐漸向定制化方向發(fā)展，而生產(chǎn)調(diào)度是制造系統(tǒng)的重要環(huán)節(jié)，高效的生產(chǎn)調(diào)度方法能促進(jìn)企業(yè)實(shí)現(xiàn)提質(zhì)增效及節(jié)能降耗。

柔性作業(yè)車間調(diào)度問題（Flexible"Job"Shop"Schedul-ing"Problem，"FJSP）主要包含工件選擇柔性、工序柔性及機(jī)器選擇柔性。柔性作業(yè)車間生產(chǎn)模式可以更好地滿足以多品種、小批量為特征的市場(chǎng)需求。目前，學(xué)者們對(duì)FJSP問題采用不同的方法進(jìn)行了研究，并取得了豐富的成果。楊艷華等[1]為提高FJSP的求解優(yōu)化應(yīng)的交叉熵改進(jìn)算法，獲得了問題的有效解及良好的算法收斂速度。李睿祺等[2]針對(duì)單一優(yōu)化方法在大算例中搜索能力下降的問題，設(shè)計(jì)了一種學(xué)習(xí)型協(xié)同進(jìn)化算法，實(shí)驗(yàn)驗(yàn)證改進(jìn)的算法具有良好的全局和局部搜索能力。Saqlain等[3]為解決FJSP中各種作業(yè)的順序操作問題，提出了一種基于蒙特卡洛樹搜索的柔性作業(yè)車間調(diào)度算法，實(shí)驗(yàn)表明該算法具有較好的評(píng)價(jià)性能。上述研究大多是基于單一目標(biāo)展開的，而在實(shí)際生產(chǎn)中，生產(chǎn)計(jì)劃者往往要綜合考慮多個(gè)目標(biāo)。因此，生產(chǎn)中的柔性多目標(biāo)調(diào)度問題已逐漸成為一個(gè)熱門的研究課題。

多目標(biāo)柔性作業(yè)車間調(diào)度問題（Multi-objectiveFlexible"Job"Shop"Scheduling"Problem，"MOFJSP）是將多個(gè)目標(biāo)作為柔性作業(yè)車間調(diào)度問題的對(duì)象，與單目標(biāo)柔性作業(yè)車間調(diào)度相比，它的情況更加復(fù)雜，優(yōu)化結(jié)果往往不具唯一性。目前學(xué)者們?cè)谇蠼釳OFJSP時(shí)多采用加權(quán)聚合法和Pareto優(yōu)化法[4]獲得最優(yōu)解集，再?gòu)钠渲羞x擇最滿意的調(diào)度方案。王秋蓮等[5]通過引入基于Pareto支配和參考點(diǎn)的選擇算子設(shè)計(jì)改進(jìn)了多目標(biāo)候鳥優(yōu)化算法，并對(duì)于求得的解集采用屬性層次模型和灰色關(guān)聯(lián)度分析法組合的方式獲取決策權(quán)重。朱光宇等[6]針對(duì)一個(gè)品種多、批量小、能耗高的生產(chǎn)車間，提出了基于直覺模糊集相似性的遺傳算法方案，在帕累托最優(yōu)解集中，直覺模糊的相似度值最高的方案被選為最滿意的方案。

此外，隨著環(huán)境污染及能源消耗問題日益突出，研究人員在研究車間調(diào)度問題時(shí)也將能耗作為重要影響因素。張洪亮等[7]在FJSP問題中考慮了工件運(yùn)輸時(shí)間和機(jī)器預(yù)維護(hù)，建立了總能耗和時(shí)間的混合整數(shù)規(guī)劃模型，并提出一種多目標(biāo)離散Jaya算法。姜一嘯等[8]建立了一個(gè)針對(duì)碳排放量、完工周期及生產(chǎn)成本的低碳調(diào)度模型，并以改進(jìn)的非支配遺傳算法進(jìn)行求解。Mokhtari等[9]開發(fā)的用于柔性作業(yè)車間調(diào)度的優(yōu)化模型，以能源成本、最大完成時(shí)間和整體系統(tǒng)可用性為目標(biāo)函數(shù)。Dai等[10]考慮到能源消耗和相關(guān)的環(huán)境問題，提出了以能耗和工期最小化為目標(biāo)的柔性作業(yè)車間調(diào)度模型。從以上研究可以看出，學(xué)者們以不同優(yōu)化目標(biāo)組合對(duì)柔性作業(yè)車間調(diào)度問題進(jìn)行了研究，且能耗越來越受到關(guān)注。

本文在研究柔性作業(yè)車間調(diào)度問題時(shí)，以能耗、生產(chǎn)成本和懲罰值作為主要優(yōu)化目標(biāo)，提出一種改進(jìn)的多目標(biāo)樽海鞘群算法（Improved"Multi-objective"SalpSwarm"Algorithm，IMSSA）求解，包括染色體編碼與解碼、食物源存儲(chǔ)庫(kù)的引入、基于正余弦算法的樽海鞘領(lǐng)導(dǎo)者位置更新、基于慣性權(quán)重方法的樽海鞘追隨者位置更新等，并通過對(duì)比實(shí)驗(yàn)驗(yàn)證了改進(jìn)算法的有"效性。

一、問題描述與模型建立

（一）FJSP問題描述

FJSP可描述為：有n個(gè)加工工件等待加工，工件集表示為J={J1，J2，···，Jn}；有m臺(tái)機(jī)器可選，機(jī)器集表示為M={M1，M2，···，Mm}；每個(gè)工件包含不超過r道工序，工序集表示為P={ }，"i=1，2，···，n;"j=1，2，···，r。根據(jù)加工機(jī)器可選情況又可分為完全柔性作業(yè)車間調(diào)度和部分柔性作業(yè)車間調(diào)度，其中，前者每道工序都有m臺(tái)機(jī)器可選，而后者所有工序中至少有一道工序至多可選（m-1）臺(tái)機(jī)器。柔性作業(yè)車間調(diào)度的目標(biāo)是在滿足工藝約束、資源約束和每個(gè)部件的其他約束的情況下，實(shí)現(xiàn)機(jī)器之間合理的工藝分配。

為了滿足實(shí)際加工要求，本文提出如下假設(shè)和約束：

1）各工件、工序及機(jī)器之間均相互獨(dú)立；

2）工件與工件之間無優(yōu)先級(jí)關(guān)系，但同一工件的某一工序的加工需在該工序的緊前工序完成后才能開始，二者之間存在順序約束；

3）零時(shí)刻，所有工件均處于可加工狀態(tài)；

4）某一時(shí)刻，一臺(tái)機(jī)器只允許加工一道工序；

5）一道工序僅在一臺(tái)機(jī)器上加工且過程中無中斷現(xiàn)象；

6）不同工序間的切換時(shí)間不計(jì)。

（二）參數(shù)定義

對(duì)本文問題描述及數(shù)學(xué)模型中所用符號(hào)參數(shù)進(jìn)行"定義，具體如表1。

（三）優(yōu)化目標(biāo)

本文優(yōu)化目標(biāo)包括最小化能源消耗、最小化生產(chǎn)成" 本和最小化懲罰值。

1.能源消耗

機(jī)器設(shè)備在使用過程中的能耗主要來自機(jī)器的啟動(dòng)、加工、空載及關(guān)閉等四個(gè)方面，由于機(jī)器設(shè)備在啟動(dòng)和關(guān)閉時(shí)耗時(shí)較短，本文將啟動(dòng)能耗和關(guān)閉能耗歸并于加工能耗，另外在前文假設(shè)中忽略了工序之間的運(yùn)輸時(shí)間，因此在能耗中也不考慮運(yùn)輸能耗。除此之外，加工車間中通常包含其他能耗設(shè)備，如照明、溫控等，本文定義這些能耗為固定能耗。

1）"加工能耗（"Pec），是指機(jī)械設(shè)備在正常加工過程中運(yùn)轉(zhuǎn)所消耗的能量，其計(jì)算方式如下：

式中， 表示機(jī)械設(shè)備加工功率， 表示工序在機(jī)器上的加工時(shí)間， 為0-1變量，" 表示工序 在機(jī)器上加工， 表示工序 不在機(jī)器上加工， 表示機(jī)械加工設(shè)備啟動(dòng)或關(guān)閉一次所需能耗，表示機(jī)器啟動(dòng)、關(guān)閉次數(shù)。

2）空載能耗（ ），指機(jī)械設(shè)備在使用過程中并未加工工件，而處于空轉(zhuǎn)狀態(tài)時(shí)所消耗的能量，計(jì)算公式如下：

式中，" 表示機(jī)械設(shè)備空載功率，" 表示機(jī)器加工完所有工序所需的時(shí)間。

3）固定能耗（ ），指加工車間除機(jī)械加工設(shè)備外照明、溫控等設(shè)備的能源消耗，計(jì)算公式如下：

式中，表示加工車間其他設(shè)備單位時(shí)間內(nèi)平均消耗功率。

綜上，車間總能耗表示為加工能耗、空載能耗及固定能耗之和，即

2.生產(chǎn)成本

生產(chǎn)成本最小化是企業(yè)利潤(rùn)最大化的重要體現(xiàn)，本文重點(diǎn)考慮原材料成本、加工成本及人工成本組成的生產(chǎn)成本計(jì)算模型。

1）原材料成本（ ），指購(gòu)買組成工件的原材料花費(fèi)的成本，計(jì)算公式如下：

式中，" 表示工件的原材料成本。

2）加工成本（ ），指機(jī)器在加工工件時(shí)耗費(fèi)的成本，計(jì)算公式如下：

式中，" 表示單位時(shí)間內(nèi)機(jī)器的加工成本。

3）人工成本（ ），指生產(chǎn)車間需要人工操作，期間產(chǎn)生的費(fèi)用，主要包括工人工資等，計(jì)算公式如下：

式中，" 表示單位時(shí)間內(nèi)工人操作機(jī)器所需人工成本。

綜上，總生產(chǎn)成本表示為原材料成本、加工成本及人工成本之和，即

3.懲罰值

懲罰值在生產(chǎn)車間中主要包含兩部分，一是產(chǎn)品完工時(shí)間早于交貨期，需要占用庫(kù)存，因此產(chǎn)生的庫(kù)存成本，本文以相應(yīng)的懲罰值代替；二是產(chǎn)品完工時(shí)間晚于交貨期，由此帶來企業(yè)信譽(yù)受損，本文以懲罰值作為量化結(jié)果體現(xiàn)。

1）提前完工懲罰值：

式中，" 表示提前完工懲罰值系數(shù)，" 表示企業(yè)與客戶之間約定的交貨期，" 表示產(chǎn)品完工時(shí)間（規(guī)定工件在機(jī)器上完成所有工序加工即為完工）。

2）拖期完工懲罰值：

式中，" 表示拖期完工懲罰值系數(shù)。總懲罰值計(jì)算公式如下：

（四）數(shù)學(xué)模型

本文構(gòu)建的多目標(biāo)柔性作業(yè)車間調(diào)度問題的數(shù)學(xué)模型如下：

目標(biāo)函數(shù)：

式（12）、式（13）、式（14）為本文求解多目標(biāo)柔性作業(yè)車間調(diào)度問題的設(shè)定的三個(gè)目標(biāo)函數(shù)，分別表示最小總能耗、最小總成本和最小懲罰值。式（15）、式（16）分別表示某一時(shí)刻，一道工序只能有一臺(tái)機(jī)器加工，同時(shí)，一臺(tái)機(jī)器只能加工一道工序；式（17）表明，同一零件的后續(xù)工序和前一工序之間必須有一個(gè)排序約束，即一個(gè)工序必須在前一工序完成后開始；式（18）表示工序加工過程中不可中斷；式（19）表示工序的開始"加工時(shí)間及完工時(shí)間均為非負(fù)。

二、改進(jìn)樽海鞘群算法求解MOFJSP

樽海鞘群算法（Salp"Swarm"Algorithm，SSA）[11]是近幾年提出的一種新穎的群智能優(yōu)化算法，主要模擬了樽海鞘鏈調(diào)整和覓食等過程，具有較強(qiáng)的全局和局部搜索能力，收斂性好、穩(wěn)定性強(qiáng)。但該算法當(dāng)前多用于求解連續(xù)性問題，對(duì)于離散型的車間調(diào)度問題，需要調(diào)整算法框架才能進(jìn)行有效求解。因此，本文通過編碼染色體進(jìn)行種群初始化，并對(duì)樽海鞘個(gè)體位置更新"進(jìn)行改進(jìn)以解決離散問題。

（一）標(biāo)準(zhǔn)樽海鞘群算法

在樽海鞘鏈的數(shù)學(xué)模型中，主要由兩部分組成，分別是領(lǐng)導(dǎo)者和追隨者，領(lǐng)導(dǎo)者位于食物鏈的頂端，而追隨者則跟隨其后，且領(lǐng)導(dǎo)者和追隨者會(huì)不斷更新各自的位置來尋找食物源F。以N×D維的樽海鞘群為例，其中，N表示樽海鞘個(gè)體數(shù)量，D表示空間維度，則樽海鞘鏈中的個(gè)體位置用二維矩陣表示，如式（20）：

樽海鞘領(lǐng)導(dǎo)者以式（21）方式進(jìn)行位置更新：

式中，"是樽海鞘領(lǐng)導(dǎo)者的位置，即第維第一個(gè)樽海鞘的位置，" 表示第維食物源的位置，""分別是第維的上、下界，" 、是[0，1]的隨機(jī)參數(shù)，式（21）表明了領(lǐng)導(dǎo)者 的位置更新與食物源 密切相關(guān)，并且系數(shù)在該算法中是一個(gè)重要參數(shù)，起到平衡的作用，其計(jì)算公式如下：

式中，是當(dāng)前迭代次數(shù)，是最大迭代次數(shù)。

樽海鞘追隨者的位置更新方式符合牛頓運(yùn)動(dòng)定律，具體表達(dá)式如下：

其中，" ，"表示第維中第個(gè)樽海鞘追隨者的位置；是時(shí)間，在算法中表示迭代，且迭代之間的差異為1；"的初速度為0，" ，" ，則方程（23）可表達(dá)如下：

表示第維中第 個(gè)追隨者的位置。綜上，（21）至（24）模擬了樽海鞘群的整體運(yùn)行機(jī)制。

（二）編碼與解碼

多目標(biāo)柔性作業(yè)車間調(diào)度問題由兩個(gè)主要的子問題構(gòu)成，分別是機(jī)器選擇和工序排序。針對(duì)工序排序部分，本文采用基于工序升序的隨機(jī)編碼，即每個(gè)樽海鞘個(gè)體由位置向量表示，取值位于0-1之間的不同隨機(jī)數(shù)，則向量的長(zhǎng)度為。以3工件8工序?yàn)槔?，先將位置向量與工序序號(hào)一一映射，再將位置向量進(jìn)行升序排列，從而得到工序編碼序列，圖1展示了具體的工序排序過程；機(jī)器選擇部分編碼根據(jù)工序可選機(jī)器集按工件順序隨機(jī)生成0到可選機(jī)器數(shù)之間的整數(shù)序列號(hào)，該部分編碼示意圖如圖2所示。

解碼過程首先按照編碼方式確定每道工序的加工順序并完成機(jī)器選擇，形成可行的調(diào)度方案，但該方法可能會(huì)造成部分機(jī)器存在較長(zhǎng)時(shí)間的空閑狀態(tài)。因此，本文采用插入式貪婪解碼[12]，過程中通過不斷遍歷加工機(jī)器，將待加工工件在不違反工序加工順序約束的前提下插入相應(yīng)機(jī)器空閑階段，以節(jié)約時(shí)間，提高效率。

（三）種群初始化

種群初始化是產(chǎn)生算法初始可行解的一條重要途徑，也是算法在迭代過程中生成最優(yōu)解的關(guān)鍵步驟之一。本文依據(jù)2.2節(jié)染色體編碼與解碼過程，采用隨機(jī)生成工序數(shù)量的位置向量，并按照升序排列形成工序加工順序方案，再隨機(jī)生成工序可選機(jī)器集序列號(hào)為各工序安排機(jī)器，以此進(jìn)行種群初始化，直至達(dá)到滿足"要求的種群規(guī)模。

（四）食物源存儲(chǔ)庫(kù)的引入

食物源作為樽海鞘群算法最優(yōu)解的導(dǎo)向，在單目標(biāo)優(yōu)化問題中，樽海鞘領(lǐng)導(dǎo)者直接向食物源方向移動(dòng)，而在多目標(biāo)優(yōu)化問題中，將其調(diào)整為向食物源存儲(chǔ)庫(kù)中的隨機(jī)一個(gè)鄰域移動(dòng)。食物源存儲(chǔ)庫(kù)的建立參考帶有精英保留策略的快速非支配排序遺傳算法過程，包括解的快速非支配排序、個(gè)體擁擠度計(jì)算和精英策略選擇，本文設(shè)置食物源存儲(chǔ)庫(kù)的大小為R，具體步驟如下：

1）計(jì)算個(gè)體在各維目標(biāo)下的目標(biāo)函數(shù)值，并通過快速非支配排序準(zhǔn)則，獲得個(gè)體非支配排序等級(jí)。

2）由式（25）計(jì)算個(gè)體在各目標(biāo)函數(shù)下的擁擠距離，而后將各維擁擠距離加和，如式（26）所示，獲得個(gè)體最終擁擠距離值。

3）從非支配排序第一等級(jí)開始選擇，若加和至某一等級(jí)時(shí)總個(gè)體數(shù)超過食物源存儲(chǔ)庫(kù)最大規(guī)模，則按擁擠距離降序順序依次添加個(gè)體，直至達(dá)到食物源存儲(chǔ)" 庫(kù)最大規(guī)模。

（五）位置更新

標(biāo)準(zhǔn)樽海鞘群算法雖然收斂速度快、參數(shù)少、行為機(jī)制簡(jiǎn)單，但其收斂精度有待提高，且算法易落入局部最優(yōu)[13]。引入正余弦策略使得個(gè)體位置更新不僅僅是依靠食物源位置，而是綜合考慮自身位置與食物源之間的信息差異，讓領(lǐng)導(dǎo)者向食物源的隨機(jī)方向移動(dòng)，以此提升算法的全局與局部搜索能力。基于此，本文在參考文獻(xiàn) [14]的基礎(chǔ)上，嘗試運(yùn)用正弦余弦算法（Sine"Cosine"Algorithm，"SCA）與樽海鞘群算法相結(jié)合的方法，改進(jìn)樽海鞘領(lǐng)導(dǎo)者位置更新方式。

由式（21）可知，樽海鞘領(lǐng)導(dǎo)者的位置隨著食物源不斷更新，追隨者則根據(jù)領(lǐng)導(dǎo)者變化而變化，算法通過不斷迭代使領(lǐng)導(dǎo)者逐漸靠近食物源，即可得到最優(yōu)解。依據(jù)SCA更新策略，樽海鞘領(lǐng)導(dǎo)者位置更新方式如下：

式（27）中 表示食物源存儲(chǔ)庫(kù)中隨機(jī)一個(gè)個(gè)體的位置向量，另外該式包含4個(gè)參數(shù)：參數(shù)定義了朝向或背離食物源移動(dòng)的距離，取值介于[0， ]；參數(shù)給出了食物源的隨機(jī)權(quán)重，取值介于[0，2]；參數(shù)決定了正余弦之間的切換，" ；參數(shù)決定了個(gè)體移動(dòng)方向，在式中起到平衡作用，且有如下計(jì)算方式：

其中，表示當(dāng)前迭代次數(shù)，表示最大迭代次數(shù)，是常數(shù)，本文設(shè)定為2。

樽海鞘追隨者的位置更新對(duì)于領(lǐng)導(dǎo)者具有較強(qiáng)的依賴性，本文引入線性微分遞減的慣性權(quán)重方法對(duì)其進(jìn)行改進(jìn)，參考文獻(xiàn) [15]，改進(jìn)后的位置更新方式如下：

式中，" 表示初始慣性權(quán)重，" 表示結(jié)束慣性權(quán)重。

（六）機(jī)器染色體變異

由于工序編碼和機(jī)器編碼方式不同，個(gè)體在進(jìn)行位置更新時(shí)，主要更新了工序部分。對(duì)于機(jī)器部分的更新，本文選擇染色體變異的方式，具體實(shí)施步驟如下：

1）隨機(jī)生成一個(gè)1/2染色體長(zhǎng)度的列表，元素為0到染色體長(zhǎng)度數(shù)之間；

2）從染色體下標(biāo)為0開始遍歷，若下標(biāo)數(shù)存在于步驟1）產(chǎn)生的列表中，則從該下標(biāo)所對(duì)應(yīng)的工序可選加工機(jī)器集中隨機(jī)選擇一臺(tái)機(jī)器，其序號(hào)作為新的染色體編號(hào)，否則，保留原染色體編號(hào)；

3）個(gè)體逐一重復(fù)上述操作，形成新的種群。

（七）IMSSA算法流程

本文在標(biāo)準(zhǔn)樽海鞘群算法上，結(jié)合MOFJSP特點(diǎn)，引入體現(xiàn)柔性作業(yè)車間調(diào)度問題的染色體編碼和解碼機(jī)制，建立食物源存儲(chǔ)庫(kù)，并基于SCA對(duì)樽海鞘群領(lǐng)導(dǎo)者進(jìn)行位置更新、基于慣性權(quán)重對(duì)樽海鞘群追隨者進(jìn)行位置更新，改進(jìn)的多目標(biāo)樽海鞘群算法流程及具體實(shí)施步驟見圖3。

步驟1：算法參數(shù)設(shè)定，種群初始化，令種群規(guī)模為N，食物源存儲(chǔ)庫(kù)規(guī)模為R。

步驟2：計(jì)算種群個(gè)體目標(biāo)函數(shù)值，進(jìn)行快速非支配排序得到非支配解等級(jí)，計(jì)算個(gè)體擁擠距離值，并通過精英保留策略確定食物源存儲(chǔ)庫(kù)。

步驟3：依據(jù)式（27）-（30）分別完成樽海鞘領(lǐng)導(dǎo)者和追隨者位置更新。

步驟4：位置更新后的個(gè)體與食物源存儲(chǔ)庫(kù)個(gè)體共同構(gòu)成新的種群，共同參與下一次迭代。

步驟5：判斷迭代是否達(dá)到最大次數(shù)，若否，則返回步驟2；若是，則輸出存儲(chǔ)庫(kù)，即為Pareto最優(yōu)解集。

三、實(shí)驗(yàn)結(jié)果與分析

（一）算法策略有效性分析

為了驗(yàn)證算法策略有效性，將改進(jìn)的樽海鞘群算法與其變體進(jìn)行實(shí)驗(yàn)對(duì)比。具體而言，IMSSA為改進(jìn)的混合樽海鞘群算法，包括主動(dòng)解碼、快速非支配排序及精英選擇策略建立的食物源存儲(chǔ)庫(kù)方法等；IMSSA1表示算法中的解碼過程不采用主動(dòng)解碼；IMSSA2表示算法中食物源存儲(chǔ)庫(kù)的建立采用個(gè)體適應(yīng)度排序的方式。

本文采用的評(píng)價(jià)指標(biāo)為多目標(biāo)優(yōu)化問題常用的綜合度量指標(biāo)，反世代距離（Inverted"Generational"Distance，IGD）和超體積（Hypervolume，HV）。其中，IGD能在一定程度上反映算法的收斂性和多樣性[5]，指標(biāo)越小，算法性能越好，計(jì)算公式如下：

式中，" 表示計(jì)算IGD值的真實(shí)帕累托前沿解集，

表示解的數(shù)量， 為近似解集，由各算法多次運(yùn)行所獲得，" 表示近似解集與真實(shí)解最近的歐式距離，則IGD為近似解集與真實(shí)解集的最近距離的平均值。

超體積（HV）為被非支配解集PF所支配且以參考點(diǎn)r為邊界的空間體積[16]，其值越大，表示算法的收斂性和多樣性越好，計(jì)算公式如下：

式中，" 為空間中被非支配解集PF支配的一個(gè)參考點(diǎn)，" 為非支配解集PF中的一個(gè)解，"為第維的目標(biāo)函數(shù)值。

實(shí)驗(yàn)數(shù)據(jù)采用BRdata測(cè)試集數(shù)據(jù)[17]，加工機(jī)器及其加工時(shí)間從數(shù)據(jù)集中提取，優(yōu)化目標(biāo)為最大完工時(shí)間、最大機(jī)器負(fù)荷和總機(jī)器負(fù)荷。各算法種群大小設(shè)置為100，最大迭代次數(shù)為200，初始慣性權(quán)重為0.9，結(jié)束慣性權(quán)重為0.4，食物源存儲(chǔ)庫(kù)最大規(guī)模為10。為消除隨機(jī)誤差，同一算例在各算法下分別運(yùn)行10次，其結(jié)果取平均值，同一算例下的最優(yōu)結(jié)果用粗體表示，計(jì)算結(jié)果如表2所示。以MK01為例，三種算法的各目標(biāo)函數(shù)值迭代收斂對(duì)比圖如圖4所示。

將IMSSA的結(jié)果與 IMSSA1的結(jié)果相比較，IGD和HV值更好，表明在本文提出的算法中使用主動(dòng)解碼為多目標(biāo)柔性作業(yè)車間調(diào)度問題提供了一個(gè)更好的解決方案。將IMSSA與IMSSA2結(jié)果對(duì)比，其IGD值和HV值同樣均較優(yōu)，表明本文采用快速非支配排序和精英策略建立食物源存儲(chǔ)庫(kù)的方式相較于使用適應(yīng)度值的方式具有更大的優(yōu)勢(shì)。綜上，本文在改進(jìn)樽海鞘群個(gè)體更新方式的基礎(chǔ)上，為求解多目標(biāo)柔性作業(yè)車間調(diào)度問題采用的主動(dòng)解碼策略及設(shè)計(jì)的食物源存儲(chǔ)" 庫(kù)確立方式均具有有效性。

（二）與其他算法對(duì)比

為驗(yàn)證本文所提算法IMSSA的有效性，將基于融合非支配排序遺傳算法（FNSGA）[18]作為對(duì)比算法進(jìn)行實(shí)驗(yàn)，采用MK01-MK07為實(shí)驗(yàn)算例，機(jī)器加工功率及空閑功率如表3所示，以最大完工時(shí)間和能耗為優(yōu)化目標(biāo)，實(shí)驗(yàn)參數(shù)同上，實(shí)驗(yàn)結(jié)果如表4所示，F(xiàn)1為最大完工時(shí)間，F(xiàn)2為能耗，本文算法獨(dú)立運(yùn)行所得非支配解如表5所示，其中括號(hào)內(nèi)第一項(xiàng)表示最大完工時(shí)間，第二項(xiàng)表示能耗。

對(duì)比表4目標(biāo)函數(shù)值可知，在7個(gè)算例中有4個(gè)算例IMSSA求得解優(yōu)于FNSGA求得解，而其余三個(gè)算例IMSSA所得解的最大完工時(shí)間小于FNSGA所得解，能夠與FNSGA所得解形成非支配解。綜合實(shí)驗(yàn)結(jié)果，本文所提算法較FNSGA在求解多目標(biāo)柔性作業(yè)車間"調(diào)度問題中具有明顯優(yōu)勢(shì)。

四、結(jié)論

本文以能源消耗、生產(chǎn)成本和懲罰值為優(yōu)化目標(biāo)建立了柔性車間調(diào)度問題的優(yōu)化模型，應(yīng)用改進(jìn)的多目標(biāo)樽海鞘算法進(jìn)行求解。改進(jìn)算法以基于工序升序排列的染色體初始化種群，設(shè)置食物源存儲(chǔ)庫(kù)以保留每代較優(yōu)非支配解，改進(jìn)樽海鞘領(lǐng)導(dǎo)者及追隨者位置更新方式，提高種群全局和局部搜索能力，并通過對(duì)比實(shí)驗(yàn)證明了IMSSA的有效性和可行性。在后續(xù)研究中，將考慮緊急插單、機(jī)器故障等動(dòng)態(tài)車間調(diào)度問題，以適應(yīng)更加符合現(xiàn)實(shí)生產(chǎn)車間的情況。

參考文獻(xiàn)：

［1］"楊艷華，"姚立綱."基于時(shí)間遞推建模及交叉熵算法求解柔性作業(yè)車間調(diào)度問題[J]."計(jì)算機(jī)集成制造系統(tǒng)，2021，27（6）：1703-1713.

［2］"李睿祺，"毛劍琳，"伍星，"等."改進(jìn)協(xié)同進(jìn)化算法求解柔性車間調(diào)度問題[J]."昆明理工大學(xué)學(xué)報(bào)（自然科學(xué)版），2022，47（5）：69-77.

［3］"SAQLAIN"M，"ALI"S，"LEE"J"Y." A"Monte-Carlo"tree"search"al-gorithm"for"the"flexible"job-shop"scheduling"in"manufacturing"sys-tems[J]." Flexible "Services "and "Manufacturing "Journal， 2023，35（2）：548-571.

［4］"彭建剛，"劉明周，"張銘鑫，"等."多目標(biāo)柔性作業(yè)車間調(diào)度算法研究綜述[J]."中國(guó)機(jī)械工程，2014，25（23）：3244-3254.

［5］"王秋蓮，"段星皓."基于高維多目標(biāo)候鳥優(yōu)化算法的柔性作業(yè)車間調(diào)度[J]."中國(guó)機(jī)械工程，2022，33（21）：2601-2612.

［6］"朱光宇，"徐文婕."考慮能耗與質(zhì)量的機(jī)床構(gòu)件生產(chǎn)線多目標(biāo)柔性作業(yè)車間調(diào)度方法[J]."控制與決策，2019，34（2）：252-260.

［7］"張洪亮，"徐公杰，"鮑薔，"等."考慮運(yùn)輸時(shí)間和機(jī)器預(yù)維護(hù)的柔性作業(yè)車間綠色調(diào)度[J/OL]."計(jì)算機(jī)集成制造系統(tǒng)，"2022-11-28.

［8］"姜一嘯，"吉衛(wèi)喜，"何鑫，"等."基于改進(jìn)非支配排序遺傳算法的多目標(biāo)柔性作業(yè)車間低碳調(diào)度[J]."中國(guó)機(jī)械工程，2022，33（21）：2564-2577.

［9］"MOKHTARI"H，"HASANI"A."An"energy-efficient"multi-objectiveoptimization"for"flexible"job-shop"scheduling"problem[J]." Com-puters"amp;"Chemical"Engineering，2017，104：339-352.

［10］"DAI"M，"TANG"D，"GIRET"A，"et"al."Multi-objective"optimizationfor"energy-efficient"flexible"job"shop"scheduling"problem"withtransportation"constraints[J]." Robotics"and"Computer-IntegratedManufacturing，2019，59：143-157.

［11］"MIRJALILI"S，"GANDOMI"A"H，"MIRJALILI"S"Z，"et"al." SalpSwarm "Algorithm： "A "bio-inspired "optimizer "for "engineeringdesign"problems[J]." Advances"in"Engineering"Software，2017，114：163-191.

［12］"張超勇，"董星，"王曉娟，"等."基于改進(jìn)非支配排序遺傳算法的多目標(biāo)柔性作業(yè)車間調(diào)度[J]."機(jī)械工程學(xué)報(bào)，2010，46（11）：156-164.

［13］"涂雪晨."改進(jìn)的樽海鞘優(yōu)化算法及其應(yīng)用研究[D]."鄭州："河南大學(xué)，"2021.

［14］"MIRJALILI"S."SCA："A"Sine"Cosine"Algorithm"for"solving"optim-ization"problems[J]."Knowledge-Based"Systems，2016，96：120-133.

［15］"張達(dá)敏，"陳忠云，"辛梓蕓，"等."基于瘋狂自適應(yīng)的樽海鞘群算法[J]."控制與決策，2020，35（9）：2112-2120.

［16］"YIN"L，"LI"X，"GAO"L，"et"al."A"novel"mathematical"model"andmulti-objective "method "for "the "low-carbon "flexible "job "shopscheduling "problem[J]." Sustainable "Computing "Informatics "amp;Systems，2016，13：15-30.

［17］"Brandimarte"P."Routing"and"scheduling"in"a"flexible"job"shop"bytabu"search[J]."Annals"of"Operations"Research，1993，41：157-183.

［18］"張麗，"王魯."基于能耗的柔性作業(yè)車間調(diào)度多目標(biāo)優(yōu)化算法[J]."現(xiàn)代電子技術(shù)，2020，43（7）：126-130.