李佳蓉，晁永生，李純艷，袁逸萍

（新疆大學(xué)智能制造現(xiàn)代產(chǎn)業(yè)學(xué)院，新疆烏魯木齊 830017）

0 前言

在“中國(guó)制造2025” 的背景下，我國(guó)制造產(chǎn)業(yè)的生產(chǎn)模式正逐步由大批量單一產(chǎn)品向多品種、小批量定制化產(chǎn)品方向轉(zhuǎn)變。定制化產(chǎn)品在生產(chǎn)過(guò)程中，由于其結(jié)構(gòu)復(fù)雜、多變等原因，通常有多條不同的生產(chǎn)加工路線。同時(shí)，日益多樣化的訂單需求，迫使制造單元更具柔性。

在傳統(tǒng)作業(yè)車間問(wèn)題中，各工件的工序、加工機(jī)器以及對(duì)應(yīng)的加工時(shí)間是固定的，而柔性作業(yè)車間問(wèn)題（Flexible Job Shop Problem，F(xiàn)JSP）是在作業(yè)車間問(wèn)題的基礎(chǔ)上兼顧考慮工件各工序機(jī)器選擇的不確定以及機(jī)器加工不同工序的時(shí)間不確定，這更符合實(shí)際生產(chǎn)的情況。

近年來(lái)，F(xiàn)JSP 已被國(guó)內(nèi)外諸多學(xué)者廣泛研究，如，在模型搭建和求解方面，JALILVAND-NEJAD、FATTAHI［1］基于加工循環(huán)下的FJSP 問(wèn)題提出一種混合整數(shù)線性規(guī)劃模型，并采用遺傳算法進(jìn)行求解驗(yàn)證。WU 等［2］研究了考慮夾具裝卸時(shí)間的雙資源約束FJSP 并建立了數(shù)學(xué)模型。VITAL-SOTO 等［3］建立了具有排序靈活性的FJSP 的數(shù)學(xué)模型，并提出一種混合細(xì)菌覓食優(yōu)化算法求解該問(wèn)題。PENG 等［4］構(gòu)建了以加工時(shí)間、能耗和噪聲為優(yōu)化目標(biāo)的雙約束多目標(biāo)的FJSP 模型，并提出一種混合離散多目標(biāo)帝國(guó)競(jìng)爭(zhēng)算法來(lái)進(jìn)行求解。NOURI 等［5］提出一種基于混合元啟發(fā)式算法的聚類整體多智能體方法來(lái)求解FJSP。張宇嘉、宋威［6］以完工時(shí)間最優(yōu)為目標(biāo)，采用構(gòu)建精英檔案和進(jìn)步檔案的方法，提出一種雙檔案粒子群算法對(duì)FJSP 進(jìn)行求解。雖然他們從模型和求解方法上對(duì)FJSP 進(jìn)行了深入研究，但目前絕大多數(shù)的研究只考慮了工件的單個(gè)工藝方案，即工件的每道工序只考慮機(jī)器的可替代性。而在實(shí)際生產(chǎn)過(guò)程中工件可以有多條工藝路線，前人對(duì)考慮多工藝路線FJSP 的研究相當(dāng)有限。

在柔性作業(yè)車間的綜合調(diào)度過(guò)程中，往往忽略多工藝路線這一關(guān)鍵因素，造成設(shè)備利用率較低、零件在某一機(jī)器堆積、單件產(chǎn)品加工時(shí)間過(guò)長(zhǎng)等問(wèn)題。因此，將多工藝路線下的柔性作業(yè)車間調(diào)度應(yīng)用于產(chǎn)品制造對(duì)提高企業(yè)綜合競(jìng)爭(zhēng)能力尤為重要。同時(shí)，由于加入多約束，模型在求解時(shí)的搜索空間范圍增大，一般算法容易在求解過(guò)程中陷入局部最優(yōu)，導(dǎo)致搜索魯棒性差、效率低下。因此，本文作者建立一種多工藝路線柔性作業(yè)車間問(wèn)題（Multiprocess Route Flexible Job Shop Problem，MRFJSP）模型，并提出一種改進(jìn)原子軌道搜索（Improved Atomic Orbital Search，IAOS）算法，用于避免模型求解過(guò)程中效率低下的問(wèn)題。

