基于果蠅協(xié)同算法求解雙目標(biāo)混裝柔性作業(yè)車間分批調(diào)度問題

關(guān)鍵詞：混裝柔性作業(yè)車間；雙層聯(lián)動；分批策略；果蠅協(xié)同搜索算法 中圖分類號：TP18 文獻標(biāo)志碼：A 文章編號：1001-3695（2025）07-020-2072-08 doi：10.19734/j.issn.1001-3695.2024.12.0514

Abstract：This paper studied the mixed-model assmblflexible job-shop scheduling problem with lot streaming，considering theclose interactionsamongproduction，transportation，inventory，andasembly.Theobjectivewasto minimizemakespan andtotalcost，nditproposedabi-levelinteractivemultiobjectivehbridalgorithm.Temulti-ojectiveparticleswaroptimizationcombinedwiththefruitflycooperationsearchoptimizationalgorithm（FCSOA）．Theouterlayerdeterminedtheoptimalbatchingstrategy，whiletheinnerlayercomputedtheoptimalschedulingplanunderthestrategyandconverteditintofitnessvalues tofeedbacktotheouterlayer，therebyenhancing solutionperformance.TheFCSOAimprovedthetraditionalfruit flyoptimizationalgorithmbyincorporatingthecollborativesearchprocess，itadopted theimprovedprecedenceoperation crosoverandmulti-point preservativecrossover tooptimizejobsequencingandmachineallocation，respectively.Finaly，it generated10 test instances basedonreal production datafrom amedical device enterprise forextensive experimentation.The comparison with multiple existing algorithms show that theFCSOAachieves fasterconvergence speedand moreevenlydistributed Paretofront solutions.Thisresearch provides anewefectivesolution tosolvethe mixed-modelassemblyflexible jobshop scheduling problem with lot streaming，offering high practical value.

Keywords：mixed-modelassemblyflexible workshop；bi-level interactive；batching strategy；fruitflycooperationsearchoptimizationalgorithm

0 引言

