改進鯨魚算法求解分布式裝配柔性作業車間生產與配送聯合調度問題

摘 要：針對一類先加工后裝配的離散生產模式，研究分布式制造環境下的裝配柔性作業車間生產與配送兩階段聯合調度問題。結合實際的生產情況，考慮供應鏈下生產與配送過程所產生的庫存成本，以最小化生產和配送的總成本為聯合調度優化目標，提出一種改進鯨魚算法。針對聯合調度的多階段調度過程，設計了一種基于工序、產品、工廠、機器和車輛的五層編碼策略；根據各階段的特點提出了相應的混合種群初始化策略，以提高解的質量；以加強種群中領頭鯨魚個體與普通鯨魚個體的聯系為導向，改進了鯨魚覓食的搜索操作并提出四種鄰域結構，以增強算法的全局探索和局部搜索能力。最后，通過仿真實驗，對比相關研究領域的多種算法來驗證所提算法在收斂速度和求解質量等方面的優勢，并且將聯合調度與分階段調度進行實驗對比，驗證了聯合調度的優越性。

關鍵詞：分布式裝配柔性作業車間；聯合調度；鯨魚算法；庫存成本

中圖分類號：TP301.6

文獻標志碼：A

文章編號：1001-3695（2023）07-010-1982-09

doi：10.19734/j.issn.1001-3695.2022.12.0780

Improved whale algorithm for integrated production and distributionscheduling problem in distributed assembly flexible Job-Shop

Tang Hongtao^a，b， Shen Yi^a，b， Zhang Wei^a，b?， Wang Kaipu^a，b

（a.School of Mechanical amp; Electronic Engineering， b.Hubei Provincial Engineering Research Center of Robotics amp; Intelligent Manufacturing， Wuhan University of Technology， Wuhan 430070， China）

Abstract：This paper studied the integrated production and distribution scheduling problem in assembly flexible Job-Shop under distributed manufacturing environment. Combined with actual production situations， taking into account the inventory costs with production and distribution under the supply chain， this paper proposed an improved whale algorithm with the objective of minimizing the total cost of production and distribution as the joint scheduling optimization. For the multi-stage scheduling process of joint scheduling， this paper developed a five-level coding strategy based on process， product， plant， machine and vehicle. According to the characteristics of each stage， this algorithm designed corresponding hybrid population initialization strategies to improve the quality of the solution. To enhance the global exploration and local search capability of the algorithm， it improved a search operation of whale foraging and proposed four neighborhood structures with the orientation of strengthening the connection between individual leader whale and ordinary whale individuals. Finally，this paper compared multiple algorithms in related research areas to verify the advantages of the proposed algorithm in terms of convergence speed and solution quality， and compared joint scheduling with phased scheduling to verify the superiority of joint scheduling through simulation experiments.

Key words：distributed assembly flexible Job-Shop; joint scheduling; whale-algorithm; inventory cost

0 引言

在全球化制造背景下，制造型企業的競爭力不僅僅是單純的制造能力，對供應鏈進行全局把控才能獲得整體經濟效益的最大化。在整個訂單交付環節中，生產的完成決定裝車發貨時間，配送的批次和效率則影響在制品和成品庫存的消耗。生產和配送兩階段間信息交互的關聯性和約束性都影響著整個調度系統的總成本，將兩個階段獨立地考慮會造成優化目標相互沖突，總成本難以優化。聯合調度是一類面向供應鏈的優化方法，它采用精確調度的方式，集成式地設計供應鏈上各環節的調度方案可以最大限度地消除調度沖突。如果將生產和配送進行兩階段的聯合調度優化，即生產—配送聯合調度（integra-ted production and distribution scheduling，IPDS），可以打破生產和配送之間的信息壁障，適應柔性動態生產現場。例如，根據客戶距離將同一客戶的產品在相近的時間內加工調度完成，并分配到同一批次的裝車分組中發貨，極大地節省了庫存和重復運輸的成本。因此生產—配送聯合調度可以提高整個訂單的交付效率、降低總成本，具有十分重要的研究意義和應用價值。

聯合調度由Hall等人^［1］提出，通過集成采購、生產和配送環節的運作能夠顯著降低制造企業的成本；Devapriya等人^［2］考慮帶有消耗限制的產品生產與配送一體化調度問題；劉星等人^［3］基于遺傳和聲搜索算法優化研究多周期、多產品、多配送中心和多客戶的混合快消品生產配送問題；馬雪麗等人^［4］設計基于隨機模擬技術改進的混合遺傳算法，優化易腐食品的生產調度與配送路線協同優化模型；劉玲等人^［5］針對單機器生產和多車輛運輸協同調度問題，建立了以最小化訂單交付時間為目標的生產與配送協同調度模型， 并提出了一種混合禁忌搜索算法進行求解；仲維亞等人^［6］研究一類新零售企業的訂單揀選問題并綜合考慮了車輛路徑規劃，提出了一種基于Johnson算法和遺傳算法的啟發式算法進行求解；Martins等人^［7］提出了一種鄰域變量偏移下降的啟發式算法，求解以最小化服務時間為目標的多階段混合流水車間調度和分批配送路徑優化的集成問題。目前聯合調度的研究主要是在傳統的集中式生產模式下，從供應鏈的相近環節考慮優化生產和運輸總成本，這一類問題由兩個及以上子問題構成，模型、求解難度和優化空間大。隨著分布式制造需求的不斷提升，技術條件日漸成熟，傳統制造模式正向分布式制造模式轉變。然而，與單工廠調度不同， 分布式調度問題的求解是從資源配置的總體層面進行考慮， 通過各工廠間的協作以實現經濟效益的最大化。顯然，分布式車間調度屬于NP-難問題^［8］，求解分布式車間調度相比求解單一車間調度問題難度更大，并且在實際生產中一個產品往往是由多個零件組裝而成，整個制造過程是由加工和裝配兩個階段構成。Hatami等人^［9］首次提出了分布式裝配置換流水線調度問題，研究多個異地流水車間工廠，工件先被分配到某一流水車間加工，再經過裝配后成為最終產品；Sang等人^［10］設計入侵雜草算法求解帶總流經時間標準的分布式裝配置換流水線調度問題；雷德明等人^［11］提出了考慮順序相關的分布式兩階段混合流水車間調度問題，基于蛙跳算法并采取種群記憶劃分方法和多種模因組搜索策略進行有效求解；Song等人^［12］提出一種基于遺傳編碼的超啟發式算法，低層的啟發式策略集合通過遺傳編碼生成啟發式序列，以求解分布式裝配置換流水車間調度問題。現有文獻對于分布式裝配柔性作業車間調度問題（distributed assembly flexible Job-Shop scheduling problem，DAFJSP）的研究較少，DAFJSP描述為分布式制造下同時包含加工和裝配的柔性作業車間調度。Wu等人^［13］首次以最小化提前/延遲總成本生產為目標建立了DAFJSP模型，提出一種改進差分進化模擬退火算法進行求解；郭晨等人^［14］ 針對模糊加工時間和裝配時間下的DAFJSP，提出了一種基于概率模型的相似系數和兩種變異算子的混合差分搜索及變鄰域搜索的分布估計算法進行求解。在實際的工程項目特別是一些離散型裝配制造企業，兩階段的DAFJSP比DFJSP更加貼合實際的生產狀況，研究成果也更能指導企業生產，因此尋求針對DAFJSP的高效調度方法和調度機制具有重要的應用價值。

