迭代貪婪算法優(yōu)化分布式阻塞流水車間成組魯棒調(diào)度問題

摘 要：為了優(yōu)化復雜生產(chǎn)環(huán)境中生產(chǎn)計劃的魯棒性，確保不同場景下生產(chǎn)調(diào)度的穩(wěn)定性，此研究將多生產(chǎn)線單元制造問題抽象為分布式流水車間成組調(diào)度問題，并在此基礎(chǔ)上考慮了實際生產(chǎn)中常見的零緩沖區(qū)、加工時間不確定性和交付時間窗口等約束。首先，構(gòu)建了以魯棒性為優(yōu)化目標的混合整數(shù)線性規(guī)劃模型并使用Gurobi求解器驗證其正確性；然后，提出了一種改進的空閑時間插入方法以適應阻塞約束和成組約束；接著，將上述改進空閑時間插入方法融入到自適應協(xié)同迭代貪婪算法中，該算法針對問題的多場景、問題求解的時間復雜度等，分別設(shè)計了有針對性的初始化方法、自適應破壞策略以及快速重構(gòu)和局部搜索方法。最后，在生成的810個實例中，與其他高效的元啟發(fā)式算法相比，所提出的算法在有限的時間內(nèi)得到了魯棒最優(yōu)解。研究結(jié)果表明，該算法能夠應對不確定因素和復雜的約束，在解決各種規(guī)模的問題上都表現(xiàn)出了良好的性能。

關(guān)鍵詞： 分布式調(diào)度； 成組調(diào)度； 不確定加工時間； 交付時間窗口； 迭代貪婪算法； 空閑時間插入

中圖分類號： TP13 文獻標志碼： A 文章編號： 1001-3695（2025）02-020-0469-08

doi： 10.19734/j.issn.1001-3695.2024.07.0232

Optimization of iterated greedy algorithm for distributed blocking

flowshop group robust scheduling problem

Wang Yizheng¹， Wang Yuting^1’， Han Yuyan¹， Li Huan¹， Gao Kaizhou²

（1.School of Computer Science， Liaocheng University， Liaocheng Shandong 252059， China; 2.Macau Institute of Systems Engineering， Macau University of Science amp; Technology， Macau 999078， China）

Abstract：To optimize the robustness of production planning in complex manufacturing environments and ensure stable production scheduling across different scenarios， this study abstracted the multi-production line cellular manufacturing problem into a distributed flowshop group scheduling problem， incorporating common constraints such as zero buffer zones， processing time uncertainties， and delivery time windows. Firstly， the study developed a mixed-integer linear programming model with robustness as the optimization objective and validated it using the Gurobi solver. Then， this paper proposed a modified idle time insertion method to meet blocking and grouping constraints. It designed an adaptive collaborative iterated greedy algorithm， which was driven by the modified idle time insertion method， to address this problem. This algorithm featured an initialization method that accounted for the intrinsic connections of multiple scenarios， an adaptive destruction strategy， and accelerated reconstruction and local search methods. Finally， in 810 generated instances， the proposed algorithm achieved better solutions within limited time compared to other efficient metaheuristic algorithms. The results demonstrate that the algorithm effectively handles uncertainties and complex constraints， showing strong performance across various problem sizes.

Key words：distributed scheduling; group scheduling; uncertain processing time; delivery time windows; iterated greedy algorithm; idle time insertion

0 引言

刷電路板組裝的表面貼裝工藝是單元制造模式的典型代表^［1］，其特點是將工藝相似的工件分到同一個組內(nèi)，減少切換工藝調(diào)整機器所花費的時間^［2］，而一些大型印刷電路板企業(yè)，比如華為、富士康等，通常在不同的地方擁有多條相同的生產(chǎn)線^［3］。上面的生產(chǎn)模式可以被抽象為存在序列依賴設(shè)置時間（sequence dependent setup time， SDST）的分布式流水車間成組調(diào)度問題（distributed flowshop group scheduling problem， DFGSP）^［4］。

生產(chǎn)線的不同機器之間通常存在沒有緩沖區(qū)或者緩沖區(qū)不足的情況^［5］，導致了阻塞的產(chǎn)生。具體表現(xiàn)為：若下一臺機器不處于空閑狀態(tài)，該工件必須停留在當前機器上，直到下一臺機器空閑^［6］。在DFGSP中考慮阻塞約束形成了分布式阻塞流水車間成組調(diào)度問題（distributed blocking flowshop group scheduling problem， DBFGSP）。

由于機器維護、工人技能水平差異以及生產(chǎn)環(huán)境變化等因素^［7］，工件的具體加工時間通常具有可變性和不確定性，所以通過預先確定加工時間得到的解可能在各種不確定條件下表現(xiàn)不佳^［8］。為了得到一個在各種情況下都表現(xiàn)較好的解^［9］，本文采用多場景方法來表達不確定加工時間，即生成多組加工時間，每組加工時間代表一個場景^［10］?？紤]到不確定加工時間（uncertain processing time， UPT），本文研究的問題用DBFGSP-UPT表示。

客戶的滿意度對于企業(yè)的發(fā)展至關(guān)重要^［11］。通常情況下，客戶會要求一個交付時間窗口^［12］，如果產(chǎn)品在對應的交付時間窗口內(nèi)完工，可以提高客戶滿意度，如果延遲交付，會降低客戶滿意度，影響企業(yè)效益^［13］；如果過早交付，會造成庫存積壓，對企業(yè)造成倉儲壓力^［14］。在這種背景下，總加權(quán)提前和延遲（total weighted earliness and tardiness， TWET）成為一個關(guān)鍵指標，反映了庫存積壓和交貨延遲產(chǎn)生的影響。本文的優(yōu)化目標為魯棒目標（robust objective， RO），它集成了TWET在各種場景下的均值和標準差，不僅考慮了算法的平均性能，還考慮了算法在不同場景之間的可變性。以TWET為目標的分布式流水車間調(diào)度已經(jīng)是NP-hard問題^［15］，DBFGSP-UPT的約束和目標增加了其復雜性，因此DBFGSP-UPT也是NP-hard問題。