隨著工業(yè)全球化進程的推進，對控制產(chǎn)品制造周期的要求也不斷提高，制造業(yè)發(fā)展伴隨著越來越多的約束與挑戰(zhàn)?，F(xiàn)行中小型制造企業(yè)客戶訂單通常存在多品種、小批量、變化性等特征，而傳統(tǒng)的生產(chǎn)模式則存在制造周期長、車間設(shè)備利用率低、生產(chǎn)成本與風(fēng)險高的缺陷[1.2]。因此企業(yè)為應(yīng)對競爭環(huán)境通常采取分批生產(chǎn)策略，將訂單所需工件拆分為多個批次進行加工運輸及裝配。該過程根據(jù)拉式生產(chǎn)規(guī)則以需求倒逼生產(chǎn)，裝配環(huán)節(jié)采用多產(chǎn)品混流裝配，且其加工過程為柔性加工，即機器能夠加工不同的工序，這被定義為混裝柔性作業(yè)車間分批調(diào)度問題（mixed-model assembly flexible job-shop schedulingproblemwithlotstreaming，MAFJSP-LS）。顯然混裝柔性作業(yè)車間分批調(diào)度是NP-hard問題，與傳統(tǒng)裝配車間調(diào)度問題相比，需要將一批具有一定數(shù)量的工件進行分批，率先完成的批次可以先進入裝配環(huán)節(jié)，生產(chǎn)和裝配的時間相對分散，大大提高了機器的利用率，但同時也會增加運輸頻率以及機器的切換頻率，導(dǎo)致成本提高[3，4]。針對傳統(tǒng)柔性生產(chǎn)模式，分批調(diào)度問題是目前的研究熱點。Li等人[5]考慮將總需求分成幾個大小不等但一致的子批，基于人工蜂群的改進生物啟發(fā)算法求解該兩階段問題的優(yōu)化策略。Zhang等人研究了具有相鄰兩個工作區(qū)域的柔性制造系統(tǒng)的生產(chǎn)調(diào)度問題，事先考慮批次流，提出分布式蟻群系統(tǒng)來解決問題。曾強等人[提出了一種批量生產(chǎn)柔性作業(yè)車間多目標(biāo)精細化調(diào)度方法，建立了以時間和成本最低為目標(biāo)的等量分批柔性作業(yè)車間調(diào)度優(yōu)化模型。黎英杰等人8針對多層級裝配作業(yè)車間中差異化零部件的加工裝配進度協(xié)同困難的問題，通過零部件合理分批來提升車間的流動性給出了分批調(diào)度模型。

然而隨著制造需求的進一步提升，客戶需求的多樣化和裝配作業(yè)的標(biāo)準(zhǔn)化要求提高，生產(chǎn)、運輸和裝配三個階段間的影響成為優(yōu)化重點，目前分批調(diào)度的研究從主要針對傳統(tǒng)柔性生產(chǎn)模式[9-11]延伸到更為復(fù)雜的混合柔性生產(chǎn)[12＼～14]，分批要求會將問題劃分為兩個及以上子問題，考慮多階段聯(lián)合[15]、分布式情況[16]，模型的復(fù)雜度增大，求解的和優(yōu)化的難度和空間也相應(yīng)提高。除了加工需要達到的調(diào)度目標(biāo)所需滿足的特定約束條件外，還需考慮運輸和裝配過程，以及多種產(chǎn)品或零部件混流裝配的情況，形成了以柔性生產(chǎn)為基礎(chǔ)的混裝作業(yè)車間分批調(diào)度問題（MAFJSP-LS），通過多產(chǎn)品混流裝配，達到低成本、高質(zhì)量和高效率的目標(biāo)。Wong等人1在裝配作業(yè)車間調(diào)度問題（AJSSP）中考慮批分割，研究批流（LS）技術(shù)，將作業(yè)分割成許多較小的子作業(yè)，以便在不同階段并行處理，提高系統(tǒng)性能。Ren等人[18]在加工裝配系統(tǒng)中，開發(fā)了一個混合集成數(shù)學(xué)模型，以提高生產(chǎn)效率并最大限度地減少能源消耗。Wang等人[19]針對離散制造問題，提出了一種集成作業(yè)車間調(diào)度和裝配順序規(guī)劃（IJSSASP）方法，實現(xiàn)了零件加工順序和裝配順序的同時優(yōu)化。魯建廈等人[20]綜合考慮混流裝配與零部件加工的集成優(yōu)化以及外協(xié)云任務(wù)與自制任務(wù)的協(xié)同調(diào)度，建立了多目標(biāo)車間調(diào)度模型，實現(xiàn)最小化最大完工時間、均衡化零部件生產(chǎn)和最大化零件車間機器利用率。

為求解多目標(biāo)多約束混裝柔性作業(yè)車間所建立的復(fù)雜模型，現(xiàn)有研究大多使用并改進元啟發(fā)式算法，提出并發(fā)展了混合遺傳算法（HGA）和混合粒子群算法（HPSO）求解。Fattahi等人[21]建立具有裝配作業(yè)的柔性作業(yè)車間調(diào)度問題的數(shù)學(xué)模型，提出了一種新的混合粒子群優(yōu)化與并行變量鄰域搜索（HPSOPVNS）算法。Lyu等人[22]提出了一種基于遺傳調(diào)控網(wǎng)絡(luò)的新型測序方法，解決同時生產(chǎn)多種產(chǎn)品的裝配線的混裝作業(yè)模型。Li等人[23基于分解的多目標(biāo)進化算法（MOEA/D）針對混合流車間調(diào)度批次流問題，提出了一種改進算法命名為PH-MOEAD，考慮可變子批次約束，實現(xiàn)時間、成本等目標(biāo)。Zhou 等人[24]建立了一種多目標(biāo)干擾與修復(fù)策略增強隊列智能（MDRCI）算法來處理多目標(biāo)問題，求解汽車混合裝配線中移動機器人的零件投料任務(wù)節(jié)能調(diào)度方案。Song等人[25]提出了一種有效的基于超啟發(fā)式的模因算法（HHMA），用于求解以最大完成時間最小為目標(biāo)的分布式裝配置換流水車間調(diào)度問題。在企業(yè)實際生產(chǎn)過程中，分批調(diào)度使得生產(chǎn)環(huán)節(jié)和裝配環(huán)節(jié)穿插，因此求解MAFJSP-LS問題具有重要的應(yīng)用價值，適用于多行業(yè)生產(chǎn)場景，多目標(biāo)進化算法求解也更為穩(wěn)定和適配。

綜上所述，盡管學(xué)者們不斷完善對混裝柔性作業(yè)車間生產(chǎn)分批問題的研究，提出多種智能優(yōu)化算法，但在有效提升效率、避免錯誤的同時，綜合考慮由于運輸頻率和機器切換頻率上升而提高成本，提出決策分批策略上尚未有方案獲得最優(yōu)解，并且基本采用單一算法對分批調(diào)度問題進行優(yōu)化，忽略了分批策略和調(diào)度方案之間的相互影響。本文研究兩者之間的平衡，以最小化完工時間和生產(chǎn)總成本為聯(lián)合優(yōu)化目標(biāo)，提出了多目標(biāo)粒子群優(yōu)化算法（MOPSO）聯(lián)合果蠅協(xié)同搜索算法（FCSOA）的雙層算法，其中FCSOA是基于FOA添加相應(yīng)的改進機制建立的，針對多目標(biāo)混裝柔性作業(yè)車間調(diào)度問題將問題劃分為內(nèi)外兩層，外層目標(biāo)為獲得分批策略，內(nèi)層目標(biāo)為分批策略下的調(diào)度方案，內(nèi)外兩層互相聯(lián)動影響，計算獲得最優(yōu)分批策略以及最優(yōu)調(diào)度方案。打破生產(chǎn)與裝配之間的約束壁壘，適應(yīng)柔性動態(tài)生產(chǎn)現(xiàn)場，提前開啟裝配環(huán)節(jié)以有效提高機器的利用率，控制總成本。

1 MAFJSP-LS建模

1.1 問題描述

本文針對混裝柔性作業(yè)車間分批調(diào)度問題（MAFJSP-LS），符合目前中小型制造企業(yè)面臨的多品種、小批量、變化性等特征現(xiàn)狀，考慮到制造周期中的生產(chǎn)、運輸、裝配多環(huán)節(jié)，建立模型將不同環(huán)節(jié)的時間、成本以及資源限制納入約束條件，貼合生產(chǎn)實際。

首先考慮拉式生產(chǎn)根據(jù)訂單產(chǎn)品的數(shù)量要求，將產(chǎn)品裝配所需要的零部件進行分批，且單位子批的某零部件數(shù)量等于裝配一個成品所需的該零部件數(shù)量，即子批的總數(shù)就等于訂單產(chǎn)品需求數(shù)。按照批次和工件工序要求選擇車間和機器進行加工，當(dāng)成品裝配所需的零部件根據(jù)批次加工并且有一定數(shù)量齊套后，便通過轉(zhuǎn)運選擇車間和機器進行裝配。其中生產(chǎn)和裝配的過程符合裝配柔性作業(yè)車間規(guī)則，每個車間分別配備一系列具有加工不同產(chǎn)品能力的機器以及一條裝配作業(yè)線，每道工序遵循工藝約束順序且可以選擇不同的機器進行加工。由于進行分批生產(chǎn)，存在率先生產(chǎn)完成的工件無法立刻進入裝配環(huán)節(jié)的情況，所以在加工和裝配兩階段間設(shè)立中間庫，根據(jù)完工時間和開始裝配時間計算產(chǎn)生的庫存成本，當(dāng)且僅當(dāng)相關(guān)產(chǎn)品在裝配階段所需全部物料齊套，才啟動裝配，同時分批會增大機器的模式轉(zhuǎn)換頻率，增加準(zhǔn)備時間以及加工到裝配過程的轉(zhuǎn)運次數(shù)，產(chǎn)生更多的加工成本和運輸成本。

基于加工和裝配的相關(guān)性，遵循時間特點建立算法模型對生產(chǎn)進行合理分批，相對于可變分批策略，等量分批策略為實踐中最直接、采用率最高的方式，能有效節(jié)省拆分設(shè)置成本，因此本文基于等量分批策略，考慮分布車間的聯(lián)合調(diào)度。首先根據(jù)訂單獲得生產(chǎn)計劃，以最小化最大完工時間和總成本最低為目標(biāo)分析不同分批策略的可行性優(yōu)越性，分批生產(chǎn)流程如圖1所示，并提出以下假設(shè)：a）相同的工件在不同的車間機器上加工裝配以及庫存的成本相同；b）當(dāng)且僅當(dāng)零部件生產(chǎn)齊套并且存在裝配線處于空閑狀態(tài)時立刻進行運輸裝配；c）各工件的優(yōu)先級相同，不會出現(xiàn)需要搶險生產(chǎn)的情況；d）分批結(jié)束后，各批次的工件種類相同，加工一旦開始就不會中斷且不能再次分批。

1.2模型符號及參數(shù)說明

為了便于對求解問題進行準(zhǔn)確的描述，引入下列符號和變量： ：P_n 表示訂單的產(chǎn)品集共 N 種產(chǎn)品； p_nj 表示產(chǎn)品 P_n 組裝所需的零部件類型 j 的單位需求批數(shù)； q_njs 表示產(chǎn)品 n 直屬的零部件 j 的第 s 批包含的單位批大?。?Q_njs 表示產(chǎn)品 Ω_n 直屬的零部件j 的第 s 批； S_nj 表示產(chǎn)品 n 直屬的零部件 j 子批分批數(shù)量； ST_njk 和 CT_njk 分別表示產(chǎn)品 n 直屬的零部件 j 子批工序 k 的加工開始時間和結(jié)束時間； ST_njs 和 CT_njs 分別表示產(chǎn)品 p 直屬工件 j 某批次的加工開始時間和完工時間； ST_p 和 CT_p 分別表示產(chǎn)品 p 開始裝配和結(jié)束裝配的時間 t_{j，i，w，m} 表示工件 j 的第 i 道工序在車間 w 的第 m 臺機器上加工所需時間； t_p，w 表示產(chǎn)品 p 在所選車間 w 裝配所需的時間； k_j、k_p、k_d 分別表示加工工件 j 對應(yīng)的單位時間所需成本系數(shù)、單位時間裝配成本系數(shù)以及每次運輸?shù)某杀鞠禂?shù)； v_j 表示工件的單位時間庫存成本。

