楊紅雄 王惠酩

（天津理工大學(xué)管理學(xué)院，天津 300384）

隨著智能化在制造業(yè)中的普及，解決車間生產(chǎn)調(diào)度的問題能有效提高車間的工作學(xué)習(xí)效率，實(shí)現(xiàn)車間現(xiàn)場(chǎng)管理的有序化、智能化和高效化。為了合理地協(xié)調(diào)控制各個(gè)機(jī)器的生產(chǎn)以實(shí)現(xiàn)多方面目標(biāo)的pareto最優(yōu)狀態(tài)，學(xué)者們經(jīng)過多年的研究，使用各種不同的方法來分析和解決生產(chǎn)環(huán)節(jié)的FJSP。隨著研究的逐漸深入，為了更貼近車間生產(chǎn)現(xiàn)場(chǎng)的工作狀態(tài)，人們將柔性車間這一概念與車間調(diào)度問題相融合并提出了FJSP。由于FJSP問題在生產(chǎn)中廣泛存在，因此，該問題引起了國(guó)內(nèi)外相關(guān)學(xué)者的廣泛關(guān)注與研究[1?5]。Ishibuchi H使用遺傳算法求解FJSP問題，但算法的有效性較低[6]。Deng Q W使用NSGA-II算法并考慮分兩階段對(duì)多目標(biāo)FJSP進(jìn)行求解，并通過一些常用的函數(shù)驗(yàn)證算法的準(zhǔn)確性[7]。Kaya S等人對(duì)相關(guān)文獻(xiàn)進(jìn)行了綜述研究，并分析了多目標(biāo)FJSP的最新算法的思想解決以完工時(shí)間最大、機(jī)器負(fù)荷最小和瓶頸工序負(fù)荷最小為目標(biāo)的FJSP問題。陳魁等提出了優(yōu)化小生境粒子群的算法求解模型，將運(yùn)輸時(shí)間這一變量加入FJSP問題，構(gòu)建以完工時(shí)間最大化、機(jī)器負(fù)載最大化以及機(jī)器總負(fù)荷最小為目標(biāo)的模型[8]。

2020年，薛建凱等人受到麻雀尋找食物和躲避天敵的行為啟發(fā)提出麻雀搜索算法（sparrow search algorithm，SSA）[9]。該算法由于具有搜索精度高、收斂速度快、穩(wěn)定性強(qiáng)和有效地避免局部最優(yōu)值等方面的優(yōu)點(diǎn)，受到了國(guó)內(nèi)外學(xué)者廣泛關(guān)注。毛清華等發(fā)現(xiàn)原始的SSA算法容易陷入局部最優(yōu)問題，提出了將SSA與正弦余弦混合算法相融合的算法(improved sparrow search algorithm,ISSA)。并對(duì)算法的結(jié)果進(jìn)行測(cè)驗(yàn)，證明 ISSA 具有更高的尋優(yōu)精度和更快的求解效率[10]。湯安迪等人為了解決規(guī)劃無人機(jī)航跡時(shí)方案的求解難度大、方案不容易收斂等一些問題，使用了基于混沌麻雀搜索算法的航跡規(guī)劃方法，根據(jù)算法來規(guī)劃無人機(jī)的航跡方案，證明了SSA算法可以有效地解決這類問題[11]。楊瑋等以降低企業(yè)冷鏈物流的成本作為優(yōu)化目標(biāo)，考慮到冷鏈物流企業(yè)在貨物存儲(chǔ)和貨物運(yùn)輸?shù)拳h(huán)節(jié)會(huì)產(chǎn)生成本的現(xiàn)象，并結(jié)合我國(guó)最近正在實(shí)行的碳交易政策，將企業(yè)的碳排放代價(jià)同其他代價(jià)綜合考慮，建立以總代價(jià)最低為目標(biāo)的成本模型，設(shè)計(jì)并改良了麻雀搜索算法進(jìn)行計(jì)算，證明了麻雀搜索算法可以有效地解決冷鏈物流運(yùn)輸問題[12]。韓統(tǒng)等人提出了一種將對(duì)數(shù)螺旋策略和自適應(yīng)步長(zhǎng)策略相混合的思想與麻雀搜索算法相結(jié)合（logarithmic spiral strategy and adaptive step size strategy of the SSA,LASSA）來解決無人機(jī)協(xié)同航向規(guī)劃問題。驗(yàn)證了LASSA可以有效地解決多無人機(jī)協(xié)同航跡規(guī)劃問題[13]。