在保證產品質量和訂單交付的前提下，優化供應鏈的資源分配策略、提高資源利用率、開展生產與配送聯合調度研究，對于節約成本、提高企業競爭力具有重要意義。從現有文獻來看：國內外對于分布式裝配柔性作業車間的生產—配送聯合調度問題（IPDS-DAFJSP）的研究較少，且大多數在理想的數學模型下進行優化，不太貼合實際生產配送過程，如忽略了生產裝配及運輸準備過程中的庫存成本。庫存作為供應鏈的重要環節，在供應鏈運作成本中的占比以及對最終調度結果的影響都十分巨大。IPDS-DAFJSP求解復雜度高，目前求解方法主要為近似方法，元啟發式算法及混合算法則廣泛應用于大規模問題。鯨魚優化算法（whale optimization algorithm，WOA）是Mirjalili等人^［15］于2016年提出的一種模仿自然界中鯨魚捕食行為的群體智能優化算法，具有參數少、多種群協同、算法適應性好的特點，且在大規模的問題模型中尋優能力較強，已成功應用于多種優化問題，尤其是調度領域^{［16，17］}。李寶帥等人^［18］在WOA中加入非線性收斂因子，結合正余弦算法策略改進鯨魚個體更新方式來求解柔性作業車間調度問題；閆旭等人^［19］利用量子計算與優化思想提出一種量子鯨魚優化算法求解作業車間調度問題；欒飛等人^［20］針對低碳車間調度問題，設計了非線性收斂因子和自適應慣性權重系數來改進鯨魚優化算法全局搜索和局部尋優的能力。此外，目前尚未找到將鯨魚優化算法應用于考慮庫存成本的IPDS-DAFJSP的研究，本文研究一類分布式裝配作業柔性車間的生產與配送聯合調度問題，考慮生產運輸過程中工件以及產品的庫存成本，建立以最小化聯合調度總成本為優化目標的調度模型。為高效地求解IPDS-DAFJSP模型，提出一種改進鯨魚優化算法（improved whale optimization algorithm，IWOA），針對多階段的調度問題設計多層的編碼結構和混合初始化策略，結合算法特征和模型特點設計鯨魚覓食搜索和引入四種鄰域結構，最后通過仿真實驗驗證了該算法和聯合調度的優越性。

1 問題描述及數學模型

1.1 問題描述

本文研究的IPDS-DAFJSP描述如圖1所示。

一段時間內制造商接收來自C個客戶的產品訂單，產品集為U_p ={p₁， p₂ ，…， p_N}。將N個產品分配到F個不同位置的工廠進行生產，工廠集U_f ={f₁，f₂，…，f_F}中每個工廠都是一個裝配柔性作業車間（assembly flexible Job-Shop， AFJSP），每個工廠配備了一系列差異化的加工機器以及一條裝配作業線，且每個工廠生產產品的能力不同。每個產品由若干個工件組成，工件集U_j ={j₁， j₂ ，…， j_n}中的第j個待加工工件包含r_j道工序，工序之間遵循工藝約束，每道工序可在一臺或多臺加工機器上加工。先完工的工件會存入零件倉，當產品所有工件都加工完畢后進行裝配，等待裝配過程會產生相應的工件庫存成本。裝配完工的產品會進入到成品倉庫，安排分組裝車確定配送車輛數H，等待發貨的過程中會產生相應的產品庫存成本。配送車輛從各工廠出發，將產品運輸給相應客戶，每個客戶點只經過一次，配送完畢立即返回工廠。配送地點（工廠或客戶）的集合為U_f，c={f₁，f₂，…，f_F，c₁，c₂，…，c_C}。

為了方便問題的建模和求解，除經典DAFJSP假設外，本文主要假設條件如下：a）同一產品的工件只能在同一工廠內加工和裝配；b）相同工件在不同工廠單位時間的加工、裝配和庫存成本相同，相同產品在不同工廠單位時間庫存成本相同；c）一個產品的工件都生產完成且裝配作業線處于空閑時立即進行裝配，當同組的產品都裝配完成后立即配送；d）不考慮產品的生產準備時間、產品的包裝時間、產品的裝車時間以及產品的卸載時間等；e）每輛配送車輛的條件相同，工廠到客戶、客戶到客戶之間的旅行時間是固定的，且只考慮最優路徑的配送方案。