DBFGSP-UPT存在如下難點：

a）多種約束使得問題存在較高的復雜性。目前，相關(guān)的數(shù)學模型并未考慮到阻塞約束、交付時間窗口以及不確定加工時間。因此，如何在數(shù)學模型中引入上述約束是一個亟待解決的問題。

b）帶有交付時間窗口的相關(guān)車間調(diào)度問題大量使用了空閑時間插入方法以優(yōu)化目標值，但傳統(tǒng)的空閑時間插入方法只推遲最后一臺機器上的工件的加工過程，不適用于阻塞約束?？紤]到阻塞和成組約束，空閑時間插入方法如何進行改進以適應DBFGSP-UPT是一個關(guān)鍵問題。

c）DBFGSP-UPT包含工廠分配、組調(diào)度以及組內(nèi)工件調(diào)度三個強耦合的子問題，同時在所有場景下均需要計算目標值，計算時間復雜度較高。因此，設(shè)計能夠?qū)崿F(xiàn)子問題協(xié)同交互的高效算法是至關(guān)重要的。

為解決上述問題，優(yōu)化生產(chǎn)調(diào)度，得到一個具有魯棒性的解，本研究主要做了如下貢獻：

a）針對現(xiàn)有數(shù)學模型未考慮阻塞、交付時間窗口以及不確定加工時間約束的問題，建立了以魯棒性為優(yōu)化目標的DBFGSP-UPT問題的混合整數(shù)線性規(guī)劃（mixed integer linear programming， MILP）模型，并采用Gurobi驗證了其正確性。

b）提出了一種適用于阻塞和成組約束的空閑時間插入方法，該方法在所有機器上均需要插入空閑時間，實現(xiàn)在不違反阻塞約束的前提下減小工件總提前時間的目的。

c）為解決DBFGSP-UPT分解出的多個子問題，本文設(shè)計了一種改進空閑時間插入方法驅(qū)動的自適應協(xié)同迭代貪婪算法，該算法具有結(jié)構(gòu)簡單、參數(shù)較少、收斂速度快、迭代次數(shù)多等優(yōu)勢，適合用于求解復雜的調(diào)度問題。本文設(shè)計的算法包含一種考慮多場景內(nèi)在聯(lián)系的初始化方法、協(xié)同機制，以及快速的重構(gòu)和局部搜索等策略，能夠更好地針對問題特性進行優(yōu)化。

1 問題描述及數(shù)學模型

1.1 問題描述

DBFGSP-UPT的具體描述如下：有f個相同的工廠/生產(chǎn)線，每個工廠都是由m臺機器組成的流水車間結(jié)構(gòu)，每臺機器對應一道工序。相鄰兩臺機器之間不存在緩沖區(qū)，當一個工件處理完成后，如果下一臺機器被占用，則必須在當前機器上等待，直到下一臺機器可用?，F(xiàn)有n個工件被分為δ個組，每個工件加工需要經(jīng)過全部m道工序且各組之間存在SDST。DBFGSP-UPT采用個場景刻畫加工時間的不確定。

假設(shè)在0時刻，所有工件和機器都是可用的。同一機器在同一時刻只能加工一個工件，一個工件在同一時刻也只能被一個機器加工。由于SDST的存在，第一個被加工的組也存在初始的設(shè)置時間。一個組中的工件必須連續(xù)不間斷地加工，不能被其他組的工件打斷。每個組都對應一個交付時間窗口［d^－，d⁺］，其中，d^－和d⁺分別對應最早和最晚交付時間。當一個組的完工時間偏離對應的交付時間窗口時就會受到懲罰，懲罰的計算方式為時間差乘以對應的提前或延遲權(quán)重。對于每個場景，都要計算所有組的懲罰值的總和，也就是TWET。根據(jù)所有場景下TWET的均值和標準差計算出魯棒優(yōu)化目標值。DBFGSP-UPT的目標就是最小化魯棒目標值，以應對不同場景。

1.2 數(shù)學模型

數(shù)學模型涉及的符號及解釋如表1所示，決策變量及解釋如表2所示。

目標：

RO=Minimize（ρ×E^α+（1－ρ）×S^α）（1）

約束：

式（1）定義了魯棒優(yōu)化目標。式（2）和（3）規(guī)定了每個組必須有且僅有一個直接前驅(qū)組和一個直接后繼組。式（4）和（5）限制虛擬組作為直接前驅(qū)和直接后繼的次數(shù)不能超過f次。式（6）要求虛擬組作為直接前驅(qū)和直接后繼的次數(shù)保持一致。式（7）和（8）規(guī)定每個組中的每個工件，包括兩個虛擬工件，必須建立前驅(qū)和后繼關(guān)系。式（9）確保對于機器M_i上的每個工件Ω_j，g，其離開時間不能早于完工時間。在每個場景下，對于來自同一個組Δ_g的任意兩個工件Ω_j，g和Ω_{j′，g}，式（10）限制工件Ω_j′，g在機器M_i上的完工時間不小于工件Ω_j，g在同機器上的離開時間加Ω_j′，g在該機器上的加工時間。在每個場景下，對于任意給定的組Δ_g及其直接后繼組Δ_g′，式（11）確保工件Ω_j′，g′的完工時間不小于工件Ω_j，g的離開時間加上工件Ω_{j′，g′}的加工時間和組Δ_g與Δ_g′之間的設(shè)置時間。式（12）強調(diào)第一個組在開始加工之前需要一個初始設(shè)置時間。其中式（10）～（12）共同作用以消除潛在的子環(huán)。式（13）規(guī)定每個工件在下一臺機器上的完工時間等于該機器上的離開時間加上下一臺機器上的加工時間。式（14）定義了組的完工時間等于組內(nèi)工件在最后一臺機器上的最大離開時間。式（15）～（17）共同定義了總提前、總延遲和TWET。式（18）和（19）通過所有場景下的TWET計算均值和標準差。