綜上所述，就算法的研究現(xiàn)狀來說，由于SSA是最近提出的一種算法，具有收斂速度快，不易陷入局部最優(yōu)等優(yōu)點(diǎn)。并且目前的研究使用SSA解決的大部分都是無人機(jī)領(lǐng)域的問題，將SSA運(yùn)用于實(shí)際車間生產(chǎn)制造中的研究較少。本文首次使用SSA解決柔性作業(yè)車間調(diào)度方面的問題，提出了基于FJSP的SSA算法，以最大完工時(shí)間最小和總能耗最小為優(yōu)化目標(biāo)求解FJSP。首先對(duì)FJSP問題進(jìn)行描述并根據(jù)其特點(diǎn)分析建模，然后介紹了一種可以求解FJSP問題的SSA算法，利用標(biāo)準(zhǔn)算例進(jìn)行仿真驗(yàn)證，由于SSA算法具有收斂速度快、結(jié)構(gòu)簡(jiǎn)單和不易陷于局部最優(yōu)的特點(diǎn)，解決了傳統(tǒng)算法在解決SSA問題時(shí)收斂速度慢，易于陷入局部最優(yōu)的問題，證明了SSA求解FJSP的可行性、高效性和優(yōu)越性。

1 問題描述與建模

1.1 問題描述

作業(yè)車間調(diào)度是根據(jù)實(shí)際車間有限的可用資源和已定的生產(chǎn)計(jì)劃，在滿足工藝約束的基礎(chǔ)上合理安排生產(chǎn)路線，均衡生產(chǎn)負(fù)荷，完成生產(chǎn)計(jì)劃的同時(shí)實(shí)現(xiàn)某種既定目標(biāo)的問題。FJSP是為了解決作業(yè)車間調(diào)度如何才能與多臺(tái)并行機(jī)相結(jié)合而提出的，主要涉及以下兩個(gè)問題：

（1）按什么順序加工工件。

（2）如何合理地分配機(jī)器。

FJSP已被證明是更復(fù)雜的NP-hard問題，本文的FJSP問題主要是基于解決以上2個(gè)問題，并結(jié)合車間的實(shí)際生產(chǎn)為了達(dá)到完成時(shí)間最短和總流程時(shí)間最短的目標(biāo)求出的pareto最優(yōu)解。

FJSP可以用以下例子來描述：設(shè)車間有m臺(tái)機(jī)器，需要加工n個(gè)工件，每臺(tái)機(jī)器表示為M1,M2,···,Mn。每個(gè)工件表示為N1,N2,···,Nn。每個(gè)工件在機(jī)器上一次性完成的工藝過程叫工序，Oij表示工件i的第j道工序。最終的目標(biāo)是使完成這批工件所用的時(shí)間最短和消耗的能源最少。相關(guān)的約束條件有：

（1）一臺(tái)機(jī)器在某一時(shí)刻只加工一個(gè)工件。

（2）每個(gè)工件加工生產(chǎn)的工序相同，工序的加工順序相同，根據(jù)算例的不同，不同工件在不同機(jī)器上加工消耗的時(shí)間不同。

（3）相同工件在某一時(shí)刻不能被不同的兩臺(tái)機(jī)器加工。

（4）工件在加工過程中不能更換機(jī)器加工。經(jīng)典的FJSP如下所示。以5臺(tái)機(jī)器加工3個(gè)工件，每個(gè)工件有3個(gè)加工工序的情況為例，加工的時(shí)間表如表1所示。

1.2 數(shù)學(xué)模型

數(shù)學(xué)模型可以清晰直觀地表達(dá)FJSP，我們將定義以下幾個(gè)參數(shù)變量：