1.2 數學模型

IPDS-DAFJSP中包含生產和配送兩個子問題，目標是合理安排機器上工件的加工順序和成品配送的方案，使整個供應鏈中的總成本TC最小。目標函數如下所示：

其中：TPC表示加工過程的成本;TAC表示裝配過程的成本;TICj表示工件的庫存成本;TICp表示產品的庫存成本;TDC表示配送成本;TTC表示拖期成本。TPC與機器加工的時間正相關，單位時間加工成本為k_j，則TPC的計算公式如下：

其中：f為工廠索引；m為機器索引；j為工件索引；i為工序索引；x_{j，i，f，m}為決策變量，若工件j的第i道工序在工廠f的第m臺機器上加工則為1，否則為0；t_{j，i，f，m}表示工廠f第m臺機器加工工件j的第i道工序所需時間。TAC與裝配機器的工作時間正相關，單位時間裝配成本為k_p，則TAC的計算公式如下：

其中：p為產品索引；t_p為產品p裝配所需的時間。工件有先后完工的順序，先完工的工件放入庫存中等待裝配，這個過程會產生相應的工件庫存成本TICj，其與庫存時間正相關。工件的單位時間庫存為v_j，則TICj的計算公式如下：

其中：μ_j，p為決策變量，若工件j屬于產品p則為1，否則為0；Sa_p為產品p的裝配開始時間；E_j為工件j的加工完工時間。

工件存放于庫存的截止時間是產品的開始裝配時間而不是產品工件的最大完工時間，因此假設p′緊接p進入裝配，則產品p′開始裝配時間Sa_p′取決于產品p加工完工時間E_p和產品p′的裝配完工時間Ea_p′中的較大值，其式如下：

其中：z_{p ，p′，f}為決策變量，若產品p′緊接產品p之后在工廠f進行裝配則為1，否則為0。Ea_p與E_p′的計算公式如下：

其中：E_j等于工件最后一道工序的完工時間，其公式為

其中：E_{j，r j}為工件j第r_j道工序的完工時間；S_{j，r j}為工件j第r_j道工序的開始加工時間。

產品裝配完畢會分組裝車配送至客戶手中，先裝配完成的產品會放入庫存中等待同組產品一起運輸，這個過程會產生相應的庫存成本TICp，其與庫存時間正相關。產品的單位時間庫存成本為v_p，配送車輛數H的取值范圍如下：

其中：W為車輛容量大小；W_p為產品大小；N為產品數，表示車輛數不能超過產品總數。因此TICp的計算公式如下：

其中：h為車輛索引；σ_p，h為決策變量，若產品p被分配到車輛h則為1，否則為0；Ea_p0和Ea_p的計算方式同式（6）。

配送過程的成本TDC由兩部分組成，一部分是車輛的固定成本ω，一部分是配送成本且配送成本與配送時間正相關，單位時間運輸成本為k_h，TDC的計算公式如下：

其中：d為地點（工廠或客戶）的索引；U_f，c為地點（工廠或客戶）的集合，U_f，c ={f₁， f₂ ，…， f_F， c₁， c₂ ，…， c_C}；π^d_h為決策變量，若d為車輛h的配送過程的一個目的地則為1，否則為0；q_d，d′為決策變量，若地點d′緊接在地點d（工廠或客戶）之后進行配送則為1，否則為0；t_d，d′為地點d到d′的運輸時間。

產品若無法按時送到客戶手中則會產生相應的拖期成本TTC，其與超出客戶交貨截止時間的大小正相關，單位時間拖期成本為k_T，則TTC的計算公式如下：

其中：c為客戶索引；λ_p，c為決策變量，若產品p屬于客戶c則為1，否則為0；T_c為車輛配送產品至客戶c的時間；E_c為客戶c交貨的截止時間。

IPDS-DAFJSP的模型約束如下：

式（13）表示一個產品只能在一個工廠進行生產。θP，f為決策變量，若產品p在工廠f生產則為1，否則為0。

式（14）表示一道工序只能在一個工廠的一臺機器上加工。

式（15）表示工件工序加工過程的連續性。

式（16）表示工件下一道工序的開始時間由上一道工序的結束時間和下一道工序所在機器的加工完成時間決定。y^f，m_{j，i，j′，i′+1}為決策變量，若工件j′的第i′+1道工序緊接工件j的第i道工序之后在工廠f的第m臺設備上加工則為1，否則為0; U_i為工序集，U_i ={i₁，i₂，…，i_I}。

式（17）表示工件所屬的產品有且只有一個。

式（18）表示產品的裝配開始時間不能小于產品工件的最大完工時間。

式（19）表示產品裝配過程的連續性。

式（20）表示產品的裝配順序。

式（21）表示一個產品只能在一輛車上進行配送。

式（22）表示一個產品只有一個對應的客戶。

式（23）表示同車產品全部裝配完工后立即配送。S_h為車輛h的開始配送時間。

式（24）約束了車輛配送產品的容量限制。

式（25）約束了配送過程的連續性。E_d為車輛配送產品至地點d的時間。

2 改進的鯨魚算法

2.1 鯨魚算法

