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

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

中圖分類號(hào)： TP13 文獻(xiàn)標(biāo)志碼： A 文章編號(hào)： 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］，其特點(diǎn)是將工藝相似的工件分到同一個(gè)組內(nèi)，減少切換工藝調(diào)整機(jī)器所花費(fèi)的時(shí)間^［2］，而一些大型印刷電路板企業(yè)，比如華為、富士康等，通常在不同的地方擁有多條相同的生產(chǎn)線^［3］。上面的生產(chǎn)模式可以被抽象為存在序列依賴設(shè)置時(shí)間（sequence dependent setup time， SDST）的分布式流水車間成組調(diào)度問題（distributed flowshop group scheduling problem， DFGSP）^［4］。

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

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

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

DBFGSP-UPT存在如下難點(diǎn)：

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

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

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

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

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

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

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

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

1.1 問題描述

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

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

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

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

目標(biāo)：

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

約束：

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

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

2 空閑時(shí)間插入驅(qū)動(dòng)的自適應(yīng)協(xié)同迭代貪婪算法

2.1 編碼方法

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

2.2 算法框架

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

2.3 改進(jìn)的空閑時(shí)間插入方法

由于問題的阻塞和成組約束，現(xiàn)有的空閑時(shí)間插入方法不能直接用于本文研究的問題，所以本文提出了一種改進(jìn)的空閑時(shí)間插入方法（modified idle time insertion，MITI）。MITI的核心概念是塊，如果不同的組之間不能插入空閑時(shí)間，那么這些組就被視為一個(gè)塊，空閑時(shí)間只能在塊之前插入。本文創(chuàng)建了三個(gè)集合來(lái)存儲(chǔ)塊內(nèi)不同狀態(tài)的組：Γ_E存儲(chǔ)提前完工的組，Γ_O存儲(chǔ)按時(shí)完工的組，Γ_T存儲(chǔ)延遲完工的組。相應(yīng)地，用SW_E和SW_T分別表示Γ_E中組的總提前權(quán)重和Γ_T中組的總延遲權(quán)重。如果塊內(nèi)組的完工時(shí)間等于最晚交付時(shí)間，那么這些組會(huì)被歸入Γ_T而不是Γ_O，因?yàn)榧词共迦胱钚挝坏目臻e時(shí)間也會(huì)導(dǎo)致延遲。只有當(dāng)SW_Egt;SW_T時(shí)，才會(huì)對(duì)塊進(jìn)行空閑時(shí)間插入。

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

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

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

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

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

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

算法1 MNEH2_en

輸入：GS和工件序列τ。

輸出：［π，τ］，TWET_SET。

計(jì)算每個(gè)工件的平均加工時(shí)間

π_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中所有可行位置測(cè)試組GS_g

TWET^*_w記錄了最小的TWET值，P_w記錄了對(duì)應(yīng)的位置

end for

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

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

TWET_w^*←TWET^*_w

隨機(jī)從位置P_w^*－1或者P_w^*+1選擇一個(gè)組Ξ

for w=1 to f do

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

TWET^*_w記錄了最小的TWET值，P_w記錄了對(duì)應(yīng)的位置

end for

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

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

TWET_w^*←TWET^*_w

end for

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

2.5 自適應(yīng)破壞策略

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

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

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

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

if RO^Templt;RO^best then

在位置Pos－1和Pos+1測(cè)試組EG_g //MITI

RO^best←min RO^Temp

else

Pos←Pos+2

end if

end while

end for

w^*←RO^best對(duì)應(yīng)的工廠

Pos_w^*←RO^best在工廠π_w^*中對(duì)應(yīng)的位置

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

end for

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

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

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

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

算法3 LS-Group

輸入：［π，τ］、RO。

輸出：［π，τ］、RO。

GS←對(duì)組{Δ₁，Δ₂，…，Δ_δ}隨機(jī)排序

Counter←0，Pos←0

while Counterlt;δ do

o←組GS_Pos所在的工廠索引