對式（1）（18）和（19）的分析表明，RO是為了平衡不同場景下的平均性能和它們的穩(wěn)定性。在式（1）中，ρ（ρ∈［0，1］）作為一個偏好系數(shù)，作用在于引導RO的焦點是放在平均TWET還是各個場景下的穩(wěn)定性。若ρ的取值較小，說明RO更加偏向于追求穩(wěn)定性，反之則優(yōu)先考慮最小化平均TWET。根據(jù)文獻［9］，本文將ρ的取值設(shè)置為0.95。

2 空閑時間插入驅(qū)動的自適應協(xié)同迭代貪婪算法

2.1 編碼方法

DBFGSP-UPT可以被分解為三個耦合的子問題：組在各工廠中的分配問題、各工廠中組序列的調(diào)度問題以及各個組中的工件序列調(diào)度問題。鑒于此，本文采用兩個二維向量來表示一個完整的解。第一個二維向量由f個一維向量組成，表示f個工廠中的組序列；第二個二維向量由δ個一維向量組成，表示δ個組中的工件序列。一個完整解的數(shù)學表示為：π={π₁，π₂，…，π_w，…，π_f}和τ={τ₁，τ₂，…，τ_δ}。π_w={π¹_w，π²_w，…，πⁱ_w，…，π^δ_ww}為第w個工廠的組序列，其中πⁱ_w表示工廠w中第i個組，δ_w表示工廠w中組的數(shù)量。為了簡化符號，本文使用［i，w］表示πⁱ_w。也就是說πⁱ_w=Δ_{［i，w］}。同樣，組πⁱ_w中的工件序列表示為τ_［i，w］={τ¹_{［i，w］}，τ²_［i，w］，…，τⁿ_{［i，w］［i，w］}}，第j個工件τ^j_{［g，w］}用Ω_{［j］，［g，w］}表示。

2.2 算法框架

通常情況下，為了更好地求解復雜調(diào)度問題，迭代貪婪算法（iterated greedy algorithm， IGA）在求解不同問題時會根據(jù)問題特性設(shè)計有針對性的策略^［16］。由于本文所考慮的問題需要解決兩個關(guān)鍵問題：a）如何協(xié)同組間調(diào)度和組內(nèi)工件調(diào)度這兩個過程；b）為了使過早完工的組盡可能貼近其交付時間窗口，如何針對阻塞約束設(shè)計空閑時間插入策略。鑒于此，本文提出了一種空閑時間插入方法驅(qū)動的自適應協(xié)同IGA（idle time insertion-driven adaptive cooperation iterated gteedy， ACIG_ITI）求解DBFGSP-UPT。針對關(guān)鍵問題1，所提算法設(shè)計了組調(diào)度迭代過程和工件調(diào)度迭代過程。組調(diào)度迭代過程包含破壞組（Des-Group）、重構(gòu)組（Con-Group）和局部搜索組序列（LS-Group）。工件調(diào)度迭代過程包含破壞工件（Des-Job）、重構(gòu)工件（Con-Job）和局部搜索工件序列（LS-Job）。本文引入了閾值GJ來動態(tài)協(xié)調(diào)這兩個迭代過程。在組調(diào)度迭代過程中，如果得到的解比之前好，就接受得到的解，反之則以5%的概率接受差解，以避免算法陷入局部最優(yōu)。在工件調(diào)度迭代過程中，由于優(yōu)化效果相對有限，所以采用貪婪接受方式。針對關(guān)鍵問題2，本文設(shè)計了一種適用于阻塞和成組約束的空閑時間插入方法，該方法在所有機器上均需要插入空閑時間，實現(xiàn)在不違反阻塞約束的前提下減小工件總提前時間的目的。圖1是ACIG_ITI的流程。

2.3 改進的空閑時間插入方法

由于問題的阻塞和成組約束，現(xiàn)有的空閑時間插入方法不能直接用于本文研究的問題，所以本文提出了一種改進的空閑時間插入方法（modified idle time insertion，MITI）。MITI的核心概念是塊，如果不同的組之間不能插入空閑時間，那么這些組就被視為一個塊，空閑時間只能在塊之前插入。本文創(chuàng)建了三個集合來存儲塊內(nèi)不同狀態(tài)的組：Γ_E存儲提前完工的組，Γ_O存儲按時完工的組，Γ_T存儲延遲完工的組。相應地，用SW_E和SW_T分別表示Γ_E中組的總提前權(quán)重和Γ_T中組的總延遲權(quán)重。如果塊內(nèi)組的完工時間等于最晚交付時間，那么這些組會被歸入Γ_T而不是Γ_O，因為即使插入最小單位的空閑時間也會導致延遲。只有當SW_Egt;SW_T時，才會對塊進行空閑時間插入。

MITI的第一步是對工件進行預處理。對于每個組，首先計算其在最后兩臺機器上的離開時間。同時，對于每個組從倒數(shù)第二到第一個的每個工件，計算該工件在最后兩臺機器上的離開時間與下一個工件的開始時間的間隔，設(shè)θ為這些間隔的最小值；然后，將該工件在最后一臺機器上的開始時間、完工時間和離開時間推遲θ；最后，通過從組中第一個工件的開始時間中減去設(shè)置時間，確定每個組在最后兩臺機器上的開始時間。

