基于改進(jìn)的多元宇宙算法的晶圓生產(chǎn)調(diào)度算法

摘要： 針對(duì)以最小化最大完工時(shí)間為目標(biāo)的晶圓生產(chǎn)制造系統(tǒng)的調(diào)度問題，提出了改進(jìn)的多元宇宙算法。根據(jù)晶圓生產(chǎn)制造系統(tǒng)的特征，構(gòu)建了一個(gè)整數(shù)規(guī)劃模型。針對(duì)原始多元宇宙算法的局限性，分別從使用啟發(fā)式規(guī)則生成初始種群、重新定義向最優(yōu)宇宙移動(dòng)策略和宇宙更新策略三個(gè)方面對(duì)算法進(jìn)行改進(jìn)。將原始多元宇宙算法、遺傳算法、NEH啟發(fā)式算法、迭代貪婪算法以及通過不同策略改進(jìn)的多元宇宙算法進(jìn)行對(duì)比實(shí)驗(yàn)，結(jié)果表明，所提方法可以高效地解決晶圓制造過程中的復(fù)雜現(xiàn)象。

關(guān)鍵詞： 晶圓制造； 多元宇宙算法； 可重入的混合流水車間； 調(diào)度算法

中圖分類號(hào)： TP18

文獻(xiàn)標(biāo)志碼： A

文章編號(hào)： 1671-6841（2024）06-0077-07

DOI： 10.13705/j.issn.1671-6841.2023063

Wafer Production Scheduling Algorithm Based on Improve Multiverse Algorithm

WANG Yinling1，2， SHI Chunxue1， TIAN Hui1，2， ZHU Xiaoran1，3， CAO Yangjie1， WEI Ronghan1，2，4

（1.School of Cyber Science and Engineering， Zhengzhou University， Zhengzhou 450002， China;

2.Institute of Intelligent Sensing， Zhengzhou University， Zhengzhou 450002，China;

3.Hanwei Electronics Group Corporation， Zhengzhou 450001，China;

4.School of Mechanics and Safety Engineering， Zhengzhou University， Zhengzhou 450001，China）

Abstract： An improved multiverse algorithm was proposed to solve the scheduling problem of wafer manufacturing systems with the aim of minimizing the maximum completion time. An integer programming model was constructed according to the characteristics of the wafer manufacturing system. In view of the limitations of the original multiverse algorithm， the algorithm was improved from three aspects： the use of heuristic rules to generate the initial population， the redefinition of the strategy of moving to the optimal universe and the strategy of updating the universe. Comparative experiments were conducted on the original multiverse algorithm， genetic algorithm， NEH heuristic algorithm， greedy iteration algorithm， and multiverse algorithms improved by different strategies. The results showed that the proposed algorithm could effectively deal with the complex characteristics of wafer manufacturing systems.

Key words： wafer manufacturing; multiverse algorithm; re-entrant hybrid flow shop; scheduling scheme

0 引言

半導(dǎo)體制造系統(tǒng)中最復(fù)雜的環(huán)節(jié)就是晶圓制造。由于晶圓制造系統(tǒng)漫長的重入性制造過程和其內(nèi)部多種復(fù)雜資源，使得該系統(tǒng)成為現(xiàn)代大規(guī)模復(fù)雜生產(chǎn)系統(tǒng)的典型代表［1-2］。為了解決晶圓制造系統(tǒng)中的調(diào)度問題，文獻(xiàn)［3］提出一種可重入的混合流水車間（re-entrant hybrid flow shop， RHFS），它具有重入的本質(zhì)特征，可以有效地解決復(fù)雜的車間調(diào)度問題。RHFS的可重入性使其比其他的流水車間和作業(yè)車間問題更加復(fù)雜，且RHFS已被證明為NP-hard問題［4］。RHFS技術(shù)可以提供更高的性能和可靠性［5］，已經(jīng)被廣泛應(yīng)用于各種工業(yè)設(shè)備，尤其在半導(dǎo)體晶圓、印刷電路板和薄膜晶體管液晶顯示器中應(yīng)用更加廣泛。