WOA可以概括為包圍捕食、氣泡攻擊以及搜尋獵物三個主要過程。根據上述模型，IPDS-DAFJSP屬于NP-難問題，且是離散組合優化問題。傳統的WOA適用于求解連續型問題，因此需要做離散化的改進才能使其適用于求解該問題。例如Jiang等人^［21］基于WOA提出了離散鯨魚算法（DWOA），成功求解了離散的FJSP問題。同時由于IPDS-DAFJSP包含多個階段的調度過程，單一的操作很難滿足各個階段的求解要求。因此，本文提出一種改進的鯨魚優化算法，設計多層編碼以及相應的混合初始化策略、鯨魚覓食搜索操作以及基于各階段特點的鄰域結構，從而使算法的探索能力和局部搜索能力得到有效的結合和平衡。算法流程如圖2所示，其具體流程如下：

a）按混合種群初始化策略生成初始種群，求解適應度并排序；

b）根據領頭鯨魚率ξ篩選出相應數量的個體組成領頭鯨魚群，剩余個體組成跟隨鯨魚群；

c）按隨機和二元錦標賽的方法分別從領頭、跟隨鯨魚群中選出一個個體作為父代；

d）根據漢明距離判斷兩個父代的差異程度；

e）使用改進的鯨魚覓食搜索更新個體，得到新種群；

f）同步驟b）的篩選方法從新種群中選出個體組成領頭鯨魚群，對領頭鯨魚群使用鄰域搜索更新個體；

g）重復執行步驟b）～f），直到算法滿足終止條件，并輸出最優解。

2.2 編碼與解碼

IPDS-DAFJSP屬于多階段復雜調度問題，一個完整的可行解應包含以下信息：產品的工廠指派方案、機器選擇和加工順序以及產品的運輸方案。同時考慮到IPDS-DAFJSP的離散性，為了能夠充分提取編碼中的有效信息，本文設計了五層的整數型編碼方案，分別是工序層X_j、產品層X_p、工廠層X_f和機器層X_m以及車輛層X_h，表示為X = ［X_j|X_p|X_f|X_m|X_h］。以表1和圖3為例，表中數據包含3個產品、6個工件、2個工廠，工序數在［1，3］，工序可選的加工機器數在［1，3］，每個工廠都包含五臺機器以及一個裝配作業線。圖3中O₄₁表示工件4的第1道工序，依此類推。因此，編碼過程如下：

a）工序層編碼。X_j=［4，2，1，5，4，2，2，6，3，1，5，6，6，3，4］，其中元素表示工件編號，第一個“4”表示工件4的第一道工序O₄₁。

b）產品層編碼。X_p=［3，2，1，3，3，2，2，3，2，1，3，3，3，2，3］，其中元素表示產品編號，由表1可知工件2、3屬于產品2，由于相同產品工件的產品編號相同，所以工件2、3對應X_p中的產品編號為2，依此類推。

c）工廠層編碼。X_f=［2，1，1，2，2，1，1，2，1，1，2，2，2，1，2］，其中元素表示工廠編號，由表1可知工件4、5、6屬于產品3，產品3在工廠2加工，同時編碼規則需滿足約束式（13）即同一產品只能在同一工廠生產，則工件4、5、6對應X_f中的工廠編號為2。

d）機器層編碼。X_m=［2，2，1，3，2，2，3，1，2，3，1，2，3，3，1］，其中元素表示對應工序可選機器集中的索引號。第一個“2”表示工序O₄₁在可選機器集的第二臺機器上加工，依此類推。

e）車輛層編碼。X_h=［2，1，1，2，2，1，1，2，1，1，2，2，2，1，2］，其中元素表示車輛編號，同時編碼規則需滿足約束式（21）（24），即一個產品只能由一輛車進行配送并且一輛車上產品大小總和不能超過車輛容量限制。

解碼過程以工廠為單位，分解成多個AFJSP的IPDS子問題，然后針對各子問題分別解碼。工件加工階段解碼如圖4所示，在相對順序不變的情況下，以工廠為單位提取各層編碼。工件加工階段的解碼是X_j和X_f編碼的逆過程，而對于X_m解碼需要將索引映射為對應的機器編號。

加工階段的解碼會產生相應的工件庫存成本TICj。如圖5所示，在加工過程中工件2先完工入庫等待工件3完工才能進行產品2的裝配，整個過程工件2等待裝配時間為t₃-t₂，相應的工件庫存成本即為v_j（t₃-t₂）。

a）產品裝配階段解碼。裝配階段采取先到先裝配（first come first served，FCFS）的規則進行解碼，即先滿足裝配條件的產品先進行裝配。若多個產品的完工時間相同，則隨機確定這些產品的裝配順序。

b）產品裝車階段解碼。分組裝車階段對裝配完工的產品分組進行裝車，期間會產生相應的產品的庫存成本TICp。如圖5所示，由于p₂工件的最大完工時間t₃小于p₁工件的最大完工時間t₁，所以p₂先進行裝配，T₂時p₂裝配完畢，緊接著進行p₁的裝配，T₁時完成p₁裝配，整個過程p₂的等待裝車時間為T₁-T₂，產品的庫存成本即為v_p（T₁-T₂）。

c）產品運輸階段解碼。運輸階段解碼過程會產生相應的配送成本TDC，由于車的容量限制以及運輸的產品數量是有限的，在運輸路徑的選擇上也是有限的。所以，可將運輸過程簡化為一個小規模的旅行商問題（travelling salesman problem，TSP），從中選出最短路徑進行運輸。此外，若產品的送達時間超過約定的截止日期則會產生相應的TTC。

2.3 混合種群初始化