1 多工藝路線柔性作業(yè)車間調(diào)度問(wèn)題

1.1 問(wèn)題描述

MRFJSP 模型作為企業(yè)在生產(chǎn)過(guò)程中為各工件選擇合理加工路線、工序排序和機(jī)器分配，以實(shí)現(xiàn)調(diào)度目標(biāo)的有效手段，可描述如下：有多個(gè)工件需要加工，每個(gè)工件的加工特征不同，不同特征可由多種加工方式實(shí)現(xiàn)，不同的加工方式可組合出多條加工路線，各路線包含的工序數(shù)不同，各工序可選的機(jī)器柔性，各機(jī)器加工同道工序的時(shí)間不同。由于在生產(chǎn)調(diào)度過(guò)程中會(huì)出現(xiàn)一種產(chǎn)品可按照不同工藝路線進(jìn)行加工、一臺(tái)機(jī)器同一時(shí)刻只能加工一件產(chǎn)品等情況，為明確MRFJSP 模型中的約束關(guān)系，做出如下假設(shè)：

（1）零件可選擇不同工藝路線且不同工藝路線下的工序之間不存在優(yōu)先級(jí)關(guān)系；

（2）禁止關(guān)閉閑置機(jī)器且不考慮機(jī)器故障；

（3）工序一旦開(kāi)始就不允許中斷；

（4）零件的一道工序完成后即可到達(dá)加工的下一個(gè)機(jī)器。

文中模型相關(guān)參數(shù)及其含義見(jiàn)表1。

表1 相關(guān)參數(shù)及其含義Tab.1 Relevant parameters and their meanings

1.2 問(wèn)題模型搭建

為提高多工藝路線柔性作業(yè)車間效率，以完工時(shí)間最小為調(diào)度優(yōu)化目標(biāo)函數(shù)，表示為式（1）：

根據(jù)基準(zhǔn)先行、先主后次、先面后孔的工藝規(guī)則，在保證有效和完整的前提下滿足以下約束：

（1）工藝路線約束。每個(gè)工件每次只能選擇一條工藝路線，表示為式（2）：

（2）機(jī)器選擇約束。各工序只允許被一臺(tái)機(jī)器進(jìn)行加工，表示為式（3）：

（3）機(jī)器約束。在任意時(shí)刻每臺(tái)機(jī)器只能加工一道工序，表示為式（4）：

（4）先序關(guān)系約束。各工件的不同工序不允許同時(shí)加工，表示為式（5）：

（5）工件加工時(shí)間約束。加工工件的完成時(shí)間非負(fù)，表示為式（6）：

（6）工序時(shí)間約束。工序的開(kāi)始時(shí)間均不大于工序的完工時(shí)間，表示為式（7）：

（7）加工路線決策變量約束。工件在第l條加工路線被選中，表示為式（8）：

（8）機(jī)器決策變量約束。工件的第l條路線的第j道工序是否在機(jī)床k上加工，表示為式（9）：

2 改進(jìn)原子軌道搜索算法

原子軌道搜索（Atomic Orbital Search，AOS）算法是由AZIZI［7］在2021 年提出的一種高效的元啟發(fā)式算法，其設(shè)計(jì)源于量子力學(xué)原理和量子原子模型。AZIZI 等［8］結(jié)合AOS 研究了多個(gè)領(lǐng)域著名工程問(wèn)題，驗(yàn)證了AOS 適用于求解不同規(guī)模組合優(yōu)化問(wèn)題，具有較優(yōu)的魯棒性、群體性。但考慮加入加工路線柔性和機(jī)器柔性等約束，問(wèn)題的復(fù)雜性指數(shù)式增長(zhǎng)，搜索空間急速擴(kuò)大，此時(shí)若使用AOS 進(jìn)行求解，反而會(huì)降低算法的搜索效率，影響全局最優(yōu)值的獲得，因而本文作者提出一種改進(jìn)原子軌道搜索（Improved Atomic Orbital Search，IAOS）算法。