MITI的主循環(huán)重點關(guān)注提前完工的組，因為推遲它們的完工/離開時間可以獲得收益。該循環(huán)按逆向運行，從最后一個組開始。對于提前完工的組，首先計算其完工時間與最早交付時間的間隔θ₁，當前組在最后兩臺機器上的離開時間與下一個組的開始時間的最小間隔θ₂，以及前一個塊提供的空閑時間λ。通過評估可用的空閑時間，推遲組在最后兩臺機器上的開始和離開時間，并更新TWET值。接下來，更新塊的信息，包括塊的索引i、塊的開始組bs_i、塊的結(jié)束組be_i，以及為前一個組提供的空閑時間λ_i。如果不存在塊，則為當前組創(chuàng)建一個新的塊。當θ₁=θ₂時，當前組從提前完成變成按時完成，并與下一個組組成一個新的塊；如果θ₁lt;θ₂，則當前組形成一個新的塊；如果θ₁gt;θ₂，則當前塊與下一個塊合并，基于塊內(nèi)組的狀態(tài)更新集合和權(quán)重。當SW_Egt;SW_T時，插入空閑時間是有利的。

使用三個變量來確定空閑時間的大小：θ₃（塊內(nèi)提前完工的組的完工時間與對應的最早交付時間的間隔的最小值）、θ₄（塊內(nèi)按時完工的組的完工時間與對應的最晚交付時間的間隔的最小值）和θ₅（下一個塊提供的空閑時間）。塊內(nèi)所有組可插入的空閑時間的大小為θ₃、θ₄和θ₅中的最小值。插入空閑時間后，更新最后兩臺機器上的開始和離開時間，并更新TWET的值、當前塊提供的空閑時間和前一個塊提供的空閑時間。如果空閑時間是θ₃，組的狀態(tài)從提前完工變?yōu)榘磿r完工，更新對應的集合和權(quán)重。如果空閑時間是θ₄，組的狀態(tài)從按時完工變?yōu)檠舆t完工，更新對應的集合和權(quán)重。如果空閑時間是θ₅，當前塊與前一個塊合并，需要考慮前一個塊內(nèi)組的狀態(tài)，更新對應的集合和權(quán)重及塊信息。這個過程會持續(xù)進行，直到所有組都被考慮完。

為了更加清晰地闡述MITI的過程，圖2給出了一個1個工廠4個組的例子。4個組的提前/延遲權(quán)重分別為（2，4）、（5，2）、（3，2）和（3，3），交付時間窗口分別為（48，64）、（68，80）、（53，75）和（86，100）。圖2（a）展示了工廠的初始狀態(tài)。圖2（b）展示了工廠中的組經(jīng)過預處理之后的狀態(tài)，此時工廠內(nèi)TWET的值為199。對于組［4，1］，其完工時間C^ζ_{［4，1］}等于77，最早交付時間d^－_［4，1］是86，因此θ₁=86－77=9。由于后面沒有組和塊，所以θ₂和λ都為正無窮。該組可插入的空閑時間大小為9，TWET的值降為172。由于當前沒有塊，所以如圖2（c）所示，該組形成了一個索引i=1、bs₁=［4，1］、be₁=［4，1］、λ₁=9的塊。如圖2（d）所示，接下來開始處理組［3，1］。該組的狀態(tài)為準時，并且形成了一個i=2、bs₂=［3，1］、be₂=［3，1］、λ₂=0的塊。接下來開始處理組［2，1］，對于該組，θ₁=68－42=26、θ₂=min（47－42，40－39）=1、λ=0。如圖2（e）所示，可插入的空閑時間為1，TWET值降為167。組［2，1］和［3，1］組成了一個bs₂=［2，1］、be₂=［3，1］、λ₂=0的塊。此時集合Γ_E中包含組［2，1］，Γ_O中包含組［3，1］，Γ_T中不存在組，SW_E=5，SW_T=0，可以插入空閑時間。θ₃=25、θ₄=19、θ₅=9，因此可以插入的空閑時間大小為9。如圖2（f）所示，TWET值降為122，組［2，1］、［3，1］和［4，1］組成了一個bs₁=［2，1］、be₁=［4，1］、λ₁=9的塊。此時SW_E=5、SW_T=0、θ₃=16、θ₄=10，θ₅為正無窮，因此可插入的空閑時間大小為10。如圖2（g）所示，TWET值降為72，此時SW_E=5、SW_T=2、θ₃=6、θ₄=4，θ₅為正無窮，因此可插入大小為4的空閑時間。如圖2（h）所示，TWET值降為60，此時SW_E=5，SW_T=5，無法繼續(xù)插入空閑時間。最后，處理組［1，1］，對于該組，θ₁=21、θ₂=27、λ=23，因此可插入空閑時間的大小為21。如圖2（i）所示，TWET值降為18，此時組［1，1］形成了一個新的塊，由于沒有后續(xù)的組，MITI過程結(jié)束。

2.4 復合啟發(fā)式方法

Nawaz等人^［17］提出了NEH啟發(fā)式方法，在調(diào)度問題中廣受認可和應用。NEH2_en在各種變體中性能相對較好，使其成為解決復雜調(diào)度問題的首選。在本研究中，將NEH2_en與多場景加工時間結(jié)合，提出了一種改進的初始化方法，稱為MNEH2_en，其過程如下：首先采用最早到期日規(guī)則（earliest due date，EDD），將組的最早交付時間升序排序得到序列GS；然后，對于組內(nèi)的工件，按照工件在所有場景下的加工時間的總和降序排序，通過計算其在所有場景下的平均加工時間以綜合考慮各個場景之間的聯(lián)系；其次，對于每個組，探索所有可以插入的位置，選擇使得TWET最小的位置插入。為了擴大解空間的搜索范圍，在確定最佳位置之后，從相鄰位置隨機再選擇一個組，進行重新插入以進一步優(yōu)化TWET。這個優(yōu)化過程持續(xù)執(zhí)行，直至得到一個完整的解。最后，使用空閑時間插入方法優(yōu)化目標值。MNEH2_en的流程如算法1所示。