初始解的質量對鯨魚算法求解速度和求解質量有非常大的影響，為提高初始種群的質量，本文基于模型的特點設計了若干策略用于種群的初始化，同時為保持種群的多樣性，仍然保留隨機初始化策略。對于工序層X_j，以下兩種策略各占種群規模的50%：a）優先選擇剩余工序多的工件，若存在多選，則隨機選擇；b）工序隨機排序，產品層X_p嚴格遵循產品與工件的關系與工序層X_j做到一一對應。對于工廠層X_f，以下兩種策略各占種群規模的50%：a）優先選擇加工產品數少的工廠，若工廠的加工產品數相同則選擇與客戶距離最近的工廠進行生產；b）隨機選擇一個工廠。對于機器層X_m，以下兩種策略各占種群規模的50%：a）優先選擇可選機器集中加工時間短的機器，若存在多選，則在加工時間較短的機器中隨機選擇；b）隨機選擇一臺加工機器。對于車輛層X_h，以下兩種策略各占種群規模的50%：a）從減少車輛固定成本的角度出發，采取最小化車輛數的裝車策略，根據產品大小和車載容量劃分出最小批次進行配送；b）在滿足車載約束的前提下，隨機選擇車輛進行配送。

2.4 改進的鯨魚覓食搜索

本文結合IPDS-DAFJSP各層編碼的特點提出一種改進的鯨魚覓食搜索。種群個體向領頭鯨魚聚集的現象會導致引導個體單一，弱化了鯨魚群個體之間的信息交流與協作，一定程度上限制了算法的搜索能力和種群的多樣性。因此，本文提出領頭鯨魚群的概念，定義領頭鯨在群體中所占的比例為領頭鯨魚率ξ，鯨魚個體根據適應度進行排序，按ξ篩選出領頭鯨魚，將鯨魚群分為領頭鯨魚群和跟隨鯨魚群。

基于鯨魚包圍捕食和搜尋獵物的捕食行為，設計了高效的搜索操作，表達式如下：

其中：search（·）為搜尋操作；catch（·）為捕食操作；d_lr表示兩個個體的漢明距離，漢明距離是指兩個序列中位置相同而值卻不同的個數；|x_l（r）|表示個體x_l（r）五層編碼的總長度，|x_l（r）|=|x_i（r）|；D_lr表示兩個個體的漢明距離占編碼總長度的比例，取值范圍為［0， 1］；P_lr表示兩個個體差異程度的閾值，取值范圍為［0， 1］。當D_lr≤P_lr時，表明x_i （r）已經接近優異個體x_l（r），需進行search（·）操作使新個體盡可能遠離當前優異個體x_l（r），相當于鯨魚搜尋獵物的行為，有助于算法跳出局部最優。當D_lr＞P_lr時，表明兩個個體之間的差異較大，需進行catch（·）操作，相當于鯨魚的包圍捕食行為，可以增強局部搜索能力。

從領頭鯨魚群中隨機選出一個個體x_l（r）作為父代1，另一個父代采用二元錦標賽方法，從跟隨鯨魚群中隨機選出兩個個體，選擇適應度較優的個體x_i（r）作為父代2。模擬鯨魚個體的搜尋和捕食操作，設計出各編碼層的改進搜索方式如下：

a）工序層搜尋操作。如圖6所示，以X_lj=［2，3，1，6，4，2，5，4，4，1，6，3，5，2，6］和X_ij=［4，2，1，5，4，2，2，6，3，1，5，6，6，3，4］為例，將工件集j={1，2，3，4，5，6}隨機分為子集j₁={1，3，6}和j₂={2，4，5}。將X_lj中屬于j₁的工件復制到子代1且保持工序原本位置不變，將X_ij中屬于j₂的工件按順序依次插入到子代1的空缺中，生成子代2的操作也是同理。其他層與X_j一樣進行同步移動。若出現非法解，需要對X_m和X_h進行修正。

產品層X_p與工序層X_j存在嚴格的產品與工件的對應關系，所以X_p只隨X_j的變化作出相應改變。

b）工廠層搜尋操作。X_f搜尋操作需滿足以下兩點條件：（a）需滿足約束式（13），所以X_f交叉只能以產品為單位進行操作；（b）交叉后的工廠應具有生產相應產品的能力，否則繼續選擇其他工廠。圖7所示為X_f交叉過程，X_j和X_p保持不變，互換個體X_f和X_m的編碼。若出現非法解，需要對X_m和X_h進行修正。

c）機器層搜尋操作。如圖8所示，隨機生成一個n維的向量v={v₁，v₂，…，v_n}，n與各層編碼的長度相等，v中的元素為［0，1］的隨機數，若小于0.5則互換相應位置的機器索引號；若出現非法解，需要對X_m進行修正。

d）車輛層動態搜尋操作。X_h的實質是產品分組裝車的策略，而分組裝車的方案需要根據產品工廠的指派方案、產品的生產完工順序以及車輛的限載容量來確定，相較于X_j、X_p、X_f和X_m的編碼方案，X_h的可行編碼數量會相對較少，對X_h進行上述的靜態搜尋操作產生新解的效率較低且不方便后續修正。因此，考慮將X_h編碼的調整轉變為一種實時更新的動態搜尋策略，采用產品先到先裝車（FCFS）和隨機選擇兩種策略各50%的概率對X_h進行更新，這樣既能響應X_j、X_p、X_f和X_m的變動又保留了編碼的多樣性。

上述各層編碼經過搜尋操作產生新解，為保證編碼的可行性以及防止出現非法解，需進行相應的修正操作。其中對于X_m的修正則是在可選機器集中隨機選擇一個機器索引來代替非法解的機器索引。對于X_h的修正則采用動態搜尋操作更新X_h。

經過上述搜尋操作后，利用貪婪選擇從生成的兩個子代中選擇適應度較優的作為新個體。

捕食操作主要包括以下幾個步驟：

a）工序層捕食操作。X_j采用插入法，兩個父代在各自的工序層隨機選取兩個不同位置，將前一個工序號插入到后一個工序號后面的位置上，其他層和X_j一樣進行同步移動。若出現非法解，需要對X_m和X_h進行修正。產品層X_p根據產品和工件的對應關系，隨X_j變化做相應改變。