r：工件總數(shù)，共有r個(gè)需要加工的工件，每個(gè)工件表示為N1,N2,···,Nr。

n：工序總數(shù)，工件Ni共有n道工序(i=1,2,···,r)。

k：機(jī)器總數(shù)，共有k個(gè)可以加工的機(jī)器，每臺(tái)機(jī)器表示為M1,M2,···,Mk。

Oij：工件Ni的第j道工序(j=1,2,···,n)。

Ωk：所有機(jī)器的集合{M1,M2,···,Mk}。

Ωik：工件Ni的第j道工序所有可選加工機(jī)器的集合，是機(jī)器集合Ωk的子集，Ωik∈{M1,M2,···,Mk}。

表13×5的完全柔性作業(yè)車間加工時(shí)間表

mik：工件Ni的第j道工序所有可以選擇的加工機(jī)器數(shù)。

Mijh：工件Ni的第j道工序(Oij)選擇在機(jī)器Mh上加工(h=1,2,···,k)。

Pijh：工序Oij在機(jī)器Mh上的加工時(shí)間。

Sij：工件Ni的第j道工序(Oij)的開始加工的時(shí)間。

Cij：工序Oij的完成加工時(shí)間。

Ci：工件Ni的完成加工的時(shí)間。

Cmax：所有工序完工時(shí)最大的完工時(shí)間。

Wt：所有機(jī)器加工完成最大工作負(fù)荷。

FJSP的約束條件有：約束條件是限制操作的可能分配的規(guī)則。FJSP問題主要有以下幾個(gè)有數(shù)條件：

式（1）表示加工第i個(gè)工件的第j道工序（Oij）只能在該道工序可以選擇的機(jī)器集合（Ωik）中選擇一臺(tái)機(jī)器進(jìn)行加工。式（2）表示加工第Ni個(gè)工件的第j道工序（Oij）的完工時(shí)間應(yīng)大于等于其在該機(jī)器上的開始加工時(shí)間與加工時(shí)間之和。式（3）表示一個(gè)零件的不同工序間需要滿足先后順序。式（4）表示機(jī)器上相鄰工件之間前一工件工序的完成加工時(shí)間應(yīng)小于等于下一工件工序的開始加工時(shí)間。式（5）表示所有工件最后一道工序的完工時(shí)間都小于等于最大完工時(shí)間。

本文考慮生產(chǎn)現(xiàn)場(chǎng)的時(shí)間生產(chǎn)情況，以最大完工時(shí)間（Cmax）和機(jī)器最大工作負(fù)荷（Wt）為目標(biāo)，建立最小化數(shù)學(xué)模型。目標(biāo)函數(shù)如式（6）和式（7）。

1.3 雙目標(biāo)優(yōu)化

對(duì)于2個(gè)目標(biāo)的FJSP問題目前主流的解決方法主要有3種：

（1）目標(biāo)規(guī)劃法：該方法主要用于解決參數(shù)和約束較少的優(yōu)化問題，首先需求出各子目標(biāo)的最優(yōu)值，然后將各子目標(biāo)的最優(yōu)值作為初始問題的約束。最后，將每個(gè)子目標(biāo)的值與其最優(yōu)值做差，最終的結(jié)果就是初始問題的最優(yōu)解。

（2）功效系數(shù)法：該方法對(duì)每個(gè)目標(biāo)函數(shù)進(jìn)行賦值，通過每個(gè)目標(biāo)對(duì)于整體結(jié)果的重要性來決定賦值的大小，綜合函數(shù)值最優(yōu)的結(jié)果及為函數(shù)的最優(yōu)解。

（3）動(dòng)態(tài)權(quán)重法：該方法對(duì)每個(gè)目標(biāo)函數(shù)進(jìn)行動(dòng)態(tài)賦值，與功效系數(shù)法不同的是，在算法迭代過程中，每迭代一次權(quán)重系數(shù)就變化一次，直到得到最優(yōu)解為止。