2.1 原子軌道搜索算法基本原理

AOS 算法通過(guò)效仿原子核外部電子密度變化、電子能量狀態(tài)以及受各類因素干擾電子發(fā)生躍遷，從電子的選擇、搜索和更新這3 個(gè)方面建立數(shù)學(xué)模型，模擬算法的尋優(yōu)過(guò)程［7］。

AOS 將原子核外的電子云模擬成薄的、同心的層作為算法的搜索空間，如圖1 所示。電子層表示為Xk，k表示電子層數(shù)。搜索空間中的電子用候選解Xi表示，候選解為電子在原子軌道模型中的映射，Xi的位置用一組決策變量［，，…，］表示，電子層X(jué)k中的一組候選解如式（10）所示。候選解在搜索空間中的層數(shù)是由電子的概率密度確定的，在數(shù)學(xué)模型中使用概率密度函數(shù)進(jìn)行確定。

圖1 電子躍遷示意Fig.1 Electron transition schematics

候選解在搜索空間中的初始位置由式（11）隨機(jī)確定，候選解的能量值表示為，即函數(shù)值。在求解最小化優(yōu)化問(wèn)題時(shí)，將候選解的能量值升序排序，能量值越小，候選解的概率密度值越高，以代表具有較低能量值的電子。

其中：i表示電子層中的第i個(gè)候選解，i∈｛1，2，…，m｝；d表示維度，j∈｛1，2，…，d｝。

候選解進(jìn)行位置更新時(shí)需考慮光或其他影響因素，如粒子、磁場(chǎng)等對(duì)電子的作用。電子受這些因素影響時(shí)會(huì)從基態(tài)躍遷至激發(fā)態(tài)，離開(kāi)所在電子層，電子位置隨之變化，即候選解位置發(fā)生更新。候選解位置更新的方式如下：

（1）當(dāng)光對(duì)電子產(chǎn)生作用（?≥PR）時(shí)：

①當(dāng)電子吸收光子時(shí)（≥BE），電子能量升高，電子從低能級(jí)向高能級(jí)躍遷，電子位置更新，即候選解位置更新，可用式（12）表示：

②當(dāng)電子發(fā)射光子時(shí)（＜BE），電子能量降低，電子從高能級(jí)向低能級(jí)躍遷，電子位置更新，即候選解位置更新，可用式（13）表示：

（2）除了受光子的影響外，電子的能量還受其他因素作用（?＜PR），此時(shí)電子位置也會(huì)更新，可用式（14）表示：

其中：?表示電子受影響的概率；PR表示光對(duì)電子作用的概率；分別表示更新前、后的候選解位置；LE表示所在層最低能量的電子位置；BS表示候選解所對(duì)應(yīng)的結(jié)合態(tài)，用平均候選解位置向量表示；BE表示候選解所在層所對(duì)應(yīng)的結(jié)合能，用層最低能量表示；ri表示一個(gè)隨機(jī)生成的電子位置；αi、βi和γi均為隨機(jī)數(shù)。

2.2 改進(jìn)算法的編碼與解碼

基于建立的MRFJSP 模型，將候選解位置向量設(shè)為三段式向量，三段向量分別對(duì)應(yīng)路線選擇、工序排序與機(jī)器分配。候選解位置向量維度d＝N＋2G，第一段向量長(zhǎng)度為N，第二段、第三段向量長(zhǎng)度均為G，N為工件數(shù)，G為加工所有工件的總工序數(shù)。候選解位置向量中各元素值均使用隨機(jī)函數(shù)均勻生成實(shí)現(xiàn)全局初始化，候選解位置向量中各元素取值范圍均為［-ε，ε］，ε＝N。