b）工廠層和機器層捕食操作。X_f和X_m均采用替換法，兩個父代在各自的X_f和X_m層隨機選取一個要替換的位置，然后在可行范圍內隨機替換成另一個新值。若出現非法解，需要對X_m和X_h進行修正。

c）車輛層捕食操作。X_h采用動態捕食操作，其方法與上文X_h的動態搜尋方式一樣。

上述各層通過捕食操作產生新解，為保證編碼的可行性以及防止出現非法解，需進行相應的修正操作。其中對于X_m和X_h的修正同上述的搜尋過程的修正。

經過上述捕食操作后，利用貪婪選擇從兩個子代中選擇適應度較優的作為新個體。

2.5 鄰域結構

鯨魚通過發泡網收縮包圍獵物，以螺旋式的方式靠近獵物，這個過程鯨魚的位置更新方式對于算法的迭代尋優過程影響極大。根據IPDS-DAFJSP的特點，影響總成本的因素主要有產品的工廠指派、工序的加工順序、加工機器的選擇及產品分組裝車的策略。為進一步增強算法的局部搜索能力，設計了四種具有針對性的鄰域結構。同時考慮到對所有個體進行局部搜索會增加算法運行時間。因此為了減少計算量，按領頭鯨魚率ξ從新種群中選出個體組成領頭鯨魚群進行鄰域搜索。

1）產品工廠的指派過程

鄰域結構N1。找到產品加工數最多的工廠，若存在多選則隨機選擇其中一個工廠，找到工廠中完工時間最大的產品，將其轉移到產品加工數最少的工廠。若存在多選，則計算該產品的所有工件在不同工廠從加工到配送所經過的時間總和，將產品安排到時間總和最小的工廠里生產。如圖9所示，以產品2為例，其在工廠1的總耗費時間為23/單位時間，在工廠2的總耗費時間為25/單位時間，所以在工廠1和2的加工產品數相同的情況下，優先選擇工廠1進行生產。

2）生產加工過程

鄰域結構N2。最小化最大完工時間在一定程度上能加快產品進入裝配以及配送階段，從而縮減拖期時間。因此采用貪婪插入的方法從工序編碼序列中隨機選取一個元素，將其插入到編碼序列中的其他位置產生多個鄰域結構，選擇最大完工時間最小的一個鄰域結構。

鄰域結構N3。在完工時間最大的工廠中找到累積加工時間最大的機器，將加工時間最長的工序換到可選機器集中累積加工時間最短的機器上加工，若存在多選則隨機選擇。

3）分組裝車過程

鄰域結構N4。在車載允許且按先裝配完工的產品先裝車的前提下，將同屬于一個客戶的產品盡量安排到同一輛車進行運輸，以減少同客戶產品的運輸次數。

進行變鄰域搜索時，某一步驟鄰域結構產生的新解優于當前解，則新解替換當前解，并跳出鄰域搜索。反之，則轉入下一個鄰域結構繼續搜索，直至所有鄰域結構都搜索完畢輸出新解。

3 實驗與分析

3.1 算例

當前沒有標準算例可用于測試IPDS-DAFJSP，因此本文以Brandimarte算例集中的MK01、MK04、MK09、MK12、MK14為基礎，每個算例各考慮兩個或者三個工廠的情況，擴展生成了10組適用于IPDS-DAFJSP的新算例以供使用，生成新算例的參數如表2所示。

以算例J10M6P3C3F2為例，表示工件數為10，單工廠機器數為6，產品數為3，客戶數為3，工廠數為2。同時考慮分布式工廠生產能力以及機器的差異性，所以將標準算例中的工時數據進行擴展，按區間左端點的80%并取整生成新的左端點，按區間右端點的120%并取整生成新的右端點。此外，關于時間和成本的相關參數設置如表3所示，其參數的單位為單位時間或單位成本。

3.2 參數設置

IWOA的參數設置對其性能影響較大，主要影響參數為：種群規模Pop、領頭鯨魚率ξ、個體差異程度P_lr。為了確定最優參數組合，本文通過正交實驗設置IWOA參數，每個參數設置三個水平，具體如表4所示。選用L₉（3⁴）正交表，以算例J10M6P3C3F2為例，算法最大迭代次數為200次，為避免測試結果的隨機性，每組實驗運行30次，將30次運行結果的平均值作為最終實驗結果列于表5中。

根據表5中的實驗結果作出參數不同水平的趨勢來反映影響程度。如圖10所示，橫坐標為同一參數的不同水平，縱坐標為同一水平下參數結果（avg）的平均值，值越小說明算法尋優能力越強，所以IWOA的參數設置為：Pop=200，ξ=0.2，P_lr=0.5。

3.3 實驗結果及分析

為驗證 IWOA求解上述模型的有效性和優越性，本文基于擴展后的測試算例進行對比實驗。根據相似離散化的特點，首先選用文獻［21］中的DWOA作為第一個對比算法；移除IWOA中的鄰域結構并命名為RWOA，以RWOA作為第二個對比算法來驗證IWOA中提出的鄰域結構的有效性；此外，由于當前對于IPDS-DAFJSP的研究較少，在最新研究成果中選擇了用于求解相似問題模型DAFJSP的單目標算法HHCEA^［22］作為第三個對比算法來驗證IWOA的有效性。

在求解IPDS-DAFJSP的算法比較中， 對DWOA、RWOA和HHCEA進行適量調整，IWOA和RWOA按3.2節的實驗結果設置參數，其余兩個算法的參數設置均采用相應參考文獻中的建議值；IWOA和RWOA采用本文所提的種群初始化策略，其余兩個算法均采用隨機初始化策略。其中在HHCEA的低層啟發式操作中缺少配送階段的鄰域結構，為保證實驗結果的可靠性，在HHCEA的低層啟發式操作中加入IWOA的鄰域結構N4，補充HHCEA對于配送階段的低層啟發式操作，并將HHCEA的高層策略長度改為12。