文獻(xiàn)[14]認(rèn)為產(chǎn)品的加工時(shí)間越小對(duì)于制造商降本增效的影響越突出，在車間調(diào)度的實(shí)施過程中，Cmax越小說明總生產(chǎn)周期越短，有助于提高企業(yè)的生產(chǎn)效率與資源利用率，Wt越小說明生產(chǎn)消耗的能耗越小，有助于降低企業(yè)生產(chǎn)成本。功效系數(shù)法相較其他兩種方法更適用于子目標(biāo)之間不均衡、具有主導(dǎo)性的多目標(biāo)問題，因此，本文考慮使用功效系數(shù)法求解FJSP問題。用dj(0

因此，目標(biāo)函數(shù)可以表示為

其中：ω1+ω2=1。

本文根據(jù)文獻(xiàn)[15]中的Delfi調(diào)查法得到ω1和ω2，對(duì)應(yīng)權(quán)重分別為0.7、0.3，在實(shí)際生產(chǎn)調(diào)度問題中該權(quán)重值應(yīng)根據(jù)車間生產(chǎn)需求情況進(jìn)行調(diào)整。

2 求解FJSP的SSA流程設(shè)計(jì)

SSA中每一只麻雀都代表一組可行的調(diào)度方案，麻雀的適應(yīng)度值表示調(diào)度方案的合理程度，適應(yīng)度值越高則表示方案越可行。麻雀尋找食物的過程可以被想象為“發(fā)現(xiàn)者-追隨者”模型，SSA將群內(nèi)個(gè)體分為發(fā)現(xiàn)者、追隨者和偵察者3種類型，為了提高個(gè)體的捕食幾率，當(dāng)追隨者通過發(fā)現(xiàn)者獲取食物時(shí)，種群中的一些個(gè)體為了增加自己的捕食量會(huì)與其他同類爭(zhēng)搶食物，同時(shí)，以安全第一為原則按比例將一部分麻雀作為偵察者進(jìn)行偵察和預(yù)警，當(dāng)偵察者發(fā)現(xiàn)危險(xiǎn)時(shí)及時(shí)警告其他麻雀如果發(fā)現(xiàn)危險(xiǎn)則停止進(jìn)食，由發(fā)現(xiàn)者重新尋找食物。通過不斷地捕食和反捕食行為迭代更新進(jìn)行尋優(yōu)進(jìn)化。

下面將介紹一種適合解決FJSP的SSA并解決一個(gè)以最大完工時(shí)間最小和總能耗最小為優(yōu)化目標(biāo)的FJSP。

2.1 編碼與解碼

SSA通過不斷地更新自身的位置和尋找食物源的方式對(duì)優(yōu)化的目標(biāo)進(jìn)行搜索，F(xiàn)JSP主要是解決工件排序和機(jī)器指派這2個(gè)問題，因此，本文使用兩階段向量編碼方法，前一段確定工序的加工順序，后一段確定機(jī)器的指派問題，保證了編碼后個(gè)體的有效性。

以3個(gè)工件每個(gè)工件包含兩道工序的問題為例，編碼鏈前半段（第1位?第6位編碼）為工序隨機(jī)排序的方案。例如，編碼中第二位的“3”表示工件3的第一道工序；后半段（第7位?第12位編碼）為機(jī)器的隨機(jī)分配方案，每個(gè)編碼表示工序在機(jī)器上的加工順序。例如，編碼中第七位的“2”表示工序O12即第一個(gè)工件的第二道工序在機(jī)器2上加工。隨機(jī)生成的編碼鏈按圖1的方式進(jìn)行存儲(chǔ)。

圖1 編碼方式

在解碼的過程中，首先根據(jù)工序排序編碼鏈確定一個(gè)工件在機(jī)器上的加工順序，然后機(jī)器分配編碼確定各個(gè)機(jī)器上加工的工序順序，即轉(zhuǎn)化為一個(gè)工序表，根據(jù)工序表將所有工序安排在適當(dāng)?shù)募庸C(jī)器和加工位置上，最后生成可行的調(diào)度方案。

2.2 SSA算法步驟