近年來，國內(nèi)外已有很多學(xué)者對(duì)RHFS問題進(jìn)行研究，并取得一定的成果。文獻(xiàn)［6］給出一種采用拉格朗日松弛的方法，用于簡化RHFS問題的加權(quán)實(shí)現(xiàn)周期。文獻(xiàn)［7］給出一種迭代Pareto貪心啟發(fā)式算法，用于求解雙目標(biāo)RHFS問題，以達(dá)到最小化最大完工時(shí)間和總延誤的目的。文獻(xiàn)［8-9］利用一種新的NEH-IGA方法來解決RHFS問題，可以有效地縮短最大完成時(shí)限和總加權(quán)完成時(shí)間。文獻(xiàn)［10］設(shè)計(jì)了一種改進(jìn)的多目標(biāo)灰狼優(yōu)化算法，可以縮短RHFS問題的最終完工時(shí)間和總拖期時(shí)間。文獻(xiàn)［11］提出一種基于Minkowski距離交叉算子的局部搜索的Pareto遺傳算法，解決了具有串行階段的RHFS調(diào)度問題。

多元宇宙算法（multi-verse optimizer， MVO）是由Mirjalili等［12］設(shè)計(jì)的一種基于物理機(jī)理的新型智能優(yōu)化算法，它是通過模擬在白洞、黑洞以及蟲洞中轉(zhuǎn)移宇宙中的物質(zhì)而進(jìn)行設(shè)計(jì)的。MVO算法擁有自組織和自調(diào)整的能力，可以根據(jù)調(diào)度問題的實(shí)際情況來自適應(yīng)，在可接受的時(shí)間內(nèi)求得高質(zhì)量的解，近年來被逐漸應(yīng)用于生產(chǎn)調(diào)度問題。文獻(xiàn)［13］使用MVO算法來解決流水車間的劣化效應(yīng)問題。文獻(xiàn)［14］針對(duì)云計(jì)算任務(wù)調(diào)度完成時(shí)間的單目標(biāo)問題，提出了基于改進(jìn)的MVO算法的云任務(wù)調(diào)度策略。文獻(xiàn)［15］建立了考慮運(yùn)行成本和負(fù)荷波動(dòng)的多目標(biāo)社區(qū)綜合能源系統(tǒng)優(yōu)化調(diào)度模型，并提出一種基于Pareto理論的多目標(biāo)MVO算法求解模型。文獻(xiàn)［16］設(shè)計(jì)了改進(jìn)的MVO算法來解決熱軋混合流水車間的多目標(biāo)調(diào)度問題。文獻(xiàn)［17］提出一種耦合橫縱向個(gè)體更新策略的改進(jìn)MVO算法來提高其全局探索和局部開采能力。文獻(xiàn)［3］使用具有學(xué)習(xí)效應(yīng)的MVO算法來解決RHFS調(diào)度問題，但是算法容易陷入局部收斂，在大規(guī)模的生產(chǎn)調(diào)度問題中表現(xiàn)不佳?；诖耍疚脑谠撍惴ǖ幕A(chǔ)上提出一種改進(jìn)的離散MVO算法，通過對(duì)MVO算法的向最優(yōu)宇宙移動(dòng)策略、宇宙更新策略等進(jìn)行改進(jìn)，使算法更適應(yīng)大規(guī)模問題的求解。

1 問題模型

RHFS問題模型可以描述為：一共有I個(gè)待加工工件，每個(gè)工件需要經(jīng)過J個(gè)步驟加工處理并重復(fù)L次，每個(gè)加工步驟有Mj臺(tái)機(jī)器，在確定某些參數(shù)的情況下，需要為工件確定正確的加工順序，并為工件的每個(gè)加工步驟選擇合適的加工機(jī)器，以實(shí)現(xiàn)最小化最大完成時(shí)間。RHFS調(diào)度示意圖如圖1所示。

在RHFS問題模型中，工件之間的優(yōu)先級(jí)沒有限制，一旦加工步驟開始就不能中斷。為了更好地模擬重復(fù)加工的過程，用重入層來描述重復(fù)加工，并將重入層設(shè)置為L-1層，將Ri設(shè)定為工件i在第1層第1個(gè)步驟加工之前的釋放時(shí)間，以便更準(zhǔn)確地模擬出加工過程，從而提高加工效率。

1.1 符號(hào)定義