算法運行環境為：Intel Core i7，CPU 2.9 GHz，RAM 8 GB，Windows 10，MATLAB 2016 b，實驗結果如表6所示。每個算法均獨立運行30次，并采用最優值（best）、平均值（avg）、相對誤差（relative percentage deviation，RPD）三個指標對算法性能進行評價。其中RPD表示為當前算法運行30次的最優值與所有算法運行30次的最優值的相對誤差。

從表6中的實驗結果可以得出，在10個擴展算例中，IWOA在大部分的算例上都表現得最為優異，HHCEA次之，并且隨著算例規模的增大，IWOA性能上的優勢也越來越明顯，由此驗證了所提算法的優越性，同時IWOA與RWOA的對比也驗證了鄰域結構的有效性。此外，在除工廠數外其他標準相同的兩算例進行對比，三個工廠算例的指標明顯優于兩個工廠算例的指標。對比J30M15P7C4F2和J30M15P7C4F3，總成本從2 748.9降至2 314.2，表明分布式工廠能夠進一步合理配置生產資源提高生產效益。

圖11為各算法對于算例J15M8P4C3F3和J30M15P7C4F3的迭代收斂曲線，其中橫坐標為迭代次數，總共迭代了200次，縱坐標為調度的總成本。由圖11可知，兩個算例中IWOA的收斂速度和解的質量都優于其他三種算法，說明IWOA改進的搜索操作和領域搜索策略能有效避免算法陷入局部最優和提高算法收斂速度；此外，兩算例中IWOA曲線的初始解明顯優于其他三種算法，說明IWOA種群初始化策略能有效提升初始解的質量。

圖12給出了算例J30M10P6C4F2的調度甘特圖。其中，產品{1，2，6}在工廠f₁加工，產品{3，4，5}在工廠f₂加工。經優化后工廠f₁裝配完工時間為406單位時間，工廠f₂裝配完工時間為459單位時間。表7給出了算例J30M10P6C4F2的配送方案。其中產品{1，2，3}屬于客戶c₁，產品4屬于客戶c₂，產品5屬于客戶c₃，產品6屬于客戶c₄。

最后，為了驗證本文IPDS框架的有效性，將產品生產階段和配送階段作為兩個單獨的子系統分別優化。與IPDS不同，生產階段單獨優化目的是得到最優的生產成本，其中生產階段成本包含TPC、TAC和TICj；而配送階段則根據生產階段的調度方案調整產品的裝車策略和配送路徑得到最優的配送成本，其中配送階段成本包含產品的庫存成本TICp、配送成本TDC以及拖期成本TTC。為了保證實驗結果對比的可靠性，生產和配送分階段優化過程中的算法迭代次數各取200次，求解過程的初始化種群策略、算法流程、參數設置均與IPDS一致。圖13為兩階段分別優化的流程圖。

表8為兩種調度方法的各項成本對比數據，選用六組工件、產品、工廠數的規模各不相同的算例來驗證聯合調度與分階段調度的優化性能。調度方式1為聯合調度，方式2為分階段調度。由表8數據可知，在小規模的算例上兩種方法得出的總成本差距不大，但隨著算例規模的增大，聯合調度對于總成本的優化效果越來越顯著，且優于分階段調度。從各項成本數據分析來看，分階段調度將生產和配送看做兩個獨立系統分別優化，雖然在生產階段取得了較優的生產成本，但沒有考慮到兩個階段之間的相互影響以及調度方案的輸送，使得配送階段的產品庫存成本與拖期成本明顯大于聯合調度。

4 結束語

本文從供應鏈的角度出發，研究了分布式制造環境下的裝配柔性作業車間生產與配送兩階段聯合調度問題。首先，考慮多環節的庫存成本，建立了以供應鏈總成本為優化目標的調度模型；然后，針對聯合調度問題多階段的特點對鯨魚算法進行改進，包括設計五層編碼方案、高質量的混合種群初始化方法以及兩類鯨魚覓食搜索策略，此外為加強算法的局部搜索能力設計了四類領域結構；最后，進行對比實驗驗證了算法的有效性以及聯合調度的優越性。

本研究對優化供應鏈的資源配置、節約成本有著重要意義，可以為相關制造模式提供可參考的調度模型方案和優化方法。然而，到目前為止關于分布式裝配柔性作業車間以及聯合調度問題還有許多欠缺有待進一步深入研究和探索，未來的工作大致包括：a）進一步完善聯合調度中的配送階段模型，如考慮不同客戶特點和不同產品特點；b）增加裝配環節的調度資源和新增裝配調度約束，驗證在大規模問題模型下此算法的尋找能力，并作出新的算法改進以提升算法的適應性和性能；c）考慮機器的故障、訂單的異常等實際擾動情況，研究動態環境下的分布式裝配柔性作業車間聯合調度問題等。

參考文獻：

［1］Hall N G， Potts C N. Supply chain scheduling：batching and delivery［J］. Operations Research， 2003，51（4）： 566-584.

［2］Devapriya P， Ferrell W， Geismar N. Integrated production and distribution scheduling with a perishable product［J］. European Journal of Operational Research， 2017，259（3）： 906-916.

［3］劉星. 和聲搜索算法優化快速消費品生產配送協調調度［J］. 工業工程， 2016，19（3）：14-17. （Liu Xing. Harmony search algorithm for coordinated scheduling in production and distribution of fast mo-ving consumer goods［J］. Industrial Engineering Journal， 2016，19（3）：14-17.）