定義的決策變量有 ：μ_j，p 表示若工件 j 屬于產(chǎn)品 p 則為1，否則為 0：θ_pnj，w 表示如果 p_nj 批次在工車間 w 進行生產(chǎn)則為1，否則等于 0;x_{j，i，w，m} 表示若工件 j 的第 i 道工序在車間 w 的第 ?_m 臺機器上加工則為1； α_{j，s，f，f} 表示工件 j 的第 s 批加工完畢后進入裝配時更換車間則為1，如果加工和裝配在同一個車間則為 0 。

1.3 目標(biāo)函數(shù)和約束條件

MAFJSP-LS所研究的優(yōu)化目標(biāo)是：最小化最大完工時間和最小化生產(chǎn)過程中的總成本。目標(biāo)函數(shù)如式（1）（2）所示。

min（T）=maxCT_p

min（C）=PC+AC+IC+DC

其中：總成本包括加工過程成本 PC 、裝配過程成本 AC 、工件庫存成本 IC 以及運輸成本 DC 。

約束條件以及說明如下：

式（3） 零部件的單位批，即 勺零部件，又等于總單位批數(shù)所劃分的所有子批大小之和 ，j 為零部件的類型數(shù);式（4）表示每批次零部件數(shù)量，分批后零部件需求若無法被批數(shù)整除，則前幾批包含的數(shù)量為需求除以分批數(shù)取整數(shù)，最后一批取相除后的余數(shù)作為子批數(shù)量；約束條件式（5）＼～（7）表示所有零件子批在零時刻均能被加工，工序需符合緊前緊后工序邏輯約束；式（8）（9）表示一種子批的一道工序只能在一個車間的一臺機器上加工，并且工件所屬的產(chǎn)品有且只有一個。約束條件式（10）＼～（12）表示產(chǎn)品裝配工序在其直屬工件的相應(yīng)齊套需求子批批量完工之后開始，一次性裝配數(shù)量根據(jù)直屬工件的最小 q_njs 以及中間庫的在庫直屬工件數(shù)量決定，如果中間庫中某產(chǎn)品的所有需求工件都有庫存，則根據(jù)其中最小的工件庫存數(shù)量進行集體轉(zhuǎn)運，所有直屬工件都扣除該個數(shù)，再等待下一輪工件齊套，裝配完工時間則為開始時間加上選擇的裝配車間所需裝配時間乘上裝配個數(shù)，并且單批次只能在一個工廠進行生產(chǎn)。式（13） ～ （15）分別表示工件的加工過程會產(chǎn)生相應(yīng)的加工過程成本PC，和當(dāng)某產(chǎn)品的所有直屬工件齊套之后，經(jīng)過轉(zhuǎn)運開始裝配則會產(chǎn)生裝配過程成本AC，以及當(dāng)工件的部分批次率先完工，但所屬產(chǎn)品的直屬工件并未齊套，則該批工件進入中間庫，產(chǎn)生相應(yīng)的工件庫存成本 IC