算法1 MNEH2_en

輸入：GS和工件序列τ。

輸出：［π，τ］，TWET_SET。

計算每個工件的平均加工時間

π_w←?，w=1，2，…，f

π←{π₁，π₂，…，π_f}

TWET_w←0，w=1，2，…，f

TWET_SET={TWET₁， TWET₂，…， TWET_f}

for g=1 to δ do

for w=1 to f do

在工廠π_w中所有可行位置測試組GS_g

TWET^*_w記錄了最小的TWET值，P_w記錄了對應的位置

end for

w^*←argmin^f_w=1（TWET^*_w）

將組GS_g插入至工廠π_w^*中的位置P_w^*

TWET_w^*←TWET^*_w

隨機從位置P_w^*－1或者P_w^*+1選擇一個組Ξ

for w=1 to f do

在工廠π_w中所有可行位置測試組Ξ

TWET^*_w記錄了最小的TWET值，P_w記錄了對應的位置

end for

w^*←argmin^f_w=1（TWET^*_w）

將組Ξ插入至工廠π_w^*中的位置P_w^*

TWET_w^*←TWET^*_w

end for

算法1涉及到δ個組尋找最優(yōu)位置插入的過程，需嘗試所有的可行位置，而計算目標值需要遍歷m個機器，因此算法1的時間復雜度為O（δ²×m）。因為組序列被存儲在各自的工廠中，所以其空間復雜度為O（f）。而如果使用傳統(tǒng)的NEH2_en以RO作為優(yōu)化目標，還需要額外遍歷個場景，時間復雜度為O（δ²××m），遠大于算法1的時間復雜度。

2.5 自適應破壞策略

本文針對組優(yōu)化（Des-Group）和工件優(yōu)化（Des-Job）提出了兩種自適應破壞策略來擴大解空間的搜索范圍，從而避免陷入局部最優(yōu)。

對于Des-Group，根據(jù)文獻［18］，組破壞的范圍在2～7最佳，因此創(chuàng)建了一個序列DG={2，3，4，5，6，7}。在每次迭代時，從DG中隨機選擇一個元素作為本次破壞組的數(shù)量，從所有工廠中隨機移除對應數(shù)量的組。如果在這次迭代中得到的解相比于之前有所改進，說明本次破壞的數(shù)量更有潛力，就將選擇的元素添加進DG中，以增大下一次被選中的概率。對于Des-Job，采用同樣的方式自適應選擇要進行工件破壞的組的數(shù)量，從這些組中隨機移除一半工件。

2.6 空閑時間插入方法驅(qū)動的重構(gòu)策略

重構(gòu)策略也分為Con-Group和Con-Job，兩者都采用貪婪插入方法，旨在最小化RO。為了提高Con-Group的效率，本文使用了一種加速策略。簡而言之，在嘗試將一個組插入到工廠的第一個位置之后，下一次嘗試的位置不是下一個（當前位置索引+1），而是當前位置索引+2。如果在某個位置得到的解比之前位置的解更好，那么就嘗試該位置左右的位置。這種步進方法基于一個假設(shè)：如果在新位置發(fā)現(xiàn)了最佳或改進的解，則在該位置附近進一步探索，可能會獲得更好的結(jié)果。這一策略減少了在非必要插入位置上花費的時間，從而簡化了尋優(yōu)過程。由于在工件優(yōu)化的過程中，每個工件在其組內(nèi)可插入的位置非常有限，所以僅采用貪婪插入策略。不論是Con-Group還是Con-Job，在評估每一個位置時，都使用了MITI方法。其中Con-Group的流程如算法2所示。

算法2 Con-Group

輸入：［π，τ］，被破壞的組序列EG。

輸出：［π，τ］，RO^best。

for g=1 to |EG| do

RO^best←+∞

for w=1 to f do

Pos←0

while Poslt;δ_w do

RO^Temp←在工廠π_w的Pos位置測試組EG_g //MITI

if RO^Templt;RO^best then

在位置Pos－1和Pos+1測試組EG_g //MITI

RO^best←min RO^Temp

else

Pos←Pos+2

end if

end while

end for

w^*←RO^best對應的工廠

Pos_w^*←RO^best在工廠π_w^*中對應的位置

將組EG_g插入至工廠π_w^*中的位置Pos_w^*

end for

對最后一個被重構(gòu)的組尋找最好位置時，需面對可插入位置最多的情況，在最壞的情況下，該組每嘗試一個位置都比之前嘗試的位置更好，在這種情況下，需要嘗試完所有的位置，還需遍歷個場景和m個機器，因此最壞情況下算法2的時間復雜度為O（|EG|×δ××m），空間復雜度為O（f）。相比之下，傳統(tǒng)的貪婪重構(gòu)方法時間復雜度為O（|EG|×δ××m），等于算法2最壞情況下的時間復雜度，因此算法2的時間復雜度在絕大多數(shù)時候低于傳統(tǒng)的貪婪重構(gòu)方法。

2.7 空閑時間插入方法驅(qū)動的局部搜索策略