2.2.1 種群初始化

設(shè)定算法的各部分參數(shù)如最大迭代次數(shù)、種群數(shù)量、發(fā)現(xiàn)者比例和安全閾值等。

本文隨機(jī)生成編碼產(chǎn)生初始調(diào)度解，每一只麻雀表示一個(gè)調(diào)度方案，由n只麻雀組成的種群可以表示為

其中：d為問題的維數(shù)；n為麻雀的數(shù)量。那么，每個(gè)方案的適應(yīng)度表示為

其中：f是適應(yīng)度值，根據(jù)適應(yīng)度值的大小對(duì)麻雀?jìng)€(gè)體進(jìn)行排序，進(jìn)而選擇出最優(yōu)個(gè)體和最差個(gè)體，得到全局最優(yōu)位置，然后根據(jù)設(shè)定的警報(bào)值進(jìn)入迭代循環(huán)。

2.2.2 發(fā)現(xiàn)者的位置更新

在SSA中，麻雀?jìng)€(gè)體相對(duì)種群的位置表示可行的調(diào)度方案。假設(shè)在D維空間中存在N只麻雀，每只麻雀可以表示為一個(gè)矩陣

則麻雀i的位置可以記作

式（8）中：n是麻雀的數(shù)量。式（9）中：i表示第i只麻雀。i=1,2,3,···,n。D代表變量的維數(shù)。Xi,1表示問題維數(shù)為1維時(shí)，第i只麻雀的位置。

每個(gè)個(gè)體的適應(yīng)度值表示為

Fx表示每個(gè)個(gè)體的適應(yīng)度值，根據(jù)適應(yīng)度對(duì)麻雀進(jìn)行排序，選出適應(yīng)度好的麻雀?jìng)€(gè)體作為發(fā)現(xiàn)者尋找食物源并優(yōu)先獲得食物，帶領(lǐng)其他麻雀向食物源靠近。在種群中，發(fā)現(xiàn)者和追尋者數(shù)量在每次迭代循環(huán)中一般都保持一致，占麻雀種群數(shù)量的10%～20%。發(fā)現(xiàn)者的位置更新公式為

其中：t為算法當(dāng)前的迭代次數(shù)，i表示第i只麻雀，j表示問題的維數(shù)，表示第t+1次迭代時(shí)第i只麻雀在第j維的位置；μ是范圍在（0,1）之間的隨機(jī)數(shù)；Tmax是最大迭代次數(shù)；R2∈[0,1]、ST∈[0.5,1]分別代表預(yù)警值和安全值；Q是一個(gè)遵從[0,1]正態(tài)分布的隨機(jī)數(shù)；L是一個(gè)所有元素都是1的1×d維矩陣。當(dāng)R2

2.2.3 追隨者的位置更新

追隨者的位置更新公式為

2.2.4 偵察預(yù)警行為

當(dāng)種群中的偵察者發(fā)現(xiàn)危險(xiǎn)或捕食者時(shí)，就會(huì)向種群發(fā)出警報(bào)信號(hào)，此時(shí)，無論是尋找食物的發(fā)現(xiàn)者還是正在進(jìn)食的追隨者都會(huì)放棄當(dāng)前食物并改變其位置向安全的位置移動(dòng)。發(fā)現(xiàn)者到達(dá)安全位置后才會(huì)繼續(xù)尋找新的食物源，繼續(xù)迭代更新其位置。一般種群都會(huì)選取SD（種群數(shù)量的10%～20%）只麻雀作為偵察者對(duì)周圍位置的安全偵察預(yù)警。偵察者的位置更新公式為