在式（16）中， CT_njs 則是產(chǎn)品 p 直屬工件 j 某批次的完工時間，假設(shè)產(chǎn)品 p 緊接著 p^′ 進入同一道裝配線，其中裝配的開始時間取決于所需工件的完工時間 CT_njs 以及上一道產(chǎn)品裝配完工時間 CT_p^′ 的較大值。式（17）表示工件各批次完工后進入中間倉以及某產(chǎn)品的直屬工件齊套后通過轉(zhuǎn)運進入裝配階段都會產(chǎn)生相應(yīng)的運輸成本DC，而運輸成本顯然與分批策略分批數(shù)量呈負相關(guān)，分批數(shù)量 S_nj 越大，運輸成本越高。

2 雙層聯(lián)動算法設(shè)計

2.1 雙層算法聯(lián)動

為了更好地選擇分批策略，本文設(shè)計采用雙層混合算法聯(lián)動迭代優(yōu)化，通過計算獲得最佳分批策略以及該策略下的最佳調(diào)度方案。雙層算法更具有針對性，可以將問題細化，直擊目標(biāo)，對于MAFJSP分批問題既要提出最優(yōu)分批策略，又要實現(xiàn)分批策略下的最優(yōu)調(diào)度方案，將問題細化分為兩層并采用雙層算法。外層目標(biāo)為分批策略，選用多目標(biāo)粒子群算法（MOP-SO）進行優(yōu)化迭代；內(nèi)層則通過果蠅協(xié)同搜索算法（FCSOA）針對分批策略下的調(diào)度方案進行迭代優(yōu)化，獲得每個分批策略下的最優(yōu)調(diào)度方案以及該方案的最大完工時間和總成本，并作為適應(yīng)度反饋給外層，計算流程如圖2所示。雙層算法分工明確且具有強耦合性，相較一般的分批問題解決辦法的單一算法，雙層算法能夠結(jié)合不同算法的優(yōu)勢兼顧內(nèi)外層不同目標(biāo)特性獲得更突出的結(jié)果。

其中外層的多目標(biāo)粒子群算法（MOPSO）的每個粒子對應(yīng)為一個分批策略，以時間和成本為目標(biāo)，通過粒子間共享信息，向全局最佳粒子和每代種群自己的最佳位置移動，找到能夠平衡雙目標(biāo)的帕累托最優(yōu)解集，通過迭代不斷更新粒子的位置和速度，最終選取最合適的分批策略。MOPSO算法結(jié)構(gòu)相對簡單，適應(yīng)性強并且收斂速度快、全局搜索能力強，能夠在保證準(zhǔn)確性的同時減小雙層算法的復(fù)雜度和實現(xiàn)難度。

內(nèi)層算法對果蠅算法進行優(yōu)化改進，F(xiàn)OA算法不同于其他群體智能算法，在坐標(biāo)系兩個方向上二維搜索，嗅覺和視覺搜索機制使其尋優(yōu)更為簡潔快速，但在處理高維復(fù)雜優(yōu)化問題時，收斂速度和全局搜索能力不足，容易陷入局部最優(yōu)解。因此，F(xiàn)OA需要通過引入新的機制更好地適應(yīng)多目標(biāo)優(yōu)化和動態(tài)環(huán)境。受到自然界群體通過信息交流來提高覓食效率的行為啟發(fā)，在傳統(tǒng)果蠅優(yōu)化算法的基礎(chǔ)上加入?yún)f(xié)同搜索策略共享果蠅位置信息，形成果蠅協(xié)同搜索算法（FCSOA）。該算法主要包含嗅覺搜索、視覺搜索和協(xié)同搜索三個主要步驟，具有較強的局部搜索能力，更好的全局尋優(yōu)性能和較快的收斂速度。

算法具體流程如下：

a）根據(jù)合理的分批原則生成初始化外層種群；b）每個個體都進入內(nèi)層循環(huán)，生成該策略下的內(nèi)層初始種群即分批策略下的調(diào)度方案；c）每個果蠅個體進行分裂生成亞種群，計算適應(yīng)度值，每個亞種群中最好的個體成為新的種群個體，并且更新全局最優(yōu)個體；

d）采用改進的優(yōu)先操作交叉（IPOX）和多點保存交叉（MPX），每個果蠅個體以一定概率和全局最優(yōu)個體或者隨機選擇個體進行交叉，結(jié)合原種群計算適應(yīng)度值，按二元錦標(biāo)賽的方法選出新種群；

e）重復(fù)執(zhí)行步驟c）d），直到滿足終止條件，輸出最優(yōu)解，并將其傳回外層作為外層的適應(yīng)度；

f外層種群全部計算得到適應(yīng)度后，找到種群的最優(yōu)解并更新全局最優(yōu)個體，以一定概率向局部最優(yōu)個體和全局最優(yōu)個體飛行，獲得新的外層種群；

g）重復(fù)執(zhí)行步驟從b）＼～f），直到滿足終止條件，輸出最優(yōu)解。

初始化參數(shù)，i=0 多目標(biāo)粒子群優(yōu)化算法（MOPSO） 果蠅協(xié)同搜索！隨機生成N個分批策略 初始化參數(shù)， g=0 一 算法（FCSOA）是否滿足停止條件？ 輸出最佳分批策略 隨機生N個調(diào)群分批否i=i+1 計算度最大完工 以出最佳調(diào)度本 是 是否滿足停止條件？得所策的優(yōu)調(diào) 嗅覺搜索 在每個成亞產(chǎn)S只獲得所批策的最優(yōu)調(diào)度解 1 視覺搜索 每個果最群著亞種 g=g+1 1↓向，優(yōu)和最 協(xié)同搜索 尋找局量優(yōu)量蠅，對每個果

2.2 編碼與解碼