相似地，局部搜索也分為LS-Group和LS-Job。如算法3所示，LS-Group首先獲取一個隨機打亂的組序列，記為GS，并初始化變量Counter=0。然后按照順序?qū)S中的組從當前位置移除，在所有工廠的所有可插入位置進行嘗試，記錄最佳結(jié)果，如果最佳結(jié)果優(yōu)于之前的結(jié)果，就將該組插入到對應的最佳位置，并重置Counter=0，否則Counter+1。重復這個過程，直到Counter不小于組的數(shù)量。由于工件優(yōu)化的效果不如組優(yōu)化顯著，所以LS-Job采用選擇性優(yōu)化方法，對每個組內(nèi)的隨機半數(shù)（向上取整）工件進行局部搜索。與LS-Group類似，首先初始化Counter=0。對于選中進行局部搜索的每個工件，在組內(nèi)嘗試所有可行的插入位置，并記錄最好結(jié)果。如果結(jié)果優(yōu)于之前的結(jié)果，就將該工件插入至該位置，并重置Counter=0，否則Counter+1。重復這個過程，直到Counter不小于該組中工件的數(shù)量才開始下一個組中工件的局部搜索。

同理，算法3涉及到對所有的組重新找最好位置的過程，計算目標值的過程中需要遍歷個場景和m個機器，因此時間復雜度為O（δ²××m），空間復雜度為O（f），其時間和空間復雜度均等于傳統(tǒng)局部搜索的復雜度。

算法3 LS-Group

輸入：［π，τ］、RO。

輸出：［π，τ］、RO。

GS←對組{Δ₁，Δ₂，…，Δ_δ}隨機排序

Counter←0，Pos←0

while Counterlt;δ do

o←組GS_Pos所在的工廠索引

originalRO←RO

π_o←π_o＼{GS_Pos}

for w=1 to f do

在工廠π_w中的所有可行位置測試組GS_Pos //MITI

用RO^*_w表示最小的RO值，用P_w表示對應的位置

end for

w^*←argmin^f_w=1（RO^*_w）

if RO^*_wlt;originalRO then

將組GS_Pos插入至工廠π_w^*的位置P_w^*

RO←RO^*_i^*

Counter←0

else

將組GS_Pos插入回原位置

Counter←Counter+1

end if

Pos←Pos%δ+1

end while

3 實驗設(shè)計與分析

3.1 實驗環(huán)境與參數(shù)校驗

本文的實驗平臺是一臺搭載了Intel Core i7 12700處理器和16 GB內(nèi)存的計算機，操作系統(tǒng)為Windows 11專業(yè)版。所有算法均使用C++在CLion中編寫。算法的運行時間為100×δ×m ms，其中δ和m分別代表組的數(shù)量和機器的數(shù)量。本文使用相對偏差指數(shù)（relative deviation index，RDI）來評估算法的性能，對于給定的實例i，RDI的計算方法如式（20）所示。

RDI_x，i=RO_x，i－RO_best，iRO_worst，i－RO_best，i（20）

其中：RO_x，i代表算法x得到的RO值；RO_best，i和RO_worst，i分別代表所有算法取得的最好的和最差的RO值。

ACIG_ITI只有一個可校驗的參數(shù)GJ，根據(jù)經(jīng)驗和文獻［19］，設(shè)置GJ=0.8。

3.2 測試實例生成

由于DBFGSP-UPT還沒有被研究過，所以沒有對應的基準實例，本文為該問題生成了測試實例。具體來說，本文設(shè)計了十個場景，設(shè)置f={2，3，4}，δ={20，40，60}，m={2，4，6}。每個組中工件的數(shù)量在1～10隨機生成，SDST的大小在1～80隨機生成。不確定加工時間通過一個由upt₁和upt₂確定的均勻分布來表示，記作U［upt₁，upt₂］。upt₁和upt₂分別來自兩個獨立的均勻分布，分別為U［1，10×Υ₁］和U［upt1+1，upt1×（1+Υ₂）］。其中，參數(shù)Υ₁的取值為{0.4，0.6}，Υ₂的取值為{1.0，1.5，2.0，2.5，3.0}。這些參數(shù)被用來調(diào)整加工時間的范圍，形成了總共10種不同的規(guī)模（|Υ₁|×|Υ₂|）。因此，實驗測試實例總共包含270種不同的規(guī)模（3×3×3×10）。每種規(guī)模下有3個不同的實例，共有810個測試實例（270×3）。為了給每個組創(chuàng)建交付時間窗口，本文改進了文獻［15］中的方法以適應加工時間不確定的情況。對于每個實例，首先使用修改后的LPT規(guī)則對所有組及其內(nèi)部的工件進行排序。接下來，使用NEH2啟發(fā)式方法^［20］確定一個完整的調(diào)度序列。最后，根據(jù)式（21）～（23）生成每個組的交付時間窗口。

d_g=max（0，U［C_max×（1－L－R2），C_max×（1－L+R2）］）（21）

d^－_g=max（d_g×（1－H100），∑ζ=1 ∑|τ_g|j=1 ∑mi=1p^ζ_j，g，i×（1+H100）/）（22）

d⁺_g=max（d_g×（1+H100），∑ζ=1 ∑|τ_g|j=1 ∑mi=1p^ζ_j，g，i×（1+3×H100）/）（23）

其中：C_max表示最大完工時間；參數(shù)L和R分別表示延遲因子和窗口范圍，均為0.2^［15］；此外，變量H在1～10均勻分布，每個組的提前權(quán)重和延遲權(quán)重也由1～5的均勻分布決定。

3.3 數(shù)學模型驗證

本文使用Gurobi求解器驗證了所提出MILP模型的正確性，同時與ACIG_ITI進行比較，以進一步評估所提算法在6個小規(guī)模實例上的性能。為了減輕MILP模型的計算負擔，將場景數(shù)量設(shè)置為5。MILP模型和ACIG_ITI的運行時間分別為3 600 s和δ×m×100 ms。表3列出了MILP模型和ACIG_ITI取得的RO值以及對應的時間，表現(xiàn)優(yōu)異的結(jié)果以粗體顯示。