I為工件集合，I={ii=1，2，…，I}，其中：i為工件編號(hào)；I為工件總數(shù)。J為加工步驟集合，J={j=1，2，…，J}，其中：j為步驟編號(hào)；J為步驟總數(shù)。L為重入層次集合，L={l=1，2，…，L}，其中：l為重入層次編號(hào)；L為總的加工次數(shù)。K為時(shí)間集合，K={k=1，2，…，K}，其中：k為某時(shí)刻；K為計(jì)劃考慮的時(shí)間范圍。Mj為第j個(gè)加工步驟的機(jī)器總數(shù)；Pi，j，l為第i個(gè)工件在第l層第j個(gè)步驟所需的加工時(shí)間；Tl，j，j+1為加工過程中前后兩個(gè)步驟之間工件所需的傳輸時(shí)間，當(dāng)l≠1時(shí)，Tl，0，1>0，表示從l-1層的最后一個(gè)加工步驟到第l層的第1個(gè)加工步驟所需的傳輸時(shí)間；Xijlk表示k時(shí)刻第i個(gè)工件正在第l層的第j個(gè)加工步驟上進(jìn)行加工；Cijl表示第i個(gè)工件在第l層的第j個(gè)階段的完工時(shí)間；Cmax為最大完工時(shí)間。

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

目標(biāo)函數(shù)為

min Cmax。（1）

機(jī)器能力約束為

∑Ii=1∑Ll=1Xijlk≤Mj，i∈I，k∈K。（2）

工件加工時(shí)間約束為

∑Kk=1Xijlk=Pi，j，l，i∈I，j∈J，l∈L。（3）

加工步驟優(yōu)先級(jí)約束為

Ci，j-1，l+Pi，j，l+Tl，j-1，j≤Ci，j，l，i∈I，j∈J，l∈L。（4）

工件動(dòng)態(tài)到達(dá)約束為

Ci，j-1，l-Pi，1，l+1≥Ri，i∈I，j∈J，l∈L。（5）

式（1）表明，本文目標(biāo)是盡可能地縮小最大完工時(shí)間，為了實(shí)現(xiàn)這一目標(biāo)，設(shè)定了一系列約束條件；式（2）表示k時(shí)刻第j個(gè)步驟的機(jī)器個(gè)數(shù)永遠(yuǎn)比在l層第j個(gè)加工步驟進(jìn)行加工的工件總個(gè)數(shù)多或者相等；式（3）表示Pi，j，l為第i個(gè)工件在第j個(gè)步驟的加工時(shí)長；式（4）表示只有在某層的前一階段或前一層的最后階段加工完成，并運(yùn)輸?shù)皆搶拥南乱浑A段或該層的第1階段后才能開始加工；式（5）表示任何一個(gè)工件必須在它到達(dá)第1層的第1個(gè)步驟之后才能開始加工。

Cijl的取值范圍為

Cijl≥0，i∈I，j∈J，l∈L。（6）

Xijlk的取值范圍為

Xijlk∈{0，1}，i∈I，j∈J，l∈L，k∈K。（7）

2 算法設(shè)計(jì)與改進(jìn)

2.1 MVO算法

MVO算法可以分為兩個(gè)階段：探測和開采。在第1階段，利用白洞和黑洞的概念來探索搜索空間；而在第2階段，則利用蟲洞來開采搜索空間，以獲取更多的信息。在RHFS調(diào)度問題中，一個(gè)調(diào)度問題的可行解作為一個(gè)宇宙，每一個(gè)工件作為宇宙中的一個(gè)物質(zhì)，定義每個(gè)宇宙適應(yīng)度值為其膨脹率，適應(yīng)度函數(shù)定義為可行解最大完工時(shí)間的倒數(shù)。初始化種群公式為

U=x11x21…xd1

x12x22…xd2

x1nx2n…xdn，（8）

其中：d為搜索空間的維度；n為多元宇宙的個(gè)數(shù)；xji表示第i個(gè)宇宙的第j個(gè)分量。在每次迭代中，MVO算法會(huì)按照宇宙的膨脹率對(duì)宇宙種群進(jìn)行排序，并采用輪盤賭法的方式從中選出一個(gè)宇宙作為白洞，與另一個(gè)作為黑洞的宇宙進(jìn)行物質(zhì)交換，具體公式為

xji=xjk，r1<NI（Ui），

xji，r1≥NI（Ui），（9）

式中：r1為［0，1］間的隨機(jī)數(shù)；NI（Ui）為第i個(gè)宇宙的歸一化膨脹率；xjk為通過輪盤賭法選出的第k個(gè)宇宙的第j個(gè)分量。宇宙中的物質(zhì)可以通過白洞/黑洞轉(zhuǎn)移策略從一個(gè)高膨脹率的宇宙（白洞）轉(zhuǎn)移到一個(gè)低膨脹率的宇宙（黑洞），從而實(shí)現(xiàn)轉(zhuǎn)移。因此，宇宙的總體膨脹率將在多次迭代中持續(xù)增加。為了改進(jìn)宇宙自身膨脹率，MVO算法會(huì)通過蟲洞將當(dāng)前最優(yōu)宇宙的物質(zhì)傳遞到當(dāng)前宇宙，具體公式為