MAFJSP-LS屬于多階段復(fù)雜調(diào)度問題，一個完整的可行解需要包括對所有工件的分批策略、分批策略下的調(diào)度方案，調(diào)度方案有包括工件各批次生產(chǎn)的車間選擇、機器選擇和加工順序。前期研究對柔性作業(yè)車間以及分批調(diào)度問題的研究和解決方案基本都采用了單一算法對分批調(diào)度問題進行優(yōu)化，即編碼方案會將分批策略和調(diào)度方案整體作為迭代優(yōu)化對象，而忽略它們本身之間的相互影響，同一種分批策略下會有多種調(diào)度方案呈現(xiàn)不同的時間、成本結(jié)果，整體迭代則非常容易陷入局部最優(yōu)，影響結(jié)果的準(zhǔn)確性?？紤]分批問題的復(fù)雜性，為了能夠充分展現(xiàn)有效信息，強調(diào)分批策略與策略下調(diào)度方案的關(guān)聯(lián)性，使優(yōu)化更加全面具體，不易陷入局部最優(yōu)，編碼采用內(nèi)外聯(lián)動反饋的機制，方式如圖3所示，外層編碼為分批策略，即將每個工件等量分為多少批，內(nèi)層編碼向外層反饋該分批策略下最優(yōu)解的時間 T 和成本 C 內(nèi)層編碼分為五層，第一層為工序?qū)覺_j ，用 j-s 表示工件 j 的第 s 批，出現(xiàn)幾次就有幾道工序；第二層為分批策略層 X_s 對應(yīng)的工件分批數(shù)量，策略來源于外層編碼；第三層代表車間層 X_w ，為簡化計算，其中某批次加工完成進入中間庫后，所屬產(chǎn)品的工件齊套則裝配默認在最后一個完工的工件批次所選擇的車間進行；第四層為機器層 X_m ，代表選擇該工序可用機器的序號，在計算過程轉(zhuǎn)為編號，不同的機器選擇方案會產(chǎn)生不同的時間成本結(jié)果。以表1為例，表中數(shù)據(jù)包含兩種產(chǎn)品五種工件兩個車間，其中工件1、2直屬于產(chǎn)品1，工件3、4、5直屬于產(chǎn)品2，工序數(shù)量為2，每個車間配備4臺加工機器和1條裝配線，工序可選擇車間及該車間可加工該工序的機器數(shù)[1，3]， O₂₁ 表示工件2的第1道工序。編碼示例如圖3所示。由圖可知，該編碼的工件3屬于產(chǎn)品1被分為兩批，其第2批次的第2道工序在第1個車間可選的第二臺機器即機器4上進行加工。

解碼過程首先根據(jù)車間層找到工序?qū)?yīng)的車間再根據(jù)機器層找到選擇的機器，工件加工產(chǎn)生加工成本，完成所有工序的工件運輸進入中間庫產(chǎn)生運輸成本，工件率先齊套的產(chǎn)品優(yōu)先進入裝配階段，產(chǎn)生裝配成本，所有成本之和即為總成本 c ，以及選擇不同車間機器產(chǎn)生加工裝配的總時間 T

2.3果蠅協(xié)同搜索算法

1）嗅覺搜索對于種群中每一個果蠅個體在其周圍生成s 只果蠅，構(gòu)建一個果蠅亞種群，如圖4所示，獲得亞種群的每個個體對于目標(biāo)食物的氣味濃度的表達式如下：

Smell_i=fitness（S_i）

式（18）是亞種群個體產(chǎn)生過程;在果蠅個體具體位置附近更新隨機距離，通過式（19）計算氣味濃度判定值 S_i ，進而代入適應(yīng)度函數(shù)獲得該個體的氣味濃度 Smell_i 。

對于MAFJSP-LS具體來說，就是通過交換果蠅群序列中隨機選擇的兩個工序的第一個操作的位置，產(chǎn)生一個新的果蠅。交換后，如果為兩個選定工序的操作更改了先前分配的機器工廠，且可能改變了對應(yīng)工件的前后工序順序，則執(zhí)行修復(fù)過程以恢復(fù)機器分配，找到所有選中的相同工件批次，確定交換后的工序，按照開始時符合工序順序要求的機器分配進行修復(fù)，過程如圖5所示。然后計算亞種群個體的完工時間和總成本作為其氣味濃度。

2）視覺搜索生成果蠅亞種群后，該亞種群中的每個果蠅個體都朝著亞種群中最好的果蠅飛去，即生成的亞種群中最好的個體替換原果蠅個體。

3）協(xié)同搜索在果蠅優(yōu)化算法中加入?yún)f(xié)同搜索過程來增強優(yōu)化，使其具備更好的全局搜索能力，有效尋找全局最優(yōu)解，采用改進的優(yōu)先操作交叉（IPOX）和多點保存交叉（MPX），分別實現(xiàn)作業(yè)順序的協(xié)同搜索和機器分配，首先尋找全局最佳果蠅個體，通過IPOX和MPX對每個果蠅組進行優(yōu)化。與IPOX不同的是，MPX使用信息接受概率（informationacceptanceprobability，P）來確定劣勢果蠅群體從優(yōu)勢果蠅群體那里學(xué)習(xí)到多少信息。交叉變異過程可以根據(jù)環(huán)境靈活調(diào)整參數(shù)保持較好的性能，同時能夠在搜索過程中保持解的多樣性和可靠性，從而避免過早收斂到局部最優(yōu)解。

IPOX和MPX的具體改進過程如下。

改進后的IPOX過程：

a）對于種群中各果蠅群 F_f 的每一個操作序列向量 （ν₁） ，選擇全局最佳果蠅個體 bFfg 的每一個操作序列向量 （ν_b1 ）；

b）將所有作業(yè)劃分為兩個非空集 G₁ 和 G₂ 。具體來說，對于每個作業(yè) X_j（j=1，2，…，n） ，生成均勻隨機數(shù) rand∈（0，1） 。若 rand

j 加入到 G₁ ；否則加入 G₂ 。如果 G₁ 或 G₂ 為空，則隨機選擇一個作業(yè)并將其添加到空集中。

c）將 G₁ 中作業(yè)的操作拷貝到與 ν_b1 相同的位置，其余操作按照 ν₁ 相同的順序拷貝，從而得到子代的一個操作序列向量（voffi）。圖6為上述IPOX過程。

改進后的MPX過程：