假設(shè)有一個(gè)MRFJSP，問(wèn)題中有2 個(gè)工件，每個(gè)工件分別有2 條加工路線，每個(gè)工件的1、2 條路線分別有2、3 道工序。該問(wèn)題的候選解由3 段向量構(gòu)成，第一段向量長(zhǎng)為2，后兩段的長(zhǎng)度需根據(jù)第一段向量中的信息進(jìn)行計(jì)算。若候選解第一段隨機(jī)位置向量為［1.8，-1.4］，則通過(guò)編碼操作得到第一段向量為［2，1］，即工件1 選擇路線2，工件2 選擇路線1。此時(shí)可知該加工任務(wù)的總工序數(shù)為5，則該候選解位置向量總長(zhǎng)為12，圖2 為滿足第一段位置向量［1.8，-1.4］的一個(gè)候選解。

圖2 候選解位置向量Fig.2 Candidate solution position vector

2.2.1 編碼

候選解位置向量的編碼包含路線選擇、工序排序和機(jī)器分配3 個(gè)部分。對(duì)第一段路線選擇位置向量進(jìn)行編碼時(shí)，編碼的長(zhǎng)度對(duì)應(yīng)總工件數(shù)，向量中的每個(gè)位置依次與工件號(hào)對(duì)應(yīng)。根據(jù)各工件的可選路線數(shù)將候選解位置元素的取值范圍［-ε，ε］均勻分區(qū)，判斷候選解位置元素值所屬的分區(qū)，得到候選解位置元素對(duì)應(yīng)的路線。以圖2 為例，候選解位置元素的取值范圍是［-2，2］，工件1 的可選路線兩條，將范圍均勻分區(qū)為［-2，0）和［0，2］，判斷元素所屬區(qū)間，則工件1 選擇路線2，工件2 選擇路線1。完成路線選擇位置向量的編碼、獲得總工序數(shù)后，采用最大位置規(guī)則對(duì)工序排序位置向量進(jìn)行編碼［9］，首先對(duì)工序排序位置向量進(jìn)行降序排序，再依照所得的排序位置對(duì)工序順序進(jìn)行重排列，得到編碼結(jié)果。編碼轉(zhuǎn)換過(guò)程如圖3所示。

圖3 工序排序位置向量編碼過(guò)程Fig.3 Process sorting position vector encoding process

完成前兩段編碼后才可開(kāi)始第三段機(jī)器分配位置向量編碼。在該編碼過(guò)程中需考慮候選解位置元素與對(duì)應(yīng)工件的可選機(jī)器之間的關(guān)系。文中采用文獻(xiàn)［10］的編碼方式，如公式（15），它將候選解位置向量映射到對(duì)應(yīng)可選機(jī)器的機(jī)器序號(hào)，實(shí)現(xiàn)機(jī)器分配編碼，即公式對(duì)應(yīng)計(jì)算出的值就是選擇的機(jī)器號(hào)，當(dāng)計(jì)算的機(jī)器號(hào)不存在時(shí)，設(shè)置該機(jī)器號(hào)為1。

其中：為機(jī)器分配編碼；為候選解位置元素；s（d）為可選擇的機(jī)器集合；ε為總工件數(shù)。

由式（15）可對(duì)機(jī)器分配位置向量進(jìn)行編碼，編碼的轉(zhuǎn)換過(guò)程如圖4 所示。

圖4 機(jī)器分配位置向量編碼過(guò)程Fig.4 Machine allocation position vector encoding process

2.2.2 解碼

解碼也包含路線選擇、工序排序和機(jī)器分配3 個(gè)部分。第一段路線選擇解碼需根據(jù)各工件的可選路線數(shù)將候選解位置元素的取值范圍［-ε，ε］均勻分區(qū)，判斷候選解編碼元素值所屬的分區(qū)范圍，在該范圍內(nèi)隨機(jī)取值，從而實(shí)現(xiàn)路線選擇解碼。