從表3中可以看出，MILP模型是正確的，但是問題的規(guī)模和約束的數(shù)量極大地影響了模型的性能，在解決復雜的調(diào)度問題方面，MILP模型并不理想。然而，ACIG_ITI能夠快速獲得高質(zhì)量的解，說明其更適合解決復雜的調(diào)度問題。

3.4 策略有效性驗證

為了驗證所提出改進空閑時間插入方法的有效性，將ACIG_ITI與其變體ACIG進行比較，ACIG為ACIG_ITI省略了MITI策略。每個算法在810個例子上獨立運行五次，表4列出了ACIG和ACIG_ITI取得的平均魯棒目標值（average robust objective，ARO）。

從表4可以看出，ACIG_ITI在所有規(guī)模的實例中，ARO指標均優(yōu)于ACIG，ACIG_ITI的平均ARO為10 729.604 71，相比ACIG（17 078.529 27），降低了37.17%，兩者之間的巨大差距顯示了改進空閑時間插入方法的顯著影響。

3.5 算法性能比較

由于DBFGSP-UPT問題尚未被研究，沒有現(xiàn)成的算法可以直接解決這個問題。為了評估所提算法的有效性，本文選擇了以下四種先進的元啟發(fā)式算法進行對比：sIGA^［10］和sILSA^［10］用于解決分布式流水車間魯棒調(diào)度問題，CIGA^［9］用于解決分布式流水車間成組魯棒調(diào)度問題，TIGA^［18］用于解決分布式流水車間成組調(diào)度問題。為了保證公平性，所有上述的算法都結(jié)合了改進空閑時間插入方法以優(yōu)化目標值。本文的實驗包括810個實例，每個算法獨立運行5次以減少隨機因素帶來的影響。實驗ARO和平均相對偏差指數(shù)（average relative deviation index，ARDI）的結(jié)果如表5所示。

在所有測試實例中，ACIG_ITI在RO和RDI兩個指標上都優(yōu)于sIGA、sILSA、CIGA和TIGA。具體來說，在810個實例中，ACIG_ITI的平均RO為10 729.60 471，這個結(jié)果比sIGA（16 897.7141）、sILSA（17 230.4 161）、CIGA（16 357.8 585）和TIGA（15 433.35 625）分別改善了36.50%、37.73%、34.41%和30.48%。此外，ACIG_ITI的ARDI值為0，展示出相對于sIGA（0.862 77）、sILSA（0.970 92）、CIGA（0.761 89）和TIGA（0.708 07）的100%改進?？傮w來看，ACIG_ITI在解決DBFGSP-UPT問題上具有明顯的優(yōu)勢。圖3展示了置信區(qū)間圖，分別展示了每種算法在不同工廠數(shù)量、不同組數(shù)量、不同機器數(shù)量和不同加工時間規(guī)模下的表現(xiàn)。從圖3可以看出，ACIG_ITI在各種規(guī)模的實例中表現(xiàn)了出色的魯棒性。

3.6 非參數(shù)檢驗

為了進一步驗證sIGA、sILSA、CIGA、TIGA和ACIG_ITI五種算法的性能差異，本文采用了Friedman檢驗和Wilcoxon signed-rank檢驗。首先，假設(shè)這幾種算法的性能沒有顯著性差異，并設(shè)定顯著性水平α=0.05。如果p-value小于α，就表示假設(shè)不成立。圖4展示了各算法在ARDI和ARO兩個指標下的顯著性差異。表6中列出了包括排名（Ranks）、樣本數(shù)量（N）、平均RDI/RO值（Means）、標準差（Std.Deviation）、最小RDI/RO值（Min）和最大RDI/RO值（Max）在內(nèi)的具體信息。

從表6中可以看到，在ARDI指標上，ACIG_ITI在排名、均值、標準差、最小值和最大值方面表現(xiàn)最佳（1.00，0.000，0.000 0，0.00，0.00），其余依次為TIGA（2.83， 0.708， 0.180 2， 0.26， 1.00）、CIGA（2.84， 0.762， 0.168 9， 0.26， 1.00）、sIGA（3.55， 0.863， 0.110 6， 0.42， 1.00）和sILSA（4.79， 0.971， 0.087 5， 0.46， 1.00）。在ARO指標上，ACIG_ITI同樣在排名、均值、標準差、最小值和最大值方面表現(xiàn)最佳（1.00， 10 729.605， 9 189.645 7， 615.74， 43 759.46），其余依次為TIGA（2.83， 15 433.356， 13 196.019 8， 1 242.55， 63 211.62）、CIGA（2.84， 16 357.859， 14 138.803 0， 1 216.47， 62 578.22）、sIGA（3.55， 16 897.714， 14 153.568 8， 1 374.08， 62 135.10）和sILSA（4.79， 17 230.416， 14 109.934 8， 1 415.64， 64 424.58）。

表7列出了在ARDI和ARO指標下，Wilcoxon signed-rank檢驗的實驗結(jié)果。在ACIG_ITI與其他四個算法對比中，p-value均為0，實驗表明在α=0.05的水平上，四種算法之間存在統(tǒng)計顯著性差異。

分析結(jié)果表明，ACIG_ITI在810個樣本數(shù)據(jù)中，在所有統(tǒng)計指標（排名、均值、標準差、最小值和最大值）上均出色，顯示了其提供優(yōu)質(zhì)解的能力，還表現(xiàn)出較低的方差，體現(xiàn)了其在解決DBFGSP-UPT問題上的高度可靠性和效率。

4 結(jié)束語

本文研究了現(xiàn)有文獻中未被解決的一個問題：具有不確定加工時間和交付時間窗口的分布式阻塞流水車間成組魯棒調(diào)度問題。針對該問題，首先建立了一個基于順序關(guān)系建模方法的MILP模型并使用Gurobi求解器驗證了其正確性。其次，提出了一種改進的空閑時間插入方法，并將其融入到迭代貪婪算法中對該問題進行求解。實驗結(jié)果表明，提出的算法在解決該問題方面具有高效性和魯棒性。