a）對于種群中各果蠅群 F_f 的每一個車間、機器分配向量（ν₂） ，選擇全局最佳果蠅個體bFfg的每一個車間、機器分配向量 （ν_b2） 。

b）對于每一個操作工序 O_ij（i=1，2，…，n;j=1，2，…，m） ，其中 i 為工件數(shù) Δ，j 為工序數(shù)，生成均勻隨機數(shù) rand∈（0，1） 。若 rand

2） 拷貝給子代的車間、機器分配向量 （νoff₂ ）；否則分配給子代與全局最佳果蠅群相同的車間、機器分配向量 （ν_b2） 。圖7為上述MPX過程。

3 實驗與分析

醫(yī)療器械行業(yè)作為中小型制造業(yè)的一大典型，低、小、散是中國醫(yī)療器械行業(yè)的重要特征。隨著社會經(jīng)濟快速發(fā)展，人民生活水平提高，醫(yī)療器械行業(yè)也得到了巨大的關(guān)注與迅速發(fā)展，人們對相關(guān)產(chǎn)品的功能和性能也有了越來越高的要求，導(dǎo)致產(chǎn)品生產(chǎn)活動的復(fù)雜性大大提升，然而傳統(tǒng)生產(chǎn)模式制造周期長、車間利用率低無法滿足企業(yè)所需面臨的復(fù)雜生產(chǎn)活動。因此本文以武漢某醫(yī)療器械企業(yè)生產(chǎn)數(shù)據(jù)為實例，其生產(chǎn)過程符合多產(chǎn)品混裝柔性作業(yè)車間規(guī)則，依托真實生產(chǎn)數(shù)據(jù)進行優(yōu)化分析，更具有實際參考價值。

3.1算例

隨機生成10組算例（以Brandimarte算例中的MKO2、MK03、MK08、MK12、MK15為參考，結(jié)合某醫(yī)療器械企業(yè)實際生產(chǎn)情況調(diào)整），如表2所示。

表2算例規(guī)模Tab.2Algorithm size

以算例J5M4P2W2為例，代表5個工件分別隸屬于兩個產(chǎn)品，車間數(shù)為2每個車間有4臺機器，工件的工序數(shù)為1或2，工序的加工時間在[2，6]。與目標(biāo)時間和成本相關(guān)的參數(shù)設(shè)置如表3所示。

3.2算法參數(shù)確定

不同的算法參數(shù)設(shè)置對雙層混合算法多目標(biāo)粒子群算法（MOPSO）和果蠅協(xié)同搜索算法（FCSOA）的性能影響較大，其中兩層的種群規(guī)模、外層MOPSO的加速度因子、內(nèi)層FCSOA的亞種群分裂數(shù)、信息接受概率 P 是最為主要的算法影響因素。為了更好地確定參數(shù)值，本文設(shè)計正交實驗對比三個水平的參數(shù)設(shè)置，以算例J10M5P3W2為例進行計算，并通過正交表進行羅列，為了避免實驗結(jié)果的偶然性、隨機性，每組實驗都進行了20次運行，取運行目標(biāo)結(jié)果的平均值作為實驗結(jié)果[15]，參數(shù)水平配置如表4所示，正交實驗結(jié)果如表5所示。

通過對表中的實驗結(jié)果進行分析，可以獲得不同參數(shù)水平對實驗結(jié)果的影響程度，對同一參數(shù)的同一水平出現(xiàn)的所有實驗結(jié)果取平均值作為該參數(shù)及該水平下的結(jié)果，值越小則說明算法性能越好，通過繪制不同目標(biāo)下不同參數(shù)水平獲得結(jié)果均值的折線圖，如圖8所示，可以更直觀地獲得參數(shù)水平性能差異，因此選擇參數(shù)設(shè)置為：種群規(guī)模 Pop₁…Pop₂ 為50、60，加速因子 c₁、c₂ 選用0.4、0.5，亞種群分裂數(shù)為3，信息接收概率為0.7。

3.3 實驗結(jié)果分析

為了驗證FCSOA求解上述模型的有效性和優(yōu)越性，選擇了優(yōu)化前的普通果蠅算法FOA、分批問題中常用的NSGA-I算法，以及求解多目標(biāo)柔性作業(yè)車間調(diào)度問題的前沿算法改進灰狼算法 IGWO^[26] 進行計算對比分析。以反世代距離（IGD）作為評價指標(biāo)，IGD是能夠提供算法收斂性和分布性情況的綜合度量，主要通過計算每個在真實Pareto前沿面上的點（個體）到算法獲取的個體集合之間的最小歐幾里德距離之和來獲得，其表達式為

將10個算例各獨立運行20次，取指標(biāo)的最小值、平均值和標(biāo)準(zhǔn)差進行分析比較，結(jié)果記錄在表6中。

IGD作為一個綜合性能評價指標(biāo)，可以說明MOPSO + FCSOA算法的收斂性能和分布性能上也基本優(yōu)于其他對比算法，在10個測試樣例中有9個都獲得了更好的表現(xiàn)，選取其中四個算例結(jié)果分別為J5M4P2W2、J10M5P3W2、J12M6P4W2、J14M7P6W3繪制數(shù)據(jù)箱線圖如圖9所示?？梢钥闯?，內(nèi)層選用FCSOA結(jié)果更好，與MAFJSP分批調(diào)度問題的適配性更高。

圖10給出了算例J12M6P4W2用四種算法所得到的Pareto前沿對比圖，其中藍色圓點代表 MOPSO+FCSOA ，黃色和紅色圓點分別代表MOPSO + NSGA-II以及 MOPSO+FOA ，綠色圓點代表MOPSO + IGWO（見電子版）。通過該圖不難看出，F(xiàn)CSOA得到的解更接近坐標(biāo)原點，且基本上優(yōu)于其他兩種算法，表明其在求Pareto最優(yōu)解集的收斂性和算法分布方面明顯優(yōu)于競爭算法。