式（14）中：β是步長(zhǎng)控制參數(shù)，服從均值為0，方差為1的正態(tài)分布隨機(jī)數(shù)。fi是第i只麻雀的適應(yīng)度值；fg是當(dāng)前麻雀的全局最優(yōu)適應(yīng)度值；K是步長(zhǎng)控制參數(shù)服從[?1,1]的均勻隨機(jī)分布，用于表示麻雀的移動(dòng)方向；fw是當(dāng)前適應(yīng)度值最低的個(gè)體；ε是常數(shù)，為了防止出現(xiàn)分母為0的情況，一般 ε的值極小。當(dāng)fi≠fg時(shí)表明，麻雀i的位置處于種群的邊緣，極易受捕食者的攻擊；當(dāng)fi=fg時(shí)表明，麻雀i正處于種群中間的位置，意識(shí)到了來自捕食者的危險(xiǎn)，需要靠近其他麻雀?jìng)€(gè)體來減少自己被捕食的危險(xiǎn)并調(diào)整搜索策略。

算法的具體步驟如下：

Step1：輸入算例的數(shù)據(jù)。

Step2：初始化種群，如設(shè)定麻雀種群中發(fā)現(xiàn)者的數(shù)量、意識(shí)到危險(xiǎn)的麻雀所占種群的比例。

Step3：初始化算法參數(shù)并對(duì)數(shù)據(jù)進(jìn)行編碼，生成初始調(diào)度方案，找到種群中最好和最差的個(gè)體。

Step4：根據(jù)式（13）、（14）更新發(fā)現(xiàn)者、追隨者位置。

Step5：判斷新位置的適應(yīng)度值是否好于當(dāng)前位置，如果沒有則保持當(dāng)前位置不變繼續(xù)下一步操作；如果有則更新當(dāng)前位置。

Step6：直至收斂或達(dá)到最大迭代次數(shù)算法結(jié)束并得到優(yōu)化目標(biāo)的最優(yōu)解。

根據(jù)以上對(duì)于數(shù)學(xué)模型的描述和算法的步驟，設(shè)計(jì)基于FJSP問題的流程如圖2所示。

圖2 算法流程圖

3 仿真測(cè)試

本文使用MATLAB編程語言并使用MATLAB 2017a運(yùn)行程序。運(yùn)行環(huán)境為：WinXP操作系統(tǒng)下內(nèi)存為8 GB的Intel Core(TM) i5-7200U CPU 2.50 GHz的計(jì)算機(jī)上運(yùn)行。

文獻(xiàn)[9]中認(rèn)為發(fā)現(xiàn)者比例應(yīng)占種群數(shù)量的10%–20%；安全閾值ST∈[0.5,1]；種群大小和迭代次數(shù)應(yīng)與對(duì)比試驗(yàn)保持相同設(shè)置，因此，SSA算法參數(shù)設(shè)定如下：工件總數(shù)為r，機(jī)器總數(shù)為k，種群大小為200，迭代次數(shù)為300，發(fā)現(xiàn)者比例為20%，追隨者比例80%，安全閾值為0.5，目標(biāo)權(quán)重ω1=0.7，ω2=0.3。如表2所示。

表2 算法參數(shù)

為了檢驗(yàn)算法的尋優(yōu)性能和證明算法在解決FJSP問題的可行性，使用實(shí)例一證明算法的可行性，使用實(shí)例二和實(shí)例三對(duì)SSA的性能進(jìn)行比較。實(shí)例一是文獻(xiàn)[16]中同樣以最大完工時(shí)間和總負(fù)荷最小為目標(biāo)函數(shù)的6×6實(shí)際案例；實(shí)例二和實(shí)例三是Kacem測(cè)試集中的3×4和4×5算例。

為驗(yàn)證SSA在解決實(shí)際FJSP問題的可行性，使用文獻(xiàn)[16]中的實(shí)際生產(chǎn)車間的原始數(shù)據(jù)。文獻(xiàn)[16]中數(shù)據(jù)來自于某汽車公司總裝車間的生產(chǎn)數(shù)據(jù)，經(jīng)過取整處理后得到規(guī)模為6×6的實(shí)驗(yàn)數(shù)據(jù)。將實(shí)例一數(shù)據(jù)代入本文算法中運(yùn)算，結(jié)果與文獻(xiàn)[16]中tsPSO和CMABC算法得出的結(jié)果進(jìn)行對(duì)比。表3為示例一實(shí)際案例的試驗(yàn)結(jié)果。其中，加粗的結(jié)果表示同一算例下使用各算法得到的最優(yōu)值，“N/A”表示相關(guān)文獻(xiàn)中沒有給出這一算例的結(jié)果。