xji=Xj+TDR×（（ubj-lbj）×r4+lbj）， r3<0.5，r2<WEP，

Xj-TDR×（（ubj-lbj）×r4+lbj）， r3≥0.5，r2<WEP，

xji，r2≥WEP，（10）

式中：r2，r3，r4均為［0，1］范圍內(nèi)的隨機(jī)數(shù)；Xj為當(dāng)前最優(yōu)宇宙的第j個(gè)分量；ubj和lbj分別代表xji的上界和下界；WEP為蟲洞存在的概率，

WEP=WEPmin+l×（WEPmax-WEPminL），（11）

式中：WEPmin代表WEP的最小值，設(shè)定為0.2；WEPmax代表WEP的最大值，設(shè)定為1；l為當(dāng)前迭代次數(shù)。

TDR為物體向當(dāng)前最優(yōu)宇宙移動(dòng)的步長，其更新公式為

TDR=1-l1/pL1/p，（12）

式中：p定義了隨迭代次數(shù)改變的探測速度。p值越高，局部探測速度越快，用時(shí)越短。為了開發(fā)準(zhǔn)確性，設(shè)定p=6。

WEP在迭代過程中線性增大，以在后期進(jìn)行更多的蟲洞交換，從而加快收斂速度。TDR在迭代過程中非線性減小，減小速率先快后慢。因?yàn)樵诘捌谶x出的最優(yōu)種群適應(yīng)度不高，所以開采時(shí)要通過一個(gè)較大的移動(dòng)距離來保持宇宙種群的多樣性，避免宇宙種群過早同化。而在迭代后期，最優(yōu)宇宙具有較高的適應(yīng)度，需要通過減小移動(dòng)距離來加快收斂速度。

2.2 改進(jìn)的離散MVO算法

標(biāo)準(zhǔn)的MVO算法只適合在連續(xù)的解空間中尋找較優(yōu)解問題?；赗HFS調(diào)度問題的解空間是離散的，參考文獻(xiàn)［18］中方法將MVO算法離散化，并在此基礎(chǔ)上進(jìn)行改進(jìn)，使其更適合于RHFS調(diào)度問題。

在原始MVO算法中，主要是通過判斷隨機(jī)數(shù)r1和膨脹率Ui的大小來決定白洞/黑洞轉(zhuǎn)移策略。如果r1小于Ui，則用Uk的第j個(gè)分量代替Ui的第j個(gè)分量，否則不發(fā)生改變。但是，RHFS調(diào)度問題中每個(gè)工件的編號(hào)唯一，如果使用原來的轉(zhuǎn)移策略會(huì)使更新之后的解不合法。對(duì)于RHFS調(diào)度問題，在Ui的第j個(gè)分量需要更新時(shí)，通過交換Uk的第j個(gè)位置的分量和Ui的第j個(gè)位置的分量，以保證解的合法性。