完成第一段解碼后采用最大位置規(guī)則中的轉(zhuǎn)換公式（16），獲得第二段工序排序位置向量對(duì)應(yīng)的解碼向量［9］，然后將原工序排序位置向量進(jìn)行升序排序，根據(jù)升序排序后的位置值對(duì)解碼向量重新排序，最終完成工序排序位置向量解碼。

完成第二段解碼后對(duì)第三段機(jī)器分配向量解碼，該解碼過(guò)程相當(dāng)于機(jī)器分配編碼過(guò)程的逆轉(zhuǎn)換，轉(zhuǎn)換公式如式（17）所示，通過(guò)該公式可直接計(jì)算出對(duì)應(yīng)的機(jī)器分配位置向量。若計(jì)算時(shí)出現(xiàn)可選機(jī)器數(shù)為1，則隨機(jī)生成該位置的解碼元素。

2.2.3 候選解位置向量的增碼與減碼

求解時(shí)候選解位置向量元素值會(huì)隨位置更新變化，當(dāng)路線選擇位置向量中的某個(gè)元素值改變時(shí)，可能會(huì)導(dǎo)致工件加工路線變化，任務(wù)的總工序數(shù)隨之變化，候選解維度改變。當(dāng)總工序數(shù)變化時(shí)，原始編碼長(zhǎng)度將不符合編碼規(guī)則，無(wú)法求解，所以在解碼時(shí)要考慮候選解位置向量的增碼與減碼。

增碼與減碼的操作方法為：每次編碼前測(cè)量候選解原始維度對(duì)應(yīng)的工序總數(shù)以及候選解路線選擇段對(duì)應(yīng)的實(shí)際工序總數(shù)。若原始工序總數(shù)小于實(shí)際工序總數(shù)，則進(jìn)行補(bǔ)碼，補(bǔ)碼數(shù)為實(shí)際工序總數(shù)與原始工序總數(shù)之差，使用隨機(jī)函數(shù)生成相應(yīng)數(shù)量的位置元素補(bǔ)碼。反之，采用位置向量末端減碼，減碼數(shù)為實(shí)際工序總數(shù)與原始工序總數(shù)之差。

2.3 自體交叉

在作業(yè)車間調(diào)度方案中，由于工序在不同機(jī)器上的排布順序不同，完成加工任務(wù)的時(shí)間也不同，所以工件在機(jī)器上的排布往往有較多空閑時(shí)間，造成時(shí)間上的浪費(fèi)。因此可以調(diào)整工序在機(jī)器上的排布，實(shí)現(xiàn)完工時(shí)間的優(yōu)化。

自體交叉的操作過(guò)程如圖5 所示。自體交叉操作通過(guò)選取候選解單個(gè)個(gè)體工序排序段上的兩個(gè)隨機(jī)位置進(jìn)行元素值互換，搜索排布中的空閑時(shí)間進(jìn)行插補(bǔ)，縮短完工時(shí)間。

圖5 候選解自體交叉過(guò)程Fig.5 Candidate solution self-crossover process

2.4 變鄰域變異

作業(yè)車間調(diào)度問(wèn)題中的鄰域結(jié)構(gòu)直接影響局部最優(yōu)解、全局最優(yōu)解的獲得。變鄰域搜索不但能避免大量無(wú)效搜索過(guò)程，還能擴(kuò)展當(dāng)前的搜索空間，避免陷入局部最優(yōu)，所以對(duì)MRFJSP 采用變鄰域搜索方法對(duì)候選解進(jìn)行變異搜索。根據(jù)變鄰域搜索方法中鄰域范圍特性（范圍介于［2，4］時(shí)搜索效率和穩(wěn)定性較好，范圍上限超過(guò)5 時(shí)搜索效率逐漸降低）［11］，結(jié)合問(wèn)題需要，合理設(shè)置鄰域范圍為［2，4］。