表3 實(shí)際案例實(shí)驗(yàn)結(jié)果

結(jié)果表明，SSA算法仿真模擬的結(jié)果明顯好于其他兩種算法，還給出了與其他兩種算法完全不同的調(diào)度方案，增加了企業(yè)生產(chǎn)調(diào)度時(shí)的選擇方案。從單目標(biāo)最優(yōu)值來看，SSA算法在Cmax、Wt兩個(gè)目標(biāo)都得到了最優(yōu)解，使企業(yè)在選擇上更加靈活。將實(shí)例一的生產(chǎn)數(shù)據(jù)通過SSA運(yùn)行，得到最優(yōu)解為：Cmax=12、Wt=41，證明了SSA在實(shí)際生產(chǎn)的可行性。圖3為實(shí)際生產(chǎn)數(shù)據(jù)最優(yōu)解的甘特圖。

圖3 實(shí)際案例甘特圖

采用Kacem I[17]設(shè)計(jì)的測(cè)試算例來驗(yàn)證算法的有效性。將SSA算法與分布估計(jì)算法[18]、基于正態(tài)云的狀態(tài)轉(zhuǎn)移算法[19]及混合人工蜂群算法[20]的文獻(xiàn)中所提及的算例結(jié)果進(jìn)行比較，證明SSA解決柔性車間調(diào)度問題的優(yōu)越性。測(cè)試結(jié)果如表4所示。其中，加粗的結(jié)果表示同一算例下使用各算法得到的最優(yōu)值，“N/A”表示相關(guān)文獻(xiàn)中沒有給出這一算例的結(jié)果。

表4 實(shí)際案例實(shí)驗(yàn)結(jié)果

結(jié)果表明，對(duì)于Kacem1問題，SSA得到的3組解除了均優(yōu)于EDA得到的兩組解。從單目標(biāo)最優(yōu)來看，SSA在Cmax、Wt兩個(gè)問題的最優(yōu)解分別為6和15，較其他算法具有較強(qiáng)的求解優(yōu)勢(shì)。對(duì)于Kacem2問題，雖然CSTA和SSA都得到了（11，32，17.3）的最優(yōu)解，但在解的數(shù)量上，SSA明顯優(yōu)于其他兩種算法，為實(shí)際調(diào)度的方案提供了更多選擇方式。從單目標(biāo)最優(yōu)來看，SSA在Cmax、Wt兩個(gè)問題的最優(yōu)解分別為11和32，說明SSA具有較強(qiáng)的尋優(yōu)能力，能夠向組合后的單目標(biāo)最優(yōu)解提供較多的選擇，證明了SSA在可行解數(shù)量和單目標(biāo)可行解上的優(yōu)勢(shì)。圖4和圖5分別給出了Kacem1的最優(yōu)解（6，15，8.7）和Kacem2的最優(yōu)解（11，32，17.3）的最優(yōu)解的甘特圖。

圖4 Kacem1最優(yōu)解的甘特圖

圖5 Kacem2最優(yōu)解的甘特圖

4 結(jié)語

針對(duì)目前元啟發(fā)式算法在解決FJSP問題時(shí)存在收斂速度慢，易于陷入局部最優(yōu)的問題。由于SSA算法具有收斂速度快，尋優(yōu)能力強(qiáng)的特點(diǎn)，本文結(jié)合SSA算法提出了一種可以解決FJSP問題的SSA方法。以最大完工時(shí)間和總能耗為指標(biāo)構(gòu)建了作業(yè)車間調(diào)度模型，為了適應(yīng)FJSP改變了SSA的編碼和解碼方式。最后，使用幾種FJSP的經(jīng)典算例驗(yàn)證SSA解決FJSP的可行性，說明了SSA在求解FJSP的可行性和高效性。下一步將考慮將SSA應(yīng)用于更多約束的車間調(diào)度問題上，解決更多實(shí)際生產(chǎn)問題。