［4］馬雪麗， 王淑云， 劉曉冰， 等. 易腐食品二級供應鏈生產調度與配送路線的協同優化［J］. 工業工程與管理， 2017，22（2）：46-52，59. （Ma Xueli， Wang Shuyun， Liu Xiaobing， et al. Integrated optimization of production scheduling and distribute for perishable food product in two-echelon supply chain［J］. Industrial Enginee-ring and Management， 2017，22（2）：46-52，59.）

［5］劉玲，李昆鵬，劉志學. 生產和運輸協同調度問題的模型和算法［J］.工業工程與管理， 2016，21（2）：86-91. （Liu Ling，Li Kunpeng，Liu Zhixue. Model and algorithms for the integrated production and transportation scheduling［J］.Industrial Engineering and Management， 2016，21（2）：86-91.）

［6］仲維亞， 崔佳. 新零售企業的訂單揀選及配送聯合調度算法研究［J］. 工業工程與管理， 2022，27（5）：149-158. （Zhong Weiya， Cui Jia. Joint scheduling algorithms for orders’ picking and delivery in new retail enterprise［J］. Industrial Engineering and Management， 2022，27（5）： 149-158.）

［7］Martins L D， Gonzalez-Neira E M， Hatami S， et al. Combining production and distribution in supply chains： the hybrid flow-shop vehicle routing problem［J］. Computers amp; Industrial Engineering， 2021，159（9）：107486.

［8］王思涵， 李新宇， 高亮， 等. 分布式車間調度研究綜述［J］. 華中科技大學學報：自然科學版， 2022，50（6）： 1-10. （Wang Sihan， Li Xinyu， Gao Liang， et al. A review of distributed shop scheduling problems［J］. Journal of Huazhong University of Science amp; Technology： Natural Science Edition， 2022，50（6）： 1-10.）

［9］Hatami S， Ruiz R， Andrés-Romano C. The distributed assembly permutation flowshop scheduling problem［J］. International Journal of Production Research， 2013，51（17）： 5292-5308.

［10］Sang Hongyan， Pan Quanke， Li Junqing， et al. Effective invasive weed optimization algorithms for distributed assembly permutation flowshop problem with total flowtime criterion［J］. Swarm and Evolutionary Computation， 2019，44（2）： 64-73.

［11］雷德明， 王甜. 基于改進蛙跳算法的分布式兩階段混合流水車間調度［J］. 控制與決策， 2021，36（1）： 241-248. （Lei Deming， Wang Tian. An improved shuffled frog leaping algorithm for the distributed two-stage hybrid flow shop scheduling［J］. Control and Decision， 2021，36（1）： 241-248.）

［12］Song Hongbo， Lin Jian. A genetic programming hyper-heuristic for the distributed assembly permutation flow-shop scheduling problem with sequence dependent setup times［J］. Swarm and Evolutionary Computation， 2021，60（2）：100807.）

［13］Wu Xiuli， Liu Xiajing， Zhao Ning. An improved differential evolution algorithm for solving a distributed assembly flexible job shop scheduling problem［J］. Memetic Computing， 2019，11（4）： 335-355.

［14］郭晨， 曾思豪， 郭鈞， 等. 混合分布估計算法求解模糊分布式裝配柔性車間調度問題［J］. 系統工程理論與實踐， 2021，41（4）： 1037-1048. （Guo Chen， Zeng Sihao， Guo Jun， et al. Hybrid estimation of distribution algorithm for distributed assembly flexible job shop scheduling problem with fuzzy processing time［J］. Systems Engineering-Theory amp; Practice， 2021，41（4）： 1037-1048.）

［15］Mirjalili S， Lewis A. The whale optimization algorithm［J］. Advances in Engineering Software， 2016，95（5）： 51-67.

［16］Petrovic M， Miljkovic Z， Jokic A. A novel methodology for optimal single mobile robot scheduling using whale optimization algorithm［J］. Applied Soft Computing， 2019，81（8）： 105520.

［17］Singh P， Prakash S. Optical network unit placement in fiber-wireless （FiWi） access network by whale optimization algorithm［J］. Optical Fiber Technology， 2019，52（11）： 101965.

［18］李寶帥， 葉春明. 混合鯨魚優化算法求解柔性作業車間調度問題［J］. 計算機系統應用， 2022，31（4）： 244-252. （Li Baoshuai， Ye Chunming. Hybrid whale algorithm for flexible job shop scheduling problem［J］. Computer Systems amp; Applications， 2022，31（4）： 244-252.）

［19］閆旭， 葉春明， 姚遠遠. 量子鯨魚優化算法求解作業車間調度問題［J］. 計算機應用研究， 2019，36（4）： 975-979. （Yan Xu， Ye Chunming， Yao Yuanyuan. Solving Job-Shop scheduling problem by quantum whale optimization algorithm［J］. Application Research of Computers， 2019，36（4）： 975-979.）

［20］欒飛， 蔡宗琰， 吳書強， 等. 求解低碳車間調度問題的改進鯨魚算法［J］. 機械科學與技術， 2020，39（5）： 721-728. （Luan Fei， Cai Zongyan， Wu Shuqiang， et al. Improved whale optimization algorithm of scheduling problem for low carbon workshop［J］. Mechanical Science and Technology for Aerospace Engineering， 2020，39（5）： 721-728.）

［21］Jiang Tianhua， Zhang Chao， Sun Qiming， et al. Green job shop scheduling problem with discrete whale optimization algorithm［J］. IEEE Access， 2019，7： 43153-43166.

［22］羅文沖， 錢斌， 胡蓉， 等. 超啟發式交叉熵算法求解分布式裝配柔性作業車間調度問題［J］. 控制理論與應用， 2021，38（10）： 1551-1568. （Luo Wenchong， Qian Bin， Hu Rong， et al. Hyper-heuristic cross-entropy algorithm for distributed assembly flexible Job-Shop scheduling problem［J］. Control Theory amp; Applications， 2021，38（10）： 1551-1568.）