變鄰域變異的操作過(guò)程。先判斷候選解是否發(fā)生變鄰域變異；若發(fā)生變異，在鄰域范圍內(nèi)隨機(jī)搜索得到一組工件位置；對(duì)工件位置數(shù)據(jù)全排列獲得多個(gè)可行候選解；計(jì)算出這些候選解的能量值再與原候選解進(jìn)行比較；將最優(yōu)候選解作為變鄰域變異后的新候選解。變鄰域變異的操作過(guò)程如圖6所示。

圖6 候選解變鄰域變異過(guò)程Fig.6 Candidate solution variation neighborhood mutation process

2.5 變工序數(shù)候選解精英保留策略

由于MRFJSP 中各工件有多條加工路線且生成的候選解維度不同，需考慮維度變化對(duì)搜索空間的影響，簡(jiǎn)單地保留能量值較優(yōu)的個(gè)體是不合理的。為保證子代搜索空間中候選解的多樣性以及避免算法陷入局部搜索空間，提出一種變工序數(shù)候選解精英保留策略。在算法生成初始候選解時(shí)對(duì)候選解標(biāo)記維度，在候選解進(jìn)行位置更新、自體交叉和變鄰域變異時(shí)更新維度標(biāo)簽，完成每次迭代時(shí)保留能量值較優(yōu)的候選解和各維度標(biāo)簽中最優(yōu)候選解，作為下一次迭代的初始搜索空間。

2.6 算法流程

具體算法流程如圖7 所示。

圖7 改進(jìn)原子軌道搜索算法流程Fig.7 Improved atomic orbital search algorithm process

改進(jìn)原子軌道搜索算法首先對(duì)候選解位置進(jìn)行初始化并計(jì)算能量值，然后確定當(dāng)前原子的結(jié)合態(tài)、結(jié)合能及最低能級(jí)，并使用概率密度函數(shù)分配候選解到各虛擬層，計(jì)算虛擬層的結(jié)合態(tài)、結(jié)合能及層能級(jí)，更新對(duì)應(yīng)層候選解位置，使用自體交叉、變鄰域變異策略進(jìn)行增強(qiáng)搜索，通過(guò)變工序數(shù)精英保留策略保留最優(yōu)個(gè)體，重復(fù)上述過(guò)程直至滿足結(jié)束條件。

3 案例驗(yàn)證與分析

本文作者在Windows 10、CPU 2.40 GHz、內(nèi)存8 GB 的系統(tǒng)上采用MATLAB 2020b 編程實(shí)現(xiàn)IAOS 算法運(yùn)行。IAOS 算法參數(shù)設(shè)置為：迭代次數(shù)為300，候選解個(gè)數(shù)為200，原子軌道數(shù)為5；光子對(duì)電子的作用率0.1；交叉概率0.8；變異概率0.2。

為能夠合理驗(yàn)證前期建立的MRFJSP 模型，選取3 種規(guī)模的實(shí)例數(shù)據(jù)驗(yàn)證，以文獻(xiàn)［12］中某內(nèi)燃機(jī)車柔性生產(chǎn)作業(yè)車間的部分?jǐn)?shù)據(jù)作為基礎(chǔ)數(shù)據(jù)［13］。這3 組 數(shù)據(jù) 分別 對(duì)應(yīng)3、6、10 工 件在小、中、大規(guī)模問(wèn)題上的加工任務(wù)且工藝路線可選。其中六工件六機(jī)器中規(guī)模問(wèn)題的工藝路線信息如表2所示。

表2 中規(guī)模問(wèn)題的工藝路線信息Tab.2 Process route information for medium scale problems

表中Ril和Oij分別表示工件的可選工藝路線和工序，i（i＝1，2，…，6）表示工件號(hào)，l（l＝1，2，…，6）表示路線號(hào)，j（j＝1，2，…，6）表示工序號(hào)。表2 中工序Oij對(duì)應(yīng)的可選機(jī)器和加工時(shí)間如表3 所示。

表3 表2 中工序Oij對(duì)應(yīng)的加工信息Tab.3 Processing information corresponding to process Oij in Tab.2