圖11給出了算例J12M6P4W2的其中一個Pareto最優(yōu)解的調(diào)度甘特圖，該算例共包含兩個車間6臺加工機器，并且每個車間配備一條裝配線用機器7代表在甘特圖的最上層。12種工件的分批策略為[3，2，3，2，3，3，3，4，2，3，2，4]，圖中標(biāo)示出了工件批次和工序，4種產(chǎn)品在其所需工件齊套后進入裝配環(huán)節(jié)，有效提前了裝配進程并提高了生產(chǎn)效率，總完工時間為484個單位時間，成本為316.48。

4結(jié)束語

本文對于多產(chǎn)品混流生產(chǎn)裝配問題，深人分析各環(huán)節(jié)之間的聯(lián)系包括生產(chǎn)、運輸、庫存、裝配，以最小化最大完工時間和總成本為目標(biāo)，建立混裝柔性作業(yè)車間分批調(diào)度模型（MAFJSP-LS）。提出的雙層聯(lián)合多目標(biāo)改進混合算法MOPSO聯(lián)合FCSOA計算最佳分批策略和最優(yōu)調(diào)度方案，外層生成分批策略傳入內(nèi)層計算調(diào)度方案，內(nèi)層再將結(jié)果反饋回外層進行迭代循環(huán)，以獲得最優(yōu)分批策略，雙層算法分工明確且具有強耦合性，相較一般的分批問題解決辦法的單一算法，能夠結(jié)合不同算法的優(yōu)勢兼顧內(nèi)外層不同目標(biāo)特性獲得更突出的結(jié)果。編碼方案對應(yīng)雙層算法設(shè)計內(nèi)外兩層，外層表示分批策略，優(yōu)化結(jié)果可以直接給出分批策略，為生產(chǎn)實際提供參考。

其中內(nèi)層FCSOA算法對傳統(tǒng)FOA算法進行改進，加入?yún)f(xié)同搜索過程來增強優(yōu)化，采用改進的優(yōu)先操作交叉（IPOX）和多點保存交叉（MPX），分別實現(xiàn)作業(yè)順序的協(xié)同搜索和機器分配，并進行實驗對比。結(jié)合已有算例和醫(yī)療器械企業(yè)實際生成10組算例，與常用經(jīng)典NSGA-Ⅱ和改進前的FOA以及近年來解決類似問題的IGWO相比，F(xiàn)CSOA表現(xiàn)更為突出，收斂速度快，前沿解分布均勻，具有獨特的搜索機制和強適應(yīng)性，非常適合解決MAFJSP分批調(diào)度等生產(chǎn)任務(wù)調(diào)度和資源分配問題，能夠高效優(yōu)化生產(chǎn)流程，提高資源利用率。

本文在優(yōu)化混裝柔性作業(yè)車間生產(chǎn)資源配置、提高生產(chǎn)效率、降低成本等方面有著重要意義，可以為相關(guān)制造企業(yè)提供可參考的分批策略方案。未來將進一步考慮車間生產(chǎn)的復(fù)雜約束，如考慮生產(chǎn)實際中人力資源，根據(jù)產(chǎn)品特點細化生產(chǎn)裝配兩階段間的運輸庫存情況等約束條件。

參考文獻：

[1］易顧潤德，李春發(fā)，孫雷霆，等.全產(chǎn)業(yè)鏈模式下制造業(yè)產(chǎn)業(yè)生 態(tài)鏈構(gòu)建機制研究——基于扎根理論的多案例探索［J]．科技 進步與對策，2023，40（14）：40-50.（YiGurunde，Li Chunfa， Sunleiting，et al. Construction mechanism of manufacturing industry eco-chain under the whole industry chain model：an multiple-case exploration based ongrounded theory[J].Scienceamp; Technology Progress and Policy，2023，40（14）： 40-50.）

