考慮工時區(qū)間的可重入混合流水車間調(diào)度方法

摘 要：為了精確求解在工時區(qū)間約束下的可重入混合流水車間調(diào)度問題（IRHFSP），構建了以最小化最大完工時間區(qū)間為目標的調(diào)度模型，并設計基于產(chǎn)品重入階段的編碼方式，采用針對問題特性提出的改進候鳥優(yōu)化算法IMBO進行求解。該算法通過啟發(fā)式種群初始化和基于基因模式的禁忌鄰域搜索等方式減少了重復解，并通過多種算法的大規(guī)模實驗對比，驗證了該算法在求解該問題上的有效性與優(yōu)越性。此外針對工時區(qū)間進行優(yōu)化，并引入基于多輪隨機仿真結果的區(qū)間精準度指標，以評估不同工時區(qū)間邊界調(diào)整策略在實際加工環(huán)境中的表現(xiàn)。最后采取IMBO進行一系列實驗求解，結果表明進行工時區(qū)間優(yōu)化后所得的最大完工時間區(qū)間，其區(qū)間長度僅有改進前長度的28.1%；區(qū)間精準度從0.243 63增加至0.764 69，提高了0.521 06；且優(yōu)化的后調(diào)度方案比優(yōu)化前更優(yōu)。這證明了結合工時區(qū)間優(yōu)化策略及IMBO的求解方法，在求解IRHFSP上更為有效且利于精準決策。

關鍵詞：可重入混合流水車間調(diào)度；生產(chǎn)調(diào)度；工時區(qū)間；候鳥優(yōu)化算法；區(qū)間調(diào)整策略