3.1 模型求解

在FJSP 中各工件的加工路線固定、機(jī)器選擇柔性，無(wú)需考慮多個(gè)加工路線。在MRFJSP 中需要考慮加工路線柔性和機(jī)器選擇柔性，兩個(gè)模型的求解目標(biāo)均為完工時(shí)間最小化。為避免隨機(jī)性，采用3 種不同規(guī)模問(wèn)題對(duì)FJSP 模型和MRFJSP 模型進(jìn)行測(cè)試，各運(yùn)行10 次。中規(guī)模問(wèn)題中FJSP 模型選擇各工件的原始車間加工路線進(jìn)行求解，即參照表2 中的Ri1所對(duì)應(yīng)的6 條加工路線，其中i＝1，2，…，6。

經(jīng)典FJSP 模型和MRFJSP 模型對(duì)3 種不同規(guī)模問(wèn)題數(shù)據(jù)對(duì)進(jìn)行求解，解得的最優(yōu)調(diào)度結(jié)果如表4 所示，tbest、tavg和t分別表示最優(yōu)完工時(shí)間、平均完工時(shí)間和算法求解的平均運(yùn)行時(shí)間。兩模型中規(guī)模問(wèn)題調(diào)度甘特圖如圖8、9 所示。

圖8 FJSP 中規(guī)模問(wèn)題的最優(yōu)調(diào)度甘特圖Fig.8 The optimal scheduling Gantt chart for scale problems in FJSP

表4 模型對(duì)比實(shí)驗(yàn)結(jié)果Tab.4 Model comparison test results

3.2 求解結(jié)果對(duì)比分析

由表4 中兩模型實(shí)驗(yàn)結(jié)果可看出，對(duì)于不同規(guī)模問(wèn)題MRFJSP 模型求解得到的完工時(shí)間總體小于FJSP 模型。從小、中、大3 個(gè)規(guī)模問(wèn)題上進(jìn)行分析，使用MRFJSP 模型相較于FJSP 模型在完工時(shí)間上分別縮短了25.95%、25.6%和29.53%。對(duì)比圖8 和圖9 所示的最優(yōu)調(diào)度方案甘特圖可看出MRFJSP 模型的調(diào)度方案相較于FJSP 模型的排程時(shí)間更緊湊，排布更合理。結(jié)合實(shí)驗(yàn)結(jié)果和甘特圖綜合分析驗(yàn)證了MRFJSP 模型求解方法能有效求解多工藝路線的FJSP，相對(duì)于經(jīng)典的FJSP，文中提出的模型能有效縮短完工時(shí)間，提高生產(chǎn)效率。

圖9 MRFJSP 中規(guī)模問(wèn)題的最優(yōu)調(diào)度甘特圖Fig.9 The optimal scheduling Gantt chart for scale problems in MRFJSP

3.3 算法評(píng)價(jià)

將IAOS 與其他的元啟發(fā)式算法進(jìn)行實(shí)驗(yàn)對(duì)比，對(duì)比算法包括原子軌道搜索算法（AOS）［7］、遺傳算法（GA）［14］、變鄰域遺傳算法（GA-VNS）［12］。為避免隨機(jī)性，算法各運(yùn)行10 次，參考文獻(xiàn)［15］的對(duì)比方法加入提升率R，用來(lái)表示IAOS 相較于其他元啟發(fā)式算法的提升水平，其計(jì)算公式為（tIAOS，Best-tAOS，Best）／tIAOS，Best。各算法在不同規(guī)模下的求解結(jié)果如表5 所示，各算法求解中規(guī)模問(wèn)題的迭代曲線如圖10 所示。

圖10 中規(guī)模問(wèn)題算法迭代曲線Fig.10 Algorithm iteration curves for medium scale problems

表5 算法實(shí)驗(yàn)結(jié)果Tab.5 Algorithm experiment results