在未來的研究中，計劃將強化學習算法融入到元啟發(fā)式算法中，利用其學習機制來解決更復雜的調(diào)度問題。

參考文獻：

［1］Wang Yuhang， Han Yuyan， Wang Yuting， et al. Sustainable scheduling of distributed flow shop group： a collaborative multi-objective evolutionary algorithm driven by indicators ［J］. IEEE Trans on Evolutionary Computation， 2024， 28（6）： 1794-1808.

［2］He Xuan， Pan Quanke， Gao Liang， et al. Historical information based iterated greedy algorithm for distributed flowshop group scheduling problem with sequence-dependent setup times ［J］. Omega， 2024， 123： 102997.

［3］Pan Quanke， Gao Liang， Wang Ling. An effective cooperative co-evolutionary algorithm for distributed flowshop group scheduling problems ［J］. IEEE Trans on Cybernetics， 2020， 52（7）： 5999-6012.

［4］袁帥鵬， 李鐵克， 王柏琳， 等. 一類具有特殊阻塞約束的兩階段流水車間成組調(diào)度模型與算法 ［J］. 控制與決策， 2020， 35（7）： 1773-1779. （Yuan Shuaipeng， Li Tieke， Wang Bailin， et al. Model and algorithm for two-stage flow shop group scheduling problem with special blocking constraint ［J］. Control and Decision， 2020， 35（7）： 1773-1779.）

［5］韓雪， 王玉亭， 韓玉艷， 等. 求解能耗成本平衡的分布式阻塞流水線調(diào)度群體迭代貪婪算法 ［J］. 控制理論與應用， 2024， 41（6）： 1147-1155. （Han Xue， Wang Yuting， Han Yuyan， et al. An iterated greedy algorithm based on population evolution for distributed blocking flowshop scheduling with balanced energy costs criterion［J］. Control Theory amp; Applications， 2024， 41（6）： 1147-1155.）

［6］Bai Danyu， Bai Xiaoyuan， Li Haoran， et al. Blocking flowshop scheduling problems with release dates ［J］. Swarm and Evolutio-nary Computation， 2022， 74： 101140.

［7］Jing Xuelei， Pan Quanke， Gao Liang， et al. An effective iterated greedy algorithm for a robust distributed permutation flowshop problem with carryover sequence-dependent setup time ［J］. IEEE Trans on Systems， Man， and Cybernetics： Systems， 2021， 52（9）： 5783-5794.

［8］Gonzalez-Neira E M， Ferone D， Hatami S， et al. A biased-randomized simheuristic for the distributed assembly permutation flowshop problem with stochastic processing times ［J］. Simulation Modelling Practice and Theory， 2017， 79： 23-36.

［9］Wang Zhiyuan， Pan Quanke， Gao Liang， et al. A cooperative iterated greedy algorithm for the distributed flowshop group robust scheduling problem with uncertain processing times ［J］. Swarm and Evolutionary Computation， 2023， 79： 101320.

［10］Jing Xuelei， Pan Quanke， Gao Liang. Local search-based metaheuristics for the robust distributed permutation flowshop problem ［J］. Applied Soft Computing， 2021， 105： 107247.

［11］Wang Zhiyuan， Pan Quanke， Gao Liang， et al. An effective two-stage iterated greedy algorithm to minimize total tardiness for the distributed flowshop group scheduling problem ［J］. Swarm and Evolutionary Computation， 2022， 74： 101143.

［12］葉立威， 吳鈞皓， 戚遠航， 等. 改進混合粒子群算法求解帶時間窗的無人機與車輛協(xié)同路徑調(diào)度問題 ［J］. 計算機應用研究，2024，41（8）：2336-2342. （Ye Liwei， Wu Junhao， Qi Yuanhang， et al. Improved hybrid particle swarm optimization algorithm for vehicle routing problem with drone and time window ［J］. Application Research of Computers， 2024，41（8）：2336-2342.）

［13］Hou Yushuang， Fu Yaping， Gao Kaizhou， et al. Modelling and optimization of integrated distributed flow shop scheduling and distribution problems with time windows ［J］. Expert Systems with Applications， 2022， 187： 115827.

［14］Zhu Ningning， Zhao Fuqing， Wang Ling， et al. A discrete learning fruit fly algorithm based on knowledge for the distributed no-wait flow shop scheduling with due windows ［J］. Expert Systems with Applications， 2022， 198： 116921.

［15］Jing Xuelei， Pan Quanke， Gao Liang， et al. An effective iterated greedy algorithm for the distributed permutation flowshop scheduling with due windows ［J］. Applied Soft Computing， 2020， 96： 106629.

［16］Ruiz R， Stützle T. A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem ［J］. European Journal of Operational Research， 2007， 177（3）： 2033-2049.

［17］Nawaz M， Enscore Jr E E， Ham I. A heuristic algorithm for the m-machine， n-job flow-shop sequencing problem ［J］. Omega， 1983， 11（1）： 91-95.

［18］Wang Yuhang， Han Yuyan， Wang Yuting， et al. An effective two-stage iterated greedy algorithm for distributed flowshop group scheduling problem with setup time ［J］. Expert Systems with Applications， 2023， 233： 120909.

［19］Wang Bingtao， Pan Quanke， Gao Liang， et al. Modeling and scheduling a constrained flowshop in distributed manufacturing environments ［J］. Journal of Manufacturing Systems， 2024， 72： 519-535.

［20］Naderi B， Ruiz R. The distributed permutation flowshop scheduling problem ［J］. Computers amp; Operations Research， 2010， 37（4）： 754-768.