在標(biāo)準(zhǔn)的MVO算法中，通過在迭代過程中和最優(yōu)宇宙進(jìn)行物質(zhì)交換，使宇宙種群不斷地向最優(yōu)宇宙靠近，從而增加算法收斂速度，提高宇宙種群整體的膨脹率。而在原始MVO算法中，這種向最優(yōu)宇宙移動(dòng)策略通過將最優(yōu)宇宙相應(yīng)位置分量直接加/減一個(gè)實(shí)數(shù)距離來實(shí)現(xiàn)。對(duì)應(yīng)于車間調(diào)度問題，相當(dāng)于直接把最優(yōu)解的第j個(gè)加工工件基于工件編號(hào)進(jìn)行移動(dòng)，由于在車間調(diào)度問題中編號(hào)只是用于識(shí)別工件，連續(xù)編號(hào)之間的工件并沒有關(guān)聯(lián)性，所以這種更新策略并不適應(yīng)于車間調(diào)度問題。相比于工件編號(hào)，工件所在的加工次序?qū)φ{(diào)度結(jié)果的影響更大。同時(shí)，基于車間調(diào)度的離散性，對(duì)向最優(yōu)宇宙移動(dòng)策略進(jìn)行了相應(yīng)的改進(jìn)，以確保MVO算法更適用于車間調(diào)度問題。改進(jìn)后的向最優(yōu)宇宙移動(dòng)策略公式為

xj+「TDR（（ubj-lbj）r4+lbj）i=xj，r3<0.5，r2<WEP，

xj-「TDR（（ubj-lbj）r4+lbj）i=xj，r3≥0.5，r2<WEP，

xji=xji，r2≥WEP，（13）

如果Ui的分量值更新后超出最大工件編號(hào)，則將其置為最大工件編號(hào)。在標(biāo)準(zhǔn)的MVO算法進(jìn)行交換更新時(shí)都是對(duì)宇宙本身直接進(jìn)行交換，但是并不能確定當(dāng)前的更新是否使當(dāng)前宇宙更優(yōu)，這會(huì)導(dǎo)致在迭代的過程中，宇宙種群不是一直向使最大完工時(shí)間變小的方向進(jìn)行，尋優(yōu)效率不高。本文借鑒遺傳算法（genetic algorithm，GA）優(yōu)勝劣汰的思想，在每次迭代時(shí)產(chǎn)生一個(gè)新的宇宙來保存更新的結(jié)果，不對(duì)原宇宙進(jìn)行交換。如果原始種群有200個(gè)宇宙，每次迭代經(jīng)過黑洞/白洞交換策略新產(chǎn)生200個(gè)宇宙，經(jīng)過向最優(yōu)宇宙移動(dòng)策略新產(chǎn)生約150個(gè)宇宙，最終對(duì)所有宇宙進(jìn)行排序，取makespan較小的前200個(gè)宇宙進(jìn)入下次迭代。宇宙更新策略算法流程如圖2所示。

2.3 使用啟發(fā)式算法改進(jìn)的MVO算法

標(biāo)準(zhǔn)的MVO算法在生成初始宇宙種群時(shí)，采用隨機(jī)生成的方法。RHFS調(diào)度問題規(guī)模較大，尋優(yōu)空間廣泛，因此隨機(jī)生成宇宙種群會(huì)導(dǎo)致算法效率低下、結(jié)果精確度不高等。使用4條啟發(fā)式規(guī)則（LPT、SPT、FSPT、FLPT）和NEH啟發(fā)式算法［19］，加上局部搜索策略以及迭代貪婪算法對(duì)初始種群的生成進(jìn)行改進(jìn)，提高尋優(yōu)效率和尋優(yōu)精度。

2.3.1 啟發(fā)式規(guī)則

4條啟發(fā)式規(guī)則中，LPT和SPT按照加工時(shí)長進(jìn)行排序，前者優(yōu)先處理加工總時(shí)長大的任務(wù)，后者反之。FSPT和FLPT按照在第1臺(tái)機(jī)器上的加工時(shí)長對(duì)任務(wù)進(jìn)行排序，前者在第1臺(tái)機(jī)器上加工時(shí)長越短越先加工，后者反之?；?條啟發(fā)式規(guī)則分別生成了4個(gè)初始宇宙。

2.3.2 NEH啟發(fā)式算法和局部搜索策略組合使用

Nawaz等［19］提出了NEH啟發(fā)式算法來解決置換流水車間調(diào)度問題。對(duì)于流水車間調(diào)度問題，基本的NEH啟發(fā)式算法不一定能給出最短或者最優(yōu)的加工序列，但可以在一定程度上保證加工序列的局部最優(yōu)性。因此，將NEH啟發(fā)式算法作為生成初始宇宙種群的方法之一。具體操作步驟如下。

Step1 首先計(jì)算各個(gè)工件完成加工所需的總加工時(shí)長，然后根據(jù)計(jì)算得到的加工時(shí)長，將工件降序排列。

Step2 從Step1中取出前兩個(gè)工件，找到一個(gè)加工順序，使這兩個(gè)工件最大完工時(shí)間最小，并保存此順序。

Step3 對(duì)于工件i=3，4，…，I，按順序取出在Step1中按加工時(shí)長降序排列的第i個(gè)工件，把它插入Step2獲得的加工順序的所有可能位置，找到使最大完工時(shí)間最小的插入位置，并保存當(dāng)前加工順序。

Step4 繼續(xù)Step3，直到完成Step1得到的加工序列中所有工件的插入，得到使整體最大完工時(shí)間最小的工件加工順序。

利用NEH啟發(fā)式算法和局部搜索策略組合使用的方式一共生成4個(gè)初始宇宙。

2.3.3 迭代貪婪算法

迭代貪婪（iterated greedy， IG）是一種高效的啟發(fā)式算法，具有實(shí)現(xiàn)簡單、搜索效率高的特點(diǎn)，經(jīng)常用于流水車間調(diào)度問題中。將IG算法作為生成初始宇宙種群的一種方式，其操作步驟如下。

Step1 設(shè)定需要取出的工件個(gè)數(shù)d。

Step2 對(duì)于一個(gè)初始工件加工順序s0，隨機(jī)刪除s0中的n個(gè)工件，然后將刪除的工件按刪除的次序進(jìn)行排列，得到一個(gè)刪除工件順序sn，剩余未刪除的工件序列為sr。

Step3 對(duì)于sn中的工件i=1，2，…，n，從sn中取出第i個(gè)工件，插入sr所有可能的位置，找到可以使優(yōu)化目標(biāo)值最小的位置，得到新的sr。

Step4 如果i<d，i=i+1，否則終止操作。

使用IG算法得到了1個(gè)初始宇宙。

3 實(shí)驗(yàn)與分析

使用Java語言進(jìn)行編程，在Intel i5-1035G1 CPU 2.3GHz PC上運(yùn)行。綜合考慮種群多樣性和計(jì)算量等因素，將蟲洞存在的最小概率設(shè)置為0.2，最大概率設(shè)置為1，種群規(guī)模設(shè)置為200。在未使用啟發(fā)式算法改進(jìn)MVO算法時(shí)，200個(gè)初始宇宙都是隨機(jī)生成的。在使用啟發(fā)式算法改進(jìn)MVO算法時(shí)，191個(gè)初始宇宙隨機(jī)生成，其余9個(gè)初始宇宙，分別由4條啟發(fā)式規(guī)則生成4個(gè)、NEH啟發(fā)式算法和局部搜索策略組合使用生成4個(gè)以及IG算法生成1個(gè)。

在比較使用不同策略改進(jìn)的MVO算法的最大完工時(shí)間時(shí)，設(shè)置最大迭代次數(shù)為1 000。為了方便表示，用MVO_1、MVO_2、MVO_3、和MVO_4分別代表離散的MVO算法、對(duì)向最優(yōu)宇宙移動(dòng)策略進(jìn)行改進(jìn)的MVO算法、使用NEH生成初始種群并對(duì)多元MVO算法的更新策略進(jìn)行改進(jìn)的MVO算法以及綜合以上所有改進(jìn)策略形成的算法。實(shí)驗(yàn)數(shù)據(jù)采用隨機(jī)生成的方式。RHFS調(diào)度模式假定各個(gè)階段都存在著相等數(shù)量的同構(gòu)并行機(jī)，為了簡便，設(shè)Mj=1，L=2，但是所提算法也可以用于求解這兩個(gè)參數(shù)等于其他值的情況。工件的釋放、運(yùn)輸以及各個(gè)加工步驟的加工時(shí)長分別為在［1，4］、［1，5］、［1，100］范圍內(nèi)均勻分布的隨機(jī)數(shù)。根據(jù)I的取值來劃分規(guī)劃，I的4個(gè)取值100、70、50和20分別代表大規(guī)模、中規(guī)模、小規(guī)模以及極小規(guī)模問題，J的取值來自集合{40，30，20}。每組{I，J}隨機(jī)產(chǎn)生10個(gè)實(shí)例，以便進(jìn)行比較和分析，實(shí)驗(yàn)部分一共進(jìn)行了120個(gè)實(shí)例的測試。

表1列出了NEH、IG、GA、MVO算法以及改進(jìn)的MVO算法的實(shí)驗(yàn)結(jié)果。其中，平均改進(jìn)率α=（CMVO_1-CMVO_2）/CMVO_2*100%，平均改進(jìn)率β=（CMVO_1-CMVO_3）/CMVO_3*100%，平均改進(jìn)率γ=（CNEH-CMVO_4）/CMVO_4*100%。表中每種規(guī)模的結(jié)果均為10個(gè)實(shí)例在相同規(guī)模問題中的平均值，以反映其普遍特征。表2列出了極小規(guī)模問題中MVO_1算法和NEH啟發(fā)式算法的實(shí)驗(yàn)結(jié)果。

由表1、表2可得到以下結(jié)論：

1） 在極小規(guī)模問題中，原始MVO算法的求解效率明顯優(yōu)于NEH啟發(fā)式算法，但是在較大規(guī)模問題中，其求解能力卻不及 NEH啟發(fā)式算法。因此，原始MVO算法在較大規(guī)模問題的求解中并不能發(fā)揮出最佳的作用。

2） 對(duì)于大規(guī)模問題，平均改進(jìn)率α、β、γ分別為2.9%、10.6%、1.2%。對(duì)于小規(guī)模問題，α、β、γ分別為2.9%、8.6%、0.8%。使用改進(jìn)策略的MVO算法的求解能力明顯高于NEH啟發(fā)式算法、IG算法以及原始MVO算法。

3） 就整體而言，在大規(guī)模問題中原始MVO算法對(duì)于目標(biāo)值的求解能力低于NEH啟發(fā)式算法，本文通過使用啟發(fā)式算法以及改善MVO算法的更新策略，使MVO算法的求解能力得到明顯提高，MVO算法的使用不再局限于小規(guī)模問題。

4） 為了分析本文提出的向最優(yōu)宇宙移動(dòng)策略對(duì)MVO算法的影響，引入了原始MVO算法（MVO_1）和改進(jìn)向最優(yōu)宇宙移動(dòng)策略的MVO算法（MVO_2）的對(duì)比案例，并通過平均改進(jìn)率表現(xiàn)其改進(jìn)程度。結(jié)果表明，本文提出的向最優(yōu)宇宙移動(dòng)策略更適合于調(diào)度問題的MVO算法，相比于原始MVO算法能夠取得更好的迭代較優(yōu)解。

5） 將GA算法和MVO_4算法的實(shí)驗(yàn)結(jié)果進(jìn)行比較，結(jié)果表明，所提算法對(duì)目標(biāo)值的求解能力明顯優(yōu)于GA算法。

4 結(jié)語

本文研究了以最小化最大完工時(shí)間為目標(biāo)的半導(dǎo)體晶圓制造的調(diào)度問題，基于RHFS調(diào)度模型構(gòu)建了一個(gè)整數(shù)規(guī)劃模型，以解決半導(dǎo)體晶圓制造過程中的調(diào)度問題。同時(shí)，提出了適合于車間調(diào)度問題的改進(jìn)MVO算法，從初始宇宙生成、宇宙更新策略、向最優(yōu)宇宙移動(dòng)策略等方面提高算法的性能。對(duì)比實(shí)驗(yàn)結(jié)果表明，所設(shè)計(jì)的算法在處理RHFS調(diào)度問題時(shí)有著顯著的優(yōu)勢。本文算法重點(diǎn)在于最小化最大完工時(shí)間，但沒有考慮算法的運(yùn)行時(shí)間，未來的研究應(yīng)該著重于如何有效地減少算法的運(yùn)行時(shí)間，同時(shí)兼顧調(diào)度問題的其他目標(biāo)。

參考文獻(xiàn)：

［1］ PAN C R， ZHOU M C， QIAO Y， et al. Scheduling cluster tools in semiconductor manufacturing： recent advances and challenges［J］. IEEE transactions on automation science and engineering， 2018， 15（2）： 586-601.

［2］ 郭乘濤. 基于問題分解與蟻群算法的半導(dǎo)體晶圓制造系統(tǒng)調(diào)度方法的研究［D］. 上海： 上海交通大學(xué)， 2012.

GUO C T. The research on scheduling of wafer fabrication system based on decomposition method and ant colony optimization algorithm［D］. Shanghai： Shanghai Jiaotong University， 2012.

［3］ 董君， 葉春明. 具有學(xué)習(xí)效應(yīng)的半導(dǎo)體晶圓制造綠色車間調(diào)度問題研究［J］. 運(yùn)籌與管理， 2021， 30（4）： 217-223.

DONG J， YE C M. Research on green job shop scheduling problem of semiconductor wafers manufacturing with learning effect［J］. Operations research and management science， 2021， 30（4）： 217-223.

［4］ LIN D P， 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.

［5］ LI L， HUO J Z， TANG O. A hybrid flowshop scheduling problem for a cold treating process in seamless steel tube production［J］. International journal of production research， 2011， 49（15）： 4679-4700.

［6］ 周炳海， 鐘臻怡. 可重入混合流水車間調(diào)度的拉格朗日松弛算法［J］. 控制理論與應(yīng)用， 2015， 32（7）： 881-886.

ZHOU B H， ZHONG Z Y. Lagrangian relaxation algorithm for scheduling problems of reentrant hybrid flow shops［J］. Control theory & applications， 2015， 32（7）： 881-886.

［7］ YING K C， LIN S W， WAN S Y. Bi-objective reentrant hybrid flowshop scheduling： an iterated Pareto greedy algorithm［J］. International journal of production research， 2014， 52（19）： 5735-5747.

［8］ 軒華， 羅書敏， 王薛苑. 可重入混合流水車間調(diào)度的改進(jìn)遺傳算法［J］. 現(xiàn)代制造工程， 2019（2）： 18-23， 35.

XUAN H， LUO S M， WANG X Y. An improved genetic algorithm for reentrant hybrid flow shop scheduling［J］. Modern manufacturing engineering， 2019（2）： 18-23， 35.

［9］ 軒華， 李冰， 羅書敏， 等. 基于總加權(quán)完成時(shí)間的可重入混合流水車間調(diào)度問題［J］. 控制與決策， 2018， 33（12）： 2218-2226.

XUAN H， LI B， LUO S M， et al. Reentrant hybrid flowshop scheduling problem based on total weighted completion time［J］. Control and decision， 2018， 33（12）： 2218-2226.

［10］姚遠(yuǎn)遠(yuǎn)， 葉春明， 楊楓. 雙目標(biāo)可重入混合流水車間調(diào)度問題的離散灰狼優(yōu)化算法［J］. 運(yùn)籌與管理， 2019， 28（8）： 190-199.

YAO Y Y， YE C M， YANG F. Solving bi-objective reentrant hybrid flow shop scheduling problems by a hybrid discrete grey wolf optimizer［J］. Operations research and management science， 2019， 28（8）： 190-199.

［11］CHO H M， BAE S J， KIM J， et al. Bi-objective scheduling for reentrant hybrid flow shop using Pareto genetic algorithm［J］. Computers and industrial engineering， 2011， 61（3）： 529-541.

［12］MIRJALILI S， MIRJALILI S M， HATAMLOU A. Multi-verse optimizer： a nature-inspired algorithm for global optimization［J］. Neural computing and applications， 2016， 27（2）： 495-513.

［13］WANG H F， HUANG M， WANG J W. An effective metaheuristic algorithm for flowshop scheduling with deteriorating jobs［J］. Journal of intelligent manufacturing， 2019， 30（7）： 2733-2742.

［14］王瑞. 云計(jì)算環(huán)境下任務(wù)調(diào)度策略的研究［D］. 贛州： 江西理工大學(xué)， 2021.

WANG R. Research on task scheduling strategy in cloud computing environment［D］. Ganzhou： Jiangxi University of Science and Technology， 2021.

［15］葛續(xù)濤. 計(jì)及多目標(biāo)的社區(qū)綜合能源系統(tǒng)優(yōu)化調(diào)度［D］. 青島： 青島大學(xué)， 2021.

GE X T. Optimal dispatch of community comprehensive energy system considering multi-objective［D］. Qingdao： Qingdao University， 2021.

［16］黃輝. 熱軋混合流水車間調(diào)度方法及仿真系統(tǒng)研究［D］. 重慶： 重慶大學(xué)， 2021.

HUANG H. Study on scheduling method and simulation system of hot rolling hybrid flow workshop［D］. Chongqing： Chongqing University， 2021.

［17］趙世杰， 高雷阜， 徒君， 等. 耦合橫縱向個(gè)體更新策略的改進(jìn)MVO算法［J］. 控制與決策， 2018， 33（8）： 1422-1428.

ZHAO S J， GAO L F， TU J， et al. Improved multi verse optimizer coupling horizontal-and-vertical individual updated strategies［J］. Control and decision， 2018， 33（8）： 1422-1428.

［18］張強(qiáng)， 姜慧清， 王穎， 等. 基于離散多元宇宙算法求解車輛路徑問題［J］. 電子科技大學(xué)學(xué)報(bào)， 2021， 50（6）： 890-898.

ZHANG Q， JIANG H Q， WANG Y， et al. Solving vehicle routing problem with fuzzy time window based on discrete multiverse algorithm［J］. Journal of university of electronic science and technology of China， 2021， 50（6）： 890-898.

［19］NAWAZ M， ENSCORE E E， HAM I. A heuristic algorithm for the m-machine， n-job flow-shop sequencing problem［J］. Omega， 1983， 11（1）： 91-95.