中圖分類號：TP301"" 文獻標志碼：A""" 文章編號：1001-3695（2025）04-016-1085-10

doi： 10.19734/j.issn.1001-3695.2024.09.0329

Re-entrant hybrid flowshop scheduling method considering interval processing time

Wang Xinfeng1， Zhang Feng1， Wang Hai1， Qin Hongbin1，2

（1.School of Mechanical amp; Electronic Engineering， Wuhan University of Technology， Wuhan 430070， China; 2. Suizhou-WUT Industry Research Institute， Suizhou Hubei 441300， China）

Abstract：To accurately solve the interval re-entrant hybrid flowshop scheduling problem （IRHFSP）， this paper developed a scheduling model targeting the minimization of interval makespan. It designed a coding mechanism based on product reentry stages and employed an improved migrating birds optimization algorithm （IMBO） tailored to the problem’s characteristics. The algorithm reduced redundant solutions through heuristic population initialization and gene-pattern-based tabu neighborhood search. Extensive comparative experiments with various algorithms demonstrated the effectiveness and superiority of our approach in solving this problem. Furthermore， it optimized the interval processing time and introduced an interval precision metric based on multiple rounds of stochastic simulation results to assess different interval boundary adjustment strategies in real processing environments. A series of experiments using IMBO showed that optimizing the interval processing time resulted in an interval makespan length that was only 28.1% of the pre-optimization length. The interval precision increased from 0.243 63 to 0.764 69， having an improvement of 0.521 06. The optimized scheduling scheme proves its superior to the pre-optimization scheme， demonstrating that the combined interval processing time optimization strategy and IMBO method are more effective for solving IRHFSP and facilitate precise decision-making.

Key words：re-entrant hybrid flowshop scheduling; production scheduling; interval processing time; migrating birds optimization algorithm; interval adjustment strategy

0 引言

在現(xiàn)代制造業(yè)中，可重入混合流水車間調(diào)度問題（re-entrant hybrid flow shop scheduling problem， RHFSP）因其在半導體制造等行業(yè)的廣泛應用而備受關注［1］。該問題的復雜性在于產(chǎn)品在生產(chǎn)過程中可能多次回到某些機臺進行加工，這一特性使得調(diào)度策略的設計更為復雜。隨著我國半導體產(chǎn)業(yè)的迅速發(fā)展，相關研究也迅速成為熱點。Lin等人［2］梳理RHFSP的研究現(xiàn)狀后，指出數(shù)學方法和元啟發(fā)式算法將是未來研究方向的兩個重要方法。朱光宇等人［1］提出了一種基于實質(zhì)不確定因子的最優(yōu)覓食算法，在多目標績效上優(yōu)于傳統(tǒng)算法。董君等人［3］考慮了預防性維護措施，提出了改進的離散鯨魚群算法，實現(xiàn)了制造和維護策略的同步優(yōu)化。Wu等人［4］針對多階段分布式RHFSP，設計了基于局部搜索分解策略的改進多目標進化算法，以及作業(yè)相似度平衡解碼方法。秦紅斌等人［5］則針對帶批處理的RHFSP，提出了改進的多目標蜉蝣算法。

現(xiàn)有對RHFSP的研究大多都基于確定工時來展開，而在半導體行業(yè)，加工過程存在一些特殊要求：精度要求高，空間精度需要達到標準，如掩膜版定位［6］；工藝要求高，工藝參數(shù)條件要達到標準，如溫控、抽真空等［7］。每次加工時對這些條件需要重新測定與調(diào)整，盡管核心工藝時間不變，但非增值時間波動較大。時間的波動性和工藝復雜性使得加工時間難以精確預測［8］。傳統(tǒng)研究采用隨機數(shù)、模糊數(shù)和區(qū)間數(shù)方法來處理這種不確定性［9］，相比前兩種方法都需要人工參與處理，區(qū)間數(shù)方法因其直接有效而被廣泛采用［10～13］。李鐵克等人［14］使用三參數(shù)區(qū)間數(shù)描述不確定信息，并設計了基于分類進化策略的改進快速非支配排序區(qū)間多目標遺傳算法。楊宏安等人［9］研究了區(qū)間交貨期問題，提出了梯形甘特圖表示調(diào)度結果。朱艷艷等人［15］建立了以提前/推遲懲罰和調(diào)度魯棒性為目標的雙準則函數(shù)，并采用了粒子群算法和化學反應算法。Lei［16］針對區(qū)間車間調(diào)度問題，提出了修正遺傳解碼方案。Allahverdi等人［17］提出了一種新的穩(wěn)定性方法求解單機調(diào)度問題，通過引入最優(yōu)性盒子的概念來量化調(diào)度方案的穩(wěn)健性，并開發(fā)了高效算法以尋找具有最大相對周長最優(yōu)性盒子的工件序列。Pereira［18］通過最小化最大遺憾，引入了一種新穎的單機調(diào)度模型和算法，有效應對了作業(yè)處理時間的不確定性。盡管存在眾多解決區(qū)間車間調(diào)度問題的方法，但這些方法在確定區(qū)間工時范圍時普遍依賴于工人的經(jīng)驗或樣本數(shù)據(jù)的極端值來設定邊界。這種做法往往導致得到的區(qū)間完工時間過于寬泛，從而降低了其在實際應用中的指導價值。

因此，針對工時區(qū)間范圍設置方法，本文提出了工時區(qū)間優(yōu)化方法，并在此基礎上探討了考慮工時區(qū)間的可重入混合流水車間調(diào)度問題（interval re-entrant hybrid flow shop sche-duling problem，IRHFSP）。本文以半導體行業(yè)為背景，首先介紹了可重入車間調(diào)度問題和區(qū)間計算方法，然后提出了工時區(qū)間優(yōu)化方法，并構建了評價最大完工時間區(qū)間的指標體系。接著，設計了基于重入階段的編碼方式，并通過優(yōu)化算法對不同區(qū)間范圍設置策略進行了實驗驗證，以探索最佳的工時區(qū)間優(yōu)化策略。

1 IRHFSP數(shù)學模型的建立

1.1 可重入混合流水車間調(diào)度問題描述

可將RHFSP描述為：對于J個工件，均有R個重入階段，而車間內(nèi)一共有P個串聯(lián)工站，每個工站上分別有mp（p=1，2，…，P）臺機器，共M=∑Pp=1mp臺。工件在每個階段上需要從第一個工站開始，依次經(jīng)過每個工站，但可以不在該工站上加工。工件經(jīng)過串聯(lián)的P個工站后，視為完成一個重入階段，而每個工件完成加工需要在串聯(lián)的工站上循環(huán)完成R個重入階段，如圖1所示。

IRHFSP則是在RHFSP的基礎上，將傳統(tǒng)的精確數(shù)運算調(diào)整為區(qū)間數(shù)運算。由于無論是工序加工時間還是最終所得的最大完工時間都是一個區(qū)間，所以在比較最大完工時間區(qū)間、最先可用設備時就涉及區(qū)間數(shù)計算。

針對該問題一般作以下假設：a）一臺機器一次只能加工一個工件；b）一個工件一次只能被一臺機器加工；c）不同的工件是相互獨立的，即機器在選擇要處理的工件時呈現(xiàn)隨機性，所有工件具有相同的優(yōu)先級，并且沒有順序限制；d）工件一旦開始加工，就不能中途停止；e）工件在不同機器上的轉移時間為零；f）所有工件在零時刻都可以被加工；g）不考慮機器宕機因素。

3 區(qū)間數(shù)優(yōu)化問題求解方法

3.1 算法流程

在求解車間調(diào)度問題時，多采用啟發(fā)式算法求解，因此本文采取該方式求解IRHFSP。在算法編碼部分采取基于重入階段的編碼，而因該編碼的特征，編碼對中不存在“優(yōu)良基因”，所以以基因進化為基礎的算法在該問題上受限。而鄰域搜索算法不存在該限制，在初始解較好的前提下，該類算法能更有效地遍歷解空間，有利于找到最優(yōu)解。

候鳥優(yōu)化（migratory bird optimization， MBO）算法是由Duman等人［20］提出的一種新型鄰域搜索算法，具有結構簡單、參數(shù)少、局部搜索能力強、易于理解等優(yōu)點，廣泛應用于復雜的調(diào)度問題［21］。因此，本文基于MBO并結合編碼特征，設計一種尋優(yōu)能力較強的改進候鳥優(yōu)化（improved migrating birds optimization，IMBO）算法。其具體流程如圖9所示。

3.2 基于區(qū)間數(shù)的染色體編碼和解碼

1）基于重入階段的編碼方案

結合可重入車間的特征，本文采取基于工件重入階段的編碼方案，具體表現(xiàn)為：在考慮I個工件和R個重入階段的RHFSP中，染色體表示采用工件編號作為基因，其在染色體上的出現(xiàn)次序指示相應工件的重入階段。以兩個工件的RHFSP為例，其各重入階段的詳列于表3，表中的0代表相應輪次中工件不在該工站進行加工。

具體而言，對于兩個工件各含四個重入階段的情形，染色體編碼將具有2×4=8的長度。以編碼方案“11221212”為例，該方案從左至右解讀，基因出現(xiàn)的次序?qū)渲厝腚A段。例如，染色體上首個基因“1”代表第一個工件的第一個重入階段在第一輪分配中被分配至所有相關工站；接著的基因“1”則表示該工件的第二個重入階段在第二輪分配中被分配；而第五個位置上的基因“1”表明在第五輪分配中，第一個工件的第三個重入階段被分配至所有工站。

該編碼方式相比于工序編碼，編碼長度更簡短，有利于大規(guī)模調(diào)度問題的求解。以表3為例，當有兩個工件時，染色體編碼將有2×10=20的長度，例如“1122122122211212”，基因出現(xiàn)次序?qū)ぜ牡趲讉€工序。因此，當有x個工件、y個重入階段、z個工站時，工序編碼的長度為x×y×z，而基于重入階段的編碼長度僅有x×y，解空間的范圍更小，更有利于找到最優(yōu)解。

2）基于區(qū)間數(shù)的解碼方案

基于區(qū)間數(shù)操作的解碼詳細過程如下：

a）從染色體中選擇一個基因i，計算當前重入階段，并初始化當前階段加工進度。

b）根據(jù)加工進度獲取工站p，若不需要加工則跳過，再次進入流程b）并獲取下一工站，否則進入流程c）。

c）根據(jù)p和r計算j，并獲取可用的機器集合MCj、當前工序Oij和加工時間TMCj。

d）比較機器集合MCj中所有機器的占用時間［WMCj］，選擇最早完工機器mk。

e）根據(jù)機器mk的占用時間［Wk］和工序Oi（j-1）的完工時間［Ci（j-1）］，得到工序Oij的開始時間［Sij］=［Ci（j-1）］∨［Wk］。

f）更新工序結束時間［Sij］和機器mk的占用時間［Wk］。

g）重復上述流程b）～f），若當前重入階段的工站序列遍歷完成，則回到流程a）選取下一個基因，直到染色體中所有基因處理完畢。

通常區(qū)間數(shù)車間調(diào)度研究中，在獲取工序Oij開始時間［Sij］時直接比較［Wk］和［Ci（j-1）］的大小，選取最大的作為下一工序的開始時間。但該操作容易產(chǎn)生邊界交叉的問題，如在計算［S13］時，［C12］=［9，20］，［W1］=［13，18］，盡管排序后［W1］gt;［C12］，導致［S13］=［13，18］，但仍要考慮工件可能在［C12］的20時刻才結束加工，因此需要對區(qū)間調(diào)度方案進行修復，修復后為［S13］=［13，20］。為了簡化流程，本文調(diào)整文獻［16］的修復流程，將修復操作合并到流程e）的［Sij］計算過程中。

3.3 種群初始化

為了獲取一定質(zhì)量和分散度的初始化種群，本文針對問題特性，采用混合策略來生成初始化種群。三種初始化規(guī)則為：a）優(yōu)先安排同一工件所有加工；b）優(yōu)先安排不同工件的同一重入階段；c）隨機初始化。三種初始化規(guī)則的選擇概率為0.3、0.4、0.3。

3.4 基于個體基因模式的禁忌鄰域搜索

3.4.1 個體基因模式

盡管相比于工序編碼，基于重入階段的編碼能大大縮短編碼長度，減少解空間的大小，但當多個工件為同一產(chǎn)品時，其編號的區(qū)別對于整個調(diào)度方案來說并無差異。例如：當工件1、工件2為同一種類工件時，編碼為111222和222111的個體在轉換為調(diào)度方案時并無區(qū)別，可將兩個個體視為等效解，稱其具有相同基因模式（model of individual gene）。因此，為減少禁忌表和生成的新鄰域解中的等效解數(shù)量，需要將每個個體轉換為個體基因模式，以提升算法的搜索效率。

對于任意個體，其基因模式的長度與個體編碼長度一致，基因模式上每個位置儲存一個3元素向量，分別表示產(chǎn)品種類、當前工件在該類產(chǎn)品中首次出現(xiàn)的次序、該工件重入階段。假設有兩種產(chǎn)品，每種產(chǎn)品分別有兩個工件和兩個重入階段。假設個體一編碼為12341324，個體二編碼為21432413，其轉化為基因模式的流程如圖10所示。

對于個體一的第2個基因，由于工件2屬于產(chǎn)品一，且為產(chǎn)品一第2個出現(xiàn)的產(chǎn)品，是第一個重入階段，所以基因模式第1位編碼的向量為{01 02 01}。對于個體二的第2個基因同理，轉換為基因模式也是{01 02 01}。盡管兩個個體編碼的每一位元素都不同，但轉換后的基因模式每個編碼都相同，因此可認為個體一和個體二具備相同基因模式，是等效解，生成的是相同調(diào)度方案，在加入禁忌表和生成鄰域時需要排除。

3.4.2 禁忌表和生成鄰域

在算法每一代運行結束后，將不在禁忌表中的優(yōu)秀個體加入禁忌表，可以有效提高種群多樣性，以獲取更好的解。在向禁忌表中添加記錄時，需要將個體基因模式加入禁忌表，而非個體本身，可以避免許多等效解同時進入禁忌表。在候鳥進化時會生成許多鄰域解，因此在鄰域結構的設計方面，本文設計了交換、逆序和插入三種鄰域操作，且生成的鄰域解的基因模式不能在禁忌表中。當個體達到年齡上限，替換為新個體時，也需要參照禁忌表。

4 仿真實驗

4.1 算法性能對比分析

4.1.1 算法性能對比

選取二進制人工蜂群算法nBABC［22］、新型人類學習優(yōu)化算法NHLO［23］、遺傳禁忌混合算法HA［24］、改進灰狼優(yōu)化算法IGWO［25］、候鳥優(yōu)化算法MBO［21］與本文IMBO進行對比。所有算法的最大迭代次數(shù)均設置為200，種群數(shù)量為50，因MBO與IMBO的種群數(shù)量需要為奇數(shù)，所以設置為51。其他主要參數(shù)如表4所示。

本文基于表5中的參數(shù)，隨機生成10 個小規(guī)模算例和10個大規(guī)模算例進行測試 。算例命名方式為：c表示工件種類、j表示總工件數(shù)、s表示重入階段、o表示工站數(shù)，即c5j13s3o5表示5種工件、13個工件、3個重入階段、5個工站的IRHFSP問題。隨后對每個算例進行10次求解，結果如表6和7所示。

將表6和7中每個算例的求解最小值加粗后可以發(fā)現(xiàn)，在該問題中，無論是哪種規(guī)模算例，MBO和IMBO均具備明顯優(yōu)勢，所求解普遍優(yōu)于其他算法。在小規(guī)模算例中，由于算例簡單，MBO和IMBO均能求得較優(yōu)解；但在更為復雜的大規(guī)模算例中，IMBO則呈現(xiàn)出更好的表現(xiàn)。

4.1.2 改進策略機制有效性分析

IMBO所改進的四種機制為：基因模式、禁忌表、種群初始化、新鄰域搜索。依次去掉一種機制，保留另外三種，構成IMBO1、IMBO2、IMBO3、IMBO4四種算法。其他參數(shù)保持不變，對上一節(jié)大規(guī)模算例進行求解，結果如表8所示。

表中差異越大說明去除的機制對算法求解影響最大?？梢园l(fā)現(xiàn)，四種機制對算法求解能力均有影響，而在大多數(shù)情況下，影響最大的是鄰域結構，其次是禁忌表。說明在IRHFSP中，鄰域的構建方式對MBO這類鄰域搜索算法求解結果影響較大；禁忌表則可以減少重復解的出現(xiàn)，提升算法求解效率。

4.2 樣本數(shù)據(jù)采集與處理

本節(jié)以OLED顯示器陣列制程為研究對象，其生產(chǎn)調(diào)度為典型的IRHFSP問題。收集了各工序在不同機器上的處理時間數(shù)據(jù)，并從這些數(shù)據(jù)中隨機抽樣，以此作為實驗分析的數(shù)據(jù)基礎。

研究案例包括15個相同工件、6個重入階段，每個階段設有6個工站，各工站的可用機器數(shù)量分別為［3，5，8，3，5，4］，構成了一個具體的IRHFSP問題實例。為了確保企業(yè)信息的安全性，對原始的標準工時數(shù)據(jù)進行了脫敏處理和比例縮放，詳細結果如表9所示，空白表示當前重入階段跳過該工站。

對各工序上某一機器的加工時間進行0-1標準化后的分布情況如圖11所示?？梢钥吹?，盡管加工時間存在波動，但大多都呈現(xiàn)集中分布的趨勢。

4.3 工時區(qū)間優(yōu)化有效性驗證

使用2.2.1節(jié)參數(shù)，對表2的10種方案各進行30次求解。共計得到10×10個調(diào)度方案，再導入到MATLAB中進行1 000次隨機仿真實驗，根據(jù)所得結果區(qū)間IV計算每種方案的區(qū)間精準度IP。得到實驗結果如表10和圖12所示。

IP表示區(qū)間精準度（左軸），［Cmax］中點、［Cmax］邊界分別表示最大完工時間區(qū)間的中點和上下限（右軸）。根據(jù)實驗結果可以發(fā)現(xiàn)，隨著分位數(shù)的不斷調(diào)整，工時區(qū)間縮小的同時，最大完工時間區(qū)間的范圍和取值也呈現(xiàn)減小趨勢；而區(qū)間精準度則隨著工時區(qū)間的縮小，呈現(xiàn)先增加后減小的趨勢。說明工時區(qū)間進行適當調(diào)整，可在減小最大完工時間區(qū)間的同時，減少區(qū)間的冗余范圍并提高區(qū)間精準度。

4.4 工時區(qū)間優(yōu)化策略比較

4.4.1 考慮數(shù)據(jù)分布的規(guī)則

實驗中所選取的s為25，q取值和GA參數(shù)均與4.1節(jié)相同，進行仿真實驗得到如表11和圖13所示結果。

實驗結果涵蓋9組數(shù)據(jù)，展示了在較低q值條件下，方案I在區(qū)間精度上略勝一籌。然而，隨著q值增加，方案II的表現(xiàn)逐漸顯現(xiàn)出顯著的優(yōu)勢，特別是［Cmax］中點，方案II普遍高于方案I。這一現(xiàn)象揭示了方案I僅聚焦于高頻數(shù)據(jù)而忽視了異常值可能導致的過高工時，從而使得其最大完工時間區(qū)間偏小，進而影響了區(qū)間精度。因此，在考慮數(shù)據(jù)偏度的情況下，方案II表現(xiàn)更佳。對比分析中，方案II的成效與4.3節(jié)中未考慮數(shù)據(jù)偏度情況的結果（用q表示）相比較，如圖14所示。

在固定工時區(qū)間的前提下，較寬的區(qū)間使得忽略偏度的精度略勝一籌；然而，對于較窄的區(qū)間，如起始于20分位數(shù)，納入偏度考量的方法優(yōu)于忽略偏度。這表明，考慮偏度能夠在區(qū)間縮減的同時，更有效地保留工時數(shù)據(jù)，從而提高區(qū)間的精確度。

4.4.2 考慮工時權重與偏度的規(guī)則

首先需要計算各工序的工時權重，采取0-1標準化的方式計算工序Oij的權重wij。以表9為例，所計算的各工序權重如表12所示。

可以發(fā)現(xiàn)在本案例中，P3工站的工序加工時間普遍較長，因此其波動所帶來的影響也會較大。由此可得工序Oij的工時區(qū)間［Tij］。對于q0和q1的取值，設置多組實驗如表13所示。

進行多輪求解后，所得實驗結果如表14和圖15所示。

圖15中，方格越靠近左上角，說明對于加工權重大和小的工時，都采取保守的策略；越靠近右下角說明采取策略較為激進。結果表明，當q0+q1在［40，50］內(nèi)時，區(qū)間精準度顯著提高，尤其是在q0=45、q1=10時達到最高。隨著q0和q1增加，最大完工時間區(qū)間趨于縮小。在先前4.4.1節(jié)實驗中，最高區(qū)間精度平均值達到0.546的峰值，而在本次實驗中，最高達到0.550。這表明，工時區(qū)間設定中引入工時權重，可以提升最大完工時間區(qū)間的精度。

4.5 懲罰系數(shù)靈敏性分析

4.4節(jié)中在計算區(qū)間精準度時，為便于研究開展，將懲罰系數(shù)設置為2。本節(jié)基于4.4節(jié)得出的各策略最優(yōu)調(diào)度方案，探究懲罰系數(shù)a的取值對區(qū)間邊界設置策略的影響。

將a取值設置為［0， 0.1， 0.5， 1， 2， 5， 10， 20， 50］九種，對4.4節(jié)中36個情況的最優(yōu)解分別進行1 000次仿真后，計算區(qū)間精準度IP，如圖16所示。

從圖中可以看出，隨著懲罰系數(shù)a的增大，區(qū)間精準度IP分母中預測錯誤的部分IF占比越來越大，使整體的IP值都在變小。且隨著a的增大，IP最大值的范圍從偏右下角的q0+q1=［55，70］逐漸向左上角移動，當a=50時，最優(yōu)取值范圍在q0+q1=［40，45］左右。因此，隨著a的增大，無論是何種權重大小的工時，設置其工時區(qū)間范圍時，都傾向于采取更為保守的策略，才能確保結果更為精準。而無論a取值為多少，在q0+q1=［40，50］內(nèi)，都能有一個比較不錯的IP值。因此在實際應用中設置工時區(qū)間時，q0和q1取值滿足q0+q1=［40，50］時會是一個較好的初始方案。

4.6 最佳工時區(qū)間參數(shù)與結果

本節(jié)將4.3節(jié)中極值區(qū)間實驗與4.4節(jié)實驗中區(qū)間精度最優(yōu)的實例進行比較。鑒于IRHFSP調(diào)度解呈區(qū)間形式，傳統(tǒng)甘特圖無法有效展示其特性，故采用梯形甘特圖［9］進行表示。在梯形甘特圖中，每個梯形表示一個工序的工時區(qū)間。其中梯形左下角、左上角、右下角、右上角分別表示該工序的最早開始時間、最晚開始時間、最早結束時間和最晚結束時間；下底長和上底長分別表示工時區(qū)間的區(qū)間下界和上界。

若圖中梯形傾斜程度小，說明區(qū)間的上下底之差小，工時區(qū)間的表示范圍更小，更利于精確決策；若圖形A比B的最右側點更小，說明圖形A所表示調(diào)度方案的最大完工時間比圖形B的最大完工時間更小，方案更優(yōu)。將最初采取極值區(qū)間設置策略時所得最優(yōu)調(diào)度方案，與進行工時區(qū)間優(yōu)化后的最優(yōu)調(diào)度方案進行對比，繪制梯形甘特圖如圖17所示。

從圖17中可以看到，進行工時區(qū)間優(yōu)化后，調(diào)度方案的最大完工時間明顯早于優(yōu)化前，且工時區(qū)間和最大完工時間區(qū)間的范圍都更小，更有利于精確決策。

將優(yōu)化后和優(yōu)化前方案的相關指標進行對比，結果如表15所示。

經(jīng)過對工時區(qū)間的優(yōu)化，觀察到顯著的改進：區(qū)間寬度顯著縮減，從6 707降至1 884，僅保留原寬度的28.1%；同時，區(qū)間精準度從0.243 63增加至0.764 69，提高了0.521 06。此外，通過分析最大完工時間區(qū)間的中點，發(fā)現(xiàn)最大完工時間區(qū)間亦有所縮小。綜上所述，適當?shù)墓r區(qū)間優(yōu)化不僅能夠縮短完工時間，還能提高最大完工時間區(qū)間的準確性，并使最終呈現(xiàn)的區(qū)間寬度更小，更為精確。

5 結束語

本文聚焦于加工時間不確定性條件下的可重入混合流水線調(diào)度問題，采用區(qū)間數(shù)處理加工時間，構建了工時區(qū)間可重入混合流水線調(diào)度（IRFHSP）數(shù)學模型。針對工件可重復進入的特性，設計了一套編碼規(guī)則，并在候鳥優(yōu)化算法中采取基于個體基因模式的緊急鄰域搜索進行求解?？紤]到之前研究中使用極值區(qū)間導致的加工時間區(qū)間和最大完工時間區(qū)間的冗余，本文首先建立了一個區(qū)間精準度評價指標，并提出了一個基于工時權重與偏度的加工時間區(qū)間設置規(guī)則，旨在消除區(qū)間冗余的同時，確保調(diào)度結果的準確性。通過多重算法對比以及不同區(qū)間參數(shù)組合的仿真實驗，驗證了考慮工時區(qū)間的可重入調(diào)度模型的有效性和求解算法的優(yōu)越性，以及工時區(qū)間優(yōu)化策略的可行性和優(yōu)越性。

未來工作將從兩方面展開：a）將模型拓展為多目標求解模型；b）OLED顯示器制造中存在批處理機，將批處理機添加到模型中。

參考文獻：

［1］朱光宇， 賈海斌. 面向半導體車間多目標可重入調(diào)度研究 ［J］. 華中科技大學學報：自然科學版， 2023， 51（2）： 122-130. （Zhu Guangyu， Jia Haibin. Research on multi-objective reentrant scheduling for semiconductor jobshops ［J］. Journal of Huazhong University of Science and Technology：Natural Science Edition， 2023， 51（2）： 122-130. ）

［2］Lin Danping， Lee C K M. A review of the research methodology for the re-entrant scheduling problem ［J］. International Journal of Production Research， 2011， 49（8）： 2221-2242.

［3］董君， 葉春明. 區(qū)間數(shù)可重入混合流水車間調(diào)度與預維護協(xié)同優(yōu)化 ［J］. 控制與決策， 2021， 36（11）： 2599-2608. （Dong Jun， Ye Chunming. Collaborative optimization of reentrant hybrid flow shop scheduling and preventive maintenance with interval processing time ［J］. Journal of Control and Decision， 2021， 36（11）： 2599-2608.）

［4］Wu Xiuli， Xie Zirun. Improved MOEA/D with local search for solving multi-stage distributed reentrant hybrid flow shop scheduling problem ［J］. Expert Systems with Applications， 2023， 232： 120893.

［5］秦紅斌， 李晨曉， 唐紅濤， 等. 基于MOMA的可重入混合流水車間調(diào)度問題研究 ［J］. 系統(tǒng)仿真學報， 2024， 36（1）： 131-148. （Qin Hongbin， Li Chenxiao， Tang Hongtao， et al. Research on reentrant hybrid flow shop scheduling problem based on MOMA ［J］. Journal of System Simulation， 2024， 36（1）： 131-148. ）

［6］Jung S W， Kim K， Park H，et al. Patternable semi-transparent cathode using thermal evaporation for OLED display applications ［J］. Advanced Electronic Materials， 2021， 7（4）： 2001101.

［7］Beccaro W， Ramos C A， Duarte S X. Optimizing semiconductor processing open tube furnace performance： comparative analysis of PI and Mamdani fuzzy-PI controllers ［J］. Journal of Intelligent Manufacturing， 2023， 34（7）： 3015-3024.

［8］Etman L F P， Veeger C P L， Lefeber E，et al. Aggregate modeling of semiconductor equipment using effective process times［C］// Proc of Winter Simulation Conference. Piscataway，NJ：IEEE Press，2011： 1790-1802.

［9］楊宏安， 王周鋒， 呂陽陽， 等. 工序加工時間不確定條件下作業(yè)車間調(diào)度問題的區(qū)間數(shù)求解方法 ［J］. 計算機集成制造系統(tǒng)， 2014， 20（9）： 2231-2240. （Yang Hongan， Wang Zhoufeng， Lyu Yangyang， et al. An interval number solution method for job shop scheduling problems under uncertain processing times ［J］. Compu-ter Integrated Manufacturing Systems， 2014， 20（9）： 2231-2240. ）

［10］蔡敏. 柔性作業(yè)車間模糊調(diào)度模型及算法［D］. 無錫：江南大學， 2022.（Cai Min. Fuzzy scheduling model and algorithm for flexible job workshop［D］. Wuxi：Jiangnan University， 2022.）

［11］唐秋華， 何明， 何曉霞， 等. 隨機工時下柔性加工車間的魯棒優(yōu)化調(diào)度方法 ［J］. 計算機集成制造系統(tǒng)， 2015， 21（4）： 1002-1012. （Tang Qiuhua， He Ming， He Xiaoxia， et al. Robust optimization scheduling method for flexible job shops with random processing times ［J］. Computer Integrated Manufacturing Systems， 2015， 21（4）： 1002-1012. ）

［12］王春. 多目標柔性作業(yè)車間調(diào)度模型及其進化算法研究［D］. 無錫：江南大學， 2018.（Wang Chun. Research on multi-objective fle-xible job shop scheduling model and its evolutionary algorithm［D］. Wuxi：Jiangnan University， 2018.）

［13］朱傳軍， 邱文， 朱孟周， 等. 隨機工時下的多目標柔性作業(yè)車間魯棒調(diào)度問題 ［J］. 中國機械工程， 2016， 27（12）： 1667-1672， 1678. （Zhu Chuanjun， Qiu Wen， Zhu Mengzhou， et al. Robust scheduling for multi-objective flexible job shop under stochastic processing times ［J］. China Mechanical Engineering， 2016， 27（12）： 1667-1672， 1678. ）

［14］李鐵克， 蘇藝璇， 張文新， 等. 加工時間不確定的煉鋼-連鑄區(qū)間多目標優(yōu)化調(diào)度 ［J］. 中國管理科學， 2021， 32（8）： 95-106. （Li Tieke， Su Yixuan， Zhang Wenxin， et al. Multi-objective optimization scheduling for steelmaking-continuous casting interval with uncertain processing time ［J］. Chinese Journal of Management Science， 2021， 32（8）： 95-106. ）

［15］朱艷艷， 徐震浩， 顧幸生. 工序加工時間不確定的可重入調(diào)度問題的求解 ［J］. 控制與決策， 2021， 36（5）： 1127-1136. （Zhu Yanyan， Xu Zhenhao， Gu Xingsheng. Solving reentrant scheduling problems with uncertain processing times ［J］. Journal of Control and Decision， 2021， 36（5）： 1127-1136. ）

［16］Lei Deming. Interval job shop scheduling problems ［J］. The International Journal of Advanced Manufacturing Technology， 2012， 60： 291-301.

［17］Allahverdi A，Aydilek H，Aydilek A. Single machine scheduling problem with interval processing times to minimize mean weighted completion time ［J］. Computers amp; Operations Research， 2014， 51： 200-207.

［18］Pereira J. The robust （minmax regret） single machine scheduling with interval processing times and total weighted completion time objective ［J］. Computers amp; Operations Research， 2016， 66： 141-152.

［19］Hubert M， Vandervieren E. An adjusted boxplot for skewed distributions ［J］. Computational Statistics amp; Data Analysis， 2008， 52（12）： 5186-5201.

［20］Duman E， Uysal M， Alkaya A F. Migrating birds optimization： a new metaheuristic approach and its performance on quadratic assignment problem ［J］. Information Sciences， 2012， 217： 65-77.

［21］杜凌浩， 向鳳紅， 楊立煒. 多策略候鳥優(yōu)化算法的多目標FJSP研究 ［J］. 控制工程， 2023， 30（7）： 1346-1356. （Du Linghao， Xiang Fenghong， Yang Liwei. Research on multi-objective FJSP using multi-strategy migrating birds optimization algorithm ［J］. Control Engineering of China， 2023， 30（7）： 1346-1356. ）

［22］孫菲， 賀毅朝， 張寒崧， 等. 基于新穎二進制人工蜂群算法求解帶權集合覆蓋問題 ［J］. 計算機應用研究， 2024， 41（9）： 2722-2731. （Sun Fei， He Yichao， Zhang Hansong， et al. Solving the weighted set cover problem using a novel binary artificial bee colony algorithm ［J］. Applications Research of Computers， 2024， 41（9）： 2722-2731. ）

［23］Jin Xie， Li Xinyu， Gao Liang，et al. An effective hybrid genetic algorithm and tabu search for flexible job shop scheduling problem ［J］. International Journal of Production Economics， 2016， 174： 93-110.

［24］張翼鵬， 劉勇， 馬良. 多維背包問題的新型人類學習優(yōu)化算法 ［J］. 計算機應用研究， 2024， 41（12）： 3689-3700. （Zhang Yipeng， Liu Yong， Ma Liang. Novel human learning optimization algorithm for multidimensional knapsack problem ［J］. Application Research of Computers， 2024， 41（12）： 3689-3700. ）

［25］Yu Yue， Hu Yang， Ge Yanran. Optimization of reentrant hybrid flow shop scheduling problem based on improved grey wolf algorithm： ta-king automatic chemiluminescence immunoassay analyzer as an example［C］// Proc of the 7th International Conference on Advanced Algorithms and Control Engineering. Piscataway，NJ：IEEE Press， 2024： 1286-1290.