[2］呂海利，朱家濤，王正國，等．裝配作業(yè)車間的JIT調(diào)度研究 [J]．機械工程學(xué)報，2021，57（5）：157-165.（Lyu Haili，Zhu Jiatao，Wang Zhengguo，et al.Research of just-in-time scheduling for assembly job shop[J].Journal of Mechanical Engineering， 2021，57（5）：157-165.）

[3]Cheng Lixin，Tang Qiuhua，Liu Shengli，et al.Mathematical model and augmented simulated annealing algorithm for mixed-model assembly job shop scheduling problem with batch transfer[J]．Knowledge-Based Systems，2023，279：110968.

[4］朱熠，陳璐．考慮準(zhǔn)備時間的多目標(biāo)混合流水車間調(diào)度［J]．工 業(yè)工程與管理，2020，25（4）：159-165．（ZhuYi，Chen Lu. Multi-objective hybrid flow shop scheduling considering setup time [J]．Industrial Engineering and Management，2020，25（4）： 159-165.）

[5]Li Xiulin，Lu Jiansha，Yang Chenxi，et al.Research of flexible assembly job-shopbatch-schedulingproblembased onimproved artificial bee colony[J]. Frontiers in Bioengineering and Biotechnology，2022，10：909548.

[6]Zhang Sicheng ，Li Xiang，Zhang Bowen，et al. Multi-objective optimisationinflexible assembly job shopscheduling usingadistributed ant colony system [J]. European Joumal of Operational Research，2020，283（2）：441-460.

[7］曾強，沈玲，潘啟東，等.批量生產(chǎn)柔性作業(yè)車間多目標(biāo)精細化 調(diào)度方法［J]．計算機工程與應(yīng)用，2014，50（2）：263-27. （Zeng Qiang，Shen Ling，Pan Qidong，et al. Multi-objective elaborate scheduling method for batch production FJSP[J]. Computer Engineering and Applications，2014，50（2）：263-270.）

[8]黎英杰，劉建軍，陳慶新，等．多層級裝配作業(yè)車間等量分批策 略與調(diào)度算法[J].計算機集成制造系統(tǒng)，2021，27（8）：2307- 2320.（Li Yingjie，Liu Jianjun，Chen Qingxin，et al.Lot-splitting and scheduling algorithm of multi-level assembly job shops[J]. Computer Integrated Manufacturing System，2021，27（8）： 2307-2320.）

[9]劉雪紅，段程，王磊．基于改進候鳥算法的柔性作業(yè)車間分批調(diào) 度問題[J]．計算機集成制造系統(tǒng)，2021，27（11）：3185-3195. （Liu Xuehong，Duan Cheng，Wang Lei. Flexible job shop scheduling withlot streaming based on improved migrating birds optimization algorithm[J]. Computer Integrated Manufacturing System， 2021，27（11）：3185-3195.）

[10］李瑞，徐華，楊金峰，等．改進近鄰人工蜂群算法求解柔性作業(yè) 車間調(diào)度問題［J]．計算機應(yīng)用研究，2024，41（2）：438-443. （Li Rui， Xu Hua， Yang Jinfeng，et al. Improved algorithm of nearneighbor artificial bee colony for flexible job-shop scheduling[J]. Application Research of Computers，2024，41（2）：438-443.）

[11］姜鵬，方成剛，楊帆.GA-COA求解柔性作業(yè)車間多資源調(diào)度問 題[J]．機械設(shè)計與制造，2023（3）：156-159，164.（Jiang Peng， Fang Chenggang，Yang Fan.Hybrid genetic-coyotealgorithm for multi-resource flexible job shop scheduling problem[J].Machinery Designamp; Manufacture，2023（3）：156-159，164.）

[12] Caldeira R H， Gnanavelbabu A. A Pareto based discrete Jaya algorithmfor multi-objectiveflexible job shopscheduling problem[J]. Expert Systems with Applications，2021，170：114567.

[13]Boek A，Werner F. Flexible job shop scheduling with lot streaming and sublot size optimisation[J].International Journal of Production Research，2017，56（19）： 6391-6411.

[14］軒華，蔡舒躍，李冰．改進遺傳禁忌算法求解含惡化效應(yīng)和多時 間約束的柔性作業(yè)車間調(diào)度［J]．工業(yè)工程與管理，2024，29 （4）：193-2O4.（Xuan Hua，Cai Shuyue，Li Bing.An improved genetic Tabu algorithm for flexible job-shop scheduling with deterioration effectsand multipletimeconstraints[J].IndustrialEngineering and Management，2024，29（4）：193-204.）

[15］刁存藝，謝乃明，王玉全．面向智能制造車間的物料揀選“訂單 分批-路徑規(guī)劃”兩階段聯(lián)合調(diào)度方法［J]．工業(yè)工程與管理， 2024，29（4）： 31-41.（Diao Cunyi，Xie Naiming，Wang Yuquan. A two-stage integrated order batching and routing method for order picking inintelligent manufacturing[J].Industrial Engineering and Management，2024，29（4）： 31-41.）

[16］唐紅濤，沈毅，張偉，等．改進鯨魚算法求解分布式裝配柔性作 業(yè)車間生產(chǎn)與配送聯(lián)合調(diào)度問題［J]．計算機應(yīng)用研究，2023， 40（7）：1982-1990.（Tang Hongtao，Shen Yi，Zhang Wei，et al. Improved whale algorithm for integrated production and distribution scheduling problem in distributed assemblyflexible job-shop[J]. Application Research of Computers，2023，40（7）：1982- 1990.）

[17]Wong TC，Ngan S C. A comparison of hybrid genetic algorithm and hybrid particle swarm optimization to minimize makespan for assembly job shop[J].Applied Soft Computing，2013，13（3）：1391- 1399.

[18]Ren Weibo，Wen Jingqian，Yan Yan，et al.Multi-objective optimisation for energy-aware flexible job-shop scheduling problem with assemblyoperations [J]. Intermational Joumal of Production Research，2021，59（23）：7216-7231.

[19] Wang Ziyue， Lu Cong. An integrated job shop scheduling and assembly sequence planning approach for discrete manufacturing[J]. Jourmal ofManufacturingSystems，2021，61：27-44.

[20］魯建廈，胡慶輝，董巧英，等．面向云制造的混流混合車間調(diào)度 問題[J]．中國機械工程，2017，28（2）：191-205.（LuJiansha， Hu Qinghui，Dong Qiaoying，et al. Cloud manufacturing-oriented mixed-model hybrid shop-scheduling problem[J].China Mechanical Engineering，2017，28（2）：191-205.）

[21]Fattahi P，RadNB，Daneshamooz F，et al.A new hybrid particle swarm optimization and parallel variable neighborhood search algorithm for flexible job shop scheduling with assembly process[J].Assembly Automation，2020，40（3）：419-432.

[22]Lyu Yao，Zhang Jie，Qin Wenxin.A genetic regulatorynetworkbased sequencing method for mixed-model assmbly lines [J]. Advances in Production Engineering amp; Management，2017，12 （1）：62-74.

[23]Li Junqing，Tao Xinrui，Jia Boxian，etal.Eficient multi-objective algorithm for the lot-streaming hybrid flowshop with variable sub-lots [J].Swarm and Evolutionary Computation，2020，52：1-17.

[24]Zhou Binghai，Zhu Zhexin. Multi-objective optimization of greening scheduling problems of part feeding for mixed model assembly lines based on the robotic mobile fulfillment system[J].Neural Computing and Applications，2021，33：9913-9937.

[25]Song Hongbo，Yang Youhong，Lin Jian，et al.An effective hyper heuristic-based memeticalgorithm for the distributed assembly permutation flow-shop scheduling problem[J].Applied Soft Computing， 2023，135： 110022.

[26］李浩平，李景瑞，杜昕毅，等．求解多目標(biāo)柔性作業(yè)車間的IGWO算法［J]．制造技術(shù)與機床，2024（10）：174-180.（Li Haoping，Li Jingrui，Du Xinyi，etal.IGWOalgorithm for solving multiobjective flexible job shop[J].Manufacturing Technology amp; Machine Tool，2024（10）： 174-180.）