由表5 可知：從求解效果來(lái)看，對(duì)于小規(guī)模問(wèn)題，除GA 算法的求解結(jié)果不佳外，其他3 種算法都取得了較好的解，IAOS 算法相較于AOS、GA 和GA-VNS算法的平均提升率分別提升了1.23%、1.64%和0.81%；對(duì)于中規(guī)模問(wèn)題的求解，IAOS 搜索到的結(jié)果最好且與其他搜索算法的最優(yōu)解拉開(kāi)了一定的差距，相較于AOS、GA 和GA-VNS 算法的平均提升率分別提升了16.2%、27.12%和13.79%，由此體現(xiàn)出IAOS 改進(jìn)的有效性以及在求解多工藝路線FJSP 上的優(yōu)越性；對(duì)于大規(guī)模問(wèn)題，AOS 和GA 算法的求解結(jié)果不理想，求解能力明顯下降，GA-VNS算法雖然在大規(guī)模問(wèn)題上仍有一定的求解能力，但求解結(jié)果不如IAOS 優(yōu)秀，證明了IAOS 算法在求解復(fù)雜度較高問(wèn)題時(shí)的高效性。

由圖10 可知：對(duì)于中規(guī)模問(wèn)題各算法在運(yùn)算初期就能快速尋優(yōu)，但在迭代50 次后明顯能看出AOS、GA 和GA-VNS 算法尋優(yōu)能力均有所下降，IAOS 算法在迭代50 次后雖尋優(yōu)速度減慢，但仍然具有一定的搜索能力。從收斂性上分析，IAOS、AOS、GA 和GA-VNS 算法分別在迭代175、38、57 和206 次時(shí)收斂。IAOS 雖然收斂速度較慢，但求得了優(yōu)于其他算法的解；AOS 收斂最快，獲得了比較好的求解結(jié)果；GA 收斂也較快，但求得的結(jié)果最差；GA-VNS 收斂速度最慢，但其對(duì)GA 的改進(jìn)有效，也取得了比較好的解。綜上可看出：雖然IAOS 收斂速度慢于AOS 和GA，時(shí)間復(fù)雜度略高于其他算法，但I(xiàn)AOS 的改進(jìn)措施有效，在算法搜索的開(kāi)始階段就能快速找到優(yōu)于其他算法的解，能有效跳出局部最優(yōu)，找到更好的解。

綜合來(lái)看，IAOS 算法在整體求解過(guò)程中尋優(yōu)能力較好，應(yīng)用于不同規(guī)模問(wèn)題時(shí)的適用性較強(qiáng)，尤其是在求解復(fù)雜度較高的大規(guī)模問(wèn)題時(shí)IAOS 算法比其他算法表現(xiàn)出更好的尋優(yōu)能力。因此采用IAOS 算法進(jìn)行多工藝路線柔性作業(yè)車間調(diào)度優(yōu)化是可行的。

4 結(jié)論

（1）本文作者分析了工件的多工藝路線與柔性作業(yè)車間調(diào)度之間的聯(lián)系以及特點(diǎn)，建立了多工藝路線柔性作業(yè)車間調(diào)度模型，通過(guò)實(shí)驗(yàn)驗(yàn)證了多工藝路線柔性作業(yè)車間調(diào)度模型的有效性。

（2）設(shè)計(jì)了一種改進(jìn)原子軌道搜索算法，引入一種三層編碼方式使其適用于求解MRFJSP；引入自體交叉和變鄰域變異增強(qiáng)局部搜索并避免陷入局部最優(yōu)；迭代過(guò)程中設(shè)計(jì)了變工序數(shù)精英保留策略，擴(kuò)大了搜索空間，使算法的求解質(zhì)量和效率得到提高。

（3）采用3 組不同規(guī)模MRFJSP 對(duì)改進(jìn)原子軌道搜索算法和其他3 種元啟發(fā)式算法的求解結(jié)果進(jìn)行比較分析，驗(yàn)證了改進(jìn)原子軌道搜索算法的可行性和適用性。