originalRO←RO

π_o←π_o＼{GS_Pos}

for w=1 to f do

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

用RO^*_w表示最小的RO值，用P_w表示對(duì)應(yīng)的位置

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í)驗(yàn)設(shè)計(jì)與分析

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

本文的實(shí)驗(yàn)平臺(tái)是一臺(tái)搭載了Intel Core i7 12700處理器和16 GB內(nèi)存的計(jì)算機(jī)，操作系統(tǒng)為Windows 11專業(yè)版。所有算法均使用C++在CLion中編寫。算法的運(yùn)行時(shí)間為100×δ×m ms，其中δ和m分別代表組的數(shù)量和機(jī)器的數(shù)量。本文使用相對(duì)偏差指數(shù)（relative deviation index，RDI）來(lái)評(píng)估算法的性能，對(duì)于給定的實(shí)例i，RDI的計(jì)算方法如式（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只有一個(gè)可校驗(yàn)的參數(shù)GJ，根據(jù)經(jīng)驗(yàn)和文獻(xiàn)［19］，設(shè)置GJ=0.8。

3.2 測(cè)試實(shí)例生成

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

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í)間；參數(shù)L和R分別表示延遲因子和窗口范圍，均為0.2^［15］；此外，變量H在1～10均勻分布，每個(gè)組的提前權(quán)重和延遲權(quán)重也由1～5的均勻分布決定。

3.3 數(shù)學(xué)模型驗(yàn)證

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

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

3.4 策略有效性驗(yàn)證

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

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

3.5 算法性能比較

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

在所有測(cè)試實(shí)例中，ACIG_ITI在RO和RDI兩個(gè)指標(biāo)上都優(yōu)于sIGA、sILSA、CIGA和TIGA。具體來(lái)說(shuō)，在810個(gè)實(shí)例中，ACIG_ITI的平均RO為10 729.60 471，這個(gè)結(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，展示出相對(duì)于sIGA（0.862 77）、sILSA（0.970 92）、CIGA（0.761 89）和TIGA（0.708 07）的100%改進(jìn)?？傮w來(lái)看，ACIG_ITI在解決DBFGSP-UPT問題上具有明顯的優(yōu)勢(shì)。圖3展示了置信區(qū)間圖，分別展示了每種算法在不同工廠數(shù)量、不同組數(shù)量、不同機(jī)器數(shù)量和不同加工時(shí)間規(guī)模下的表現(xiàn)。從圖3可以看出，ACIG_ITI在各種規(guī)模的實(shí)例中表現(xiàn)了出色的魯棒性。

3.6 非參數(shù)檢驗(yàn)

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

從表6中可以看到，在ARDI指標(biāo)上，ACIG_ITI在排名、均值、標(biāo)準(zhǔn)差、最小值和最大值方面表現(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指標(biāo)上，ACIG_ITI同樣在排名、均值、標(biāo)準(zhǔn)差、最小值和最大值方面表現(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指標(biāo)下，Wilcoxon signed-rank檢驗(yàn)的實(shí)驗(yàn)結(jié)果。在ACIG_ITI與其他四個(gè)算法對(duì)比中，p-value均為0，實(shí)驗(yàn)表明在α=0.05的水平上，四種算法之間存在統(tǒng)計(jì)顯著性差異。

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

4 結(jié)束語(yǔ)

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

在未來(lái)的研究中，計(jì)劃將強(qiáng)化學(xué)習(xí)算法融入到元啟發(fā)式算法中，利用其學(xué)習(xí)機(jī)制來(lái)解決更復(fù)雜的調(diào)度問題。

參考文獻(xiàn)：

［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］. 控制理論與應(yīng)用， 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］葉立威， 吳鈞皓， 戚遠(yuǎn)航， 等. 改進(jìn)混合粒子群算法求解帶時(shí)間窗的無(wú)人機(jī)與車輛協(xié)同路徑調(diào)度問題 ［J］. 計(jì)算機(jī)應(yīng)用研究，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.