• <tr id="yyy80"></tr>
  • <sup id="yyy80"></sup>
  • <tfoot id="yyy80"><noscript id="yyy80"></noscript></tfoot>
  • 99热精品在线国产_美女午夜性视频免费_国产精品国产高清国产av_av欧美777_自拍偷自拍亚洲精品老妇_亚洲熟女精品中文字幕_www日本黄色视频网_国产精品野战在线观看 ?

    多目標(biāo)變分批混合流水車間調(diào)度算法自動設(shè)計

    2022-12-05 11:40:26孟磊磊桑紅燕
    計算機(jī)集成制造系統(tǒng) 2022年11期
    關(guān)鍵詞:算例機(jī)器調(diào)度

    張 彪,孟磊磊,桑紅燕,盧 超

    (1.聊城大學(xué) 計算機(jī)學(xué)院,山東 聊城 252000;2.中國地質(zhì)大學(xué)(武漢)計算機(jī)學(xué)院,湖北 武漢 430074)

    0 引言

    混合流水車間調(diào)度問題(Hybrid Flowshop Scheduling Problem, HFSP)作為流水車間調(diào)度問題的一個分支,因其重要的理論價值和實用價值引起了研究人員的廣泛關(guān)注[1-5]。HFSP常見于電子、家具、紡織、石化、制藥等各種柔性制造車間中[6-7]。HFSP要根據(jù)生產(chǎn)約束確定各階段的作業(yè)順序和機(jī)器分配,即使是在非常小規(guī)模的問題實例上,也被證明是NP困難的[1]。在目前大多數(shù)關(guān)于HFSP的研究中,作業(yè)是不能被分割的,即每個作業(yè)在某一特定階段完成之前不能轉(zhuǎn)移到下游階段。然而,在許多現(xiàn)實場景中,這將對生產(chǎn)效率產(chǎn)生負(fù)面影響,在這些場景中,一個作業(yè)是由一系列相同的加工單元組成的。

    REITER[8]首先在作業(yè)車間調(diào)度問題中引入了批量流技術(shù),高效地完成了基于生產(chǎn)效率的調(diào)度目標(biāo)。如今,批量流技術(shù)被制造企業(yè)廣泛使用,以提升它們的客戶服務(wù)[9]。批量流技術(shù)將一個給定的批次分割成若干較小的子批,以實現(xiàn)在一個多階段制造車間中同一批次在不同階段中的并行加工。也就是說,批次的一個子批一旦在某一階段完成加工,就可以立即運輸?shù)较掠坞A段。因此,它的好處是減少生產(chǎn)周期,從而更快地生產(chǎn)和交付產(chǎn)品。此外,它還具有減少在制品庫存、線邊倉和空間需求的優(yōu)點。批量流的劃分方法可分為等量分批、一致分批和可變分批[9-10]。在等量分批下,同一批次的不同子批規(guī)模是相同的,并且在不同階段保持一致;在一致分批下,批次的不同子批規(guī)模可能不同,但在不同階段保持一致;而在可變分批下,批次的不同子批規(guī)模可能不同,并且在不同階段也保持變化。顯然,可變分批是最復(fù)雜的情形,等量分批和一致分批則可作為可變分批的特例。

    因此,本文將可變分批引入HFSP中,除了考慮批次順序和機(jī)器分配之外,每個批次的批次分割(即子批數(shù)量和子批規(guī)模)都應(yīng)被考慮。本文研究的問題比經(jīng)典HFSP要困難得多,顯然也是NP困難的。批量流技術(shù)能夠縮短生產(chǎn)周期,但它也有實現(xiàn)成本,如子批的運輸和管理。也就是說,子批的數(shù)量越大,最大完工時間就可能越小,但相應(yīng)的運輸成本會增加。因此,考慮到實際中子批的運輸成本,子批的總量會受到限制。總而言之,最大完工時間與子批總量之間通常存在著一種權(quán)衡關(guān)系。因此,本文將致力于解決多目標(biāo)變分批混合流水車間調(diào)度問題(Multi-objective Hybrid Flowshop Scheduling Problem with Variable Sublot, MOHFSP_VS),同時優(yōu)化最大完工時間和子批總量。

    在現(xiàn)有批量流HFSP文獻(xiàn)中,涉及到多目標(biāo)優(yōu)化,只查到兩篇論文。CHEN等[11]研究了一種具有一致分批的HFSP,同時考慮機(jī)器具有不同的加工速度,以最小化最大完工時間和能耗為目標(biāo),其提出一種多目標(biāo)遺傳算法,在其研究中,每個批次的子批數(shù)量是預(yù)先確定的。LI等[12]研究了一種可變子批的多目標(biāo)HFSP,最小化4個目標(biāo),即逗留時間懲罰、能量消耗、提前和延遲值。需要注意的是,在該研究中,可變子批只是指每個批次在不同階段的子批數(shù)量可能不同,但同一批次不同子批的規(guī)模是相同的,即每個子批的加工時間是預(yù)先確定的。為求解上述問題,LI等[12]提出了基于分解的多目標(biāo)進(jìn)化算法。在上述研究中,來自不同批次的子批可以混合。但當(dāng)不同批次間具有啟動作業(yè)時,這種設(shè)置是不現(xiàn)實的,因為要頻繁地進(jìn)行切換,嚴(yán)重影響加工效率。因此,本文設(shè)定來自不同批次的子批不可以混合。此外,上述研究均將批量流作為問題約束,沒有研究生產(chǎn)效率與批量分割之間的權(quán)衡關(guān)系,而本文將重點研究這一問題。ZHANG等[13]研究了基于一致分批的HFSP,同時考慮了啟動和運輸操作,并利用AAD算法取得了滿意的效果。本文將在此基礎(chǔ)上,研究基于可變分批的HFSP,利用自動算法設(shè)計(Automated Algorithm Design,AAD)方法自動構(gòu)建MOEA。

    因為問題的NP難特性,為解決MOHFSP_VS,本文采用多目標(biāo)進(jìn)化算法(Multi-objective Evolutionary Algorithm, MOEA)進(jìn)行求解。眾所周知,MOEA的性能在很大程度上依賴于算法參數(shù)值(包括數(shù)值參數(shù)和類別參數(shù))的設(shè)置[14-15]。事實上,這些參數(shù)的設(shè)置取決于所解決的問題。然而,傳統(tǒng)的設(shè)置過程可能會受到以往經(jīng)驗的影響。為了消除這些限制,本文引入一種自動算法設(shè)計(AAD)方法[16-19]基于算法框架來自動構(gòu)建MOEA。本文采用的AAD方法稱為I/F-Race(iterated F-race)[16],它通過測試一組測試算例,自動尋找并組合最佳參數(shù)取值,從而構(gòu)建一個針對給定問題表現(xiàn)優(yōu)異的自動算法,避免了過多的人為干預(yù)。關(guān)于所選擇的算法框架,本文采用多目標(biāo)離散人工蜂群算法(Multi-objective Discrete Artificial Bee Colony algorithm, MDABC)[20]。MDABC利用分解策略,通過使用聚合函數(shù)將多目標(biāo)問題分解為若干標(biāo)量子問題,并通過協(xié)作的方法同時優(yōu)化這些子問題。選擇該算法框架的原因如下:一方面,MDABC在HFSP上表現(xiàn)出了優(yōu)異的性能;另一方面,求解MOHFSP_VS,需要同時解決一些耦合的問題,如批次排序、機(jī)器分配和批量分割,因此,在解的編碼中需要包含不同的部分來呈現(xiàn)不同的解空間信息,每個部分都有其特定的鄰域結(jié)構(gòu)。此外,由于問題間是高度耦合的,使用基于鄰域結(jié)構(gòu)的元啟發(fā)式算法可以實現(xiàn)不同鄰域結(jié)構(gòu)之間的交互。而MDABC正是基于變鄰域下降策略(Variable Neighborhood Descent, VND)開發(fā)的一種基于協(xié)作的MOEA。

    本文的主要貢獻(xiàn)總結(jié)如下:①在可變分批策略下,研究了考慮啟動和運輸操作的多目標(biāo)HFSP;②建立了多目標(biāo)混合整數(shù)規(guī)劃模型,同時優(yōu)化最大完工時間和子批總數(shù);③引入了一種自動算法設(shè)計方法,構(gòu)建高性能的MOEA。

    1 問題描述

    在MOHFSP_VS中,一系列批次要經(jīng)過連續(xù)的階段進(jìn)行加工,每個階段包含若干相同的機(jī)器,并且每個批次包含若干加工單元,加工單元的數(shù)量稱為批次規(guī)模。在變分批策略下,每個批次被分割成若干子批,受運輸管理的限制,子批的數(shù)量有一個最大限定值。每個子批包含不同數(shù)量的加工單元,加工單元的數(shù)量稱為子批規(guī)模。批次的子批數(shù)量和子批規(guī)模在不同階段是發(fā)生變化的。來自同一批次的不同子批需要在每個階段的同一臺機(jī)器上連續(xù)加工,子批內(nèi)的加工單元也是連續(xù)性地加工。也就是說,一個子批的加工時間是子批規(guī)模和單位加工時間(一個加工單元的加工時間)的乘積。不同的批次之間機(jī)器需要執(zhí)行啟動操作,而同一批次的任意兩個連續(xù)子批間則不需要啟動操作。此外,不同批次在不同階段需要的啟動時間也不同的。當(dāng)一個子批在某一階段完成加工后,立即被運輸?shù)较乱浑A段,兩個不同連續(xù)階段之間的運輸時間是不同。MOHFSP_VS的特征如下:

    (1)所有批次中的加工單元在0時刻均是可用的,不考慮優(yōu)先權(quán)和中斷。

    (2)機(jī)器可以有空閑時間,各階段之間的緩沖區(qū)容量是無限的。

    (3)每個批次都要經(jīng)過所有階段,在一個階段上,每個批次只能分配到一臺機(jī)器。

    (4)每個批次被分割成若干子批,但子批數(shù)有一個限定的最大值。每個子批規(guī)??赡懿煌?,相同子批在不同階段上的規(guī)模也可能不同。

    (5)每個子批在某一階段完成加工后,將立即傳輸?shù)较掠坞A段。

    (6)同一批次的各個子批在一臺機(jī)器上連續(xù)地進(jìn)行加工。在運輸?shù)教囟A段后,第一個子批可在啟動操作之后開始加工,其余的子批在運輸?shù)竭@個階段后,在前一個子批完成加工后開始加工。

    (7)在任意時刻,一臺機(jī)器至多只能加工一個加工單元,一個子批中的加工單元連續(xù)地進(jìn)行加工。

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

    MOHFSP_VS需要確定不同階段的批次分割、批次順序和機(jī)器分配。為了建立多目標(biāo)混合整數(shù)規(guī)劃模型,表1和表2所示為問題參數(shù)和決策變量的符號與定義。對于可變分批,與等量和一致分批相比,存在一個重要的約束條件,即對于一個給定的批次,它的任一子批都不能包含屬于那些在先前階段未完成并轉(zhuǎn)移到該階段的子批中的加工單元。因此,該模型的主要貢獻(xiàn)在于引入了一個決策變量Xi,j,e,e′,用來描述批次的子批規(guī)模間關(guān)系。

    表1 模型問題參數(shù)符號與定義

    表2 模型決策變量符號與定義

    基于表1和表2中的符號表示,本文建立的多目標(biāo)混合整數(shù)規(guī)劃模型如下:

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

    minMS;

    (1)

    (2)

    s.t.

    MS≥Em,j,L,?j∈J;

    (3)

    Si,j,e≥0,?i∈I,j∈J,e∈[1,L];

    (4)

    (5)

    (6)

    B1,j,1≥t1,j,?j∈J;

    (7)

    Ei,j,e-Bi,j,e=pk,j×Si,j,e,

    ?i∈I,j∈J,e∈[1,…,L];

    (8)

    Bi,j,e+1-Ei,j,e≥0,?i∈I,

    j∈J,e∈[1,…,L-1];

    (9)

    Yi,j,j′,k+Yi,j′,j,k≤1,?j,j′∈J,k∈Mi;

    (10)

    Yi,j,j′,k+Yi,j′,j,k≤Di,j,k+Di,j′,k,

    ?i∈I,j,j′∈J,k∈Mi;

    (11)

    Di,j,k+Di,j′,k-1≤Yi,j,j′,k+Yi,j′,j,k,

    ?i∈I,j,j′∈J,k∈Mi;

    (12)

    Bi,j,1-Ei,j′,L-ti,j+Q×(3-Yi,j′,j,k-Di,j,k-

    Di,j′,k)≥0,?i∈I,j,j′∈J,k∈Mi;

    (13)

    ?i∈I,j∈J,e∈[1,…,l];

    (14)

    Bi+1,j,1≥Ei,j,1+fi,j×Wi,j,1+si+1,j,

    ?i∈{1,2,…m-1},j∈J;

    (15)

    Bi+1,j,1+Q×(1-Xi+1.j,1,e′)≥fi,j×Wi,j,e′+ti+1,j+

    Ei,j,e′,?i∈I,j∈J,e′∈[1,…,L];

    (16)

    Bi+1,j,e+Q×(1-Xi+1,j,e,e′)≥Ei.j,e′+fi,j×Wi,j,e,

    ?i∈I,j∈J,e,e′∈[2,…,L];

    (17)

    i∈[1,…,m-1],j∈J,

    u∈[1,…,L],u′∈[2,…,L];

    (18)

    Wi,j,e≥Wi,j,e+1,?i∈I,j∈J,e∈[1,…,L-1];

    (19)

    Di,j,k∈{0,1},

    ?i∈I,j∈J,k∈M,k∈{1,2,…,σi};

    (20)

    Yi,j,j′,k∈{0,1},?i∈I,j,j′∈J,k∈M;

    (21)

    Wi,j,e∈{0,1},?i∈I,j∈J,e∈[1,…,L];

    (22)

    Xi,j,e,e′∈{0,1},?i∈I,j∈J,e,e′∈[1,…,n]。

    (23)

    其中:式(1)定義了模型的目標(biāo)之一:最大完工時間(MS)。式(2)定義了模型的目標(biāo)之二:批次在所有階段的子批總數(shù)(NOS)。式(3)保證MS要大于每個批次的最后一個子批在最后一階段上的完工時間。式(4)要求在每個階段每個子批的規(guī)模要大于等于0。式(5)要求在每一階段對于給定的批次,子批規(guī)模之和等于批次的總規(guī)模。式(6)保證了每個批次都要經(jīng)過所有階段的加工,并且在每個階段只能分配到一臺機(jī)器上。因為在問題中考慮了啟動操作,式(7)要求在第一個階段,每個批次的第一個子批的開始加工時間要大于它的啟動時間。式(8)保證了每個子批的加工不能被打斷。式(9)保證在每個階段,來自給定批次的子批只有在它相鄰的前一個子批完成加工之后才能開始加工。式(10)~式(12)共同定義了變量Di,j,k和Yi,j,j′,k的關(guān)系,兩個變量的取值決定了批次的機(jī)器分配和調(diào)度次序。式(13)表達(dá)了如果有任意的批次在其之前加工,每個批次的第一個子批只有在啟動操作完成之后才能開始加工。式(14)定義了決策變量Si,j,e和Wi,j,e的關(guān)系,當(dāng)Si,j,e>0時,Wi,j,e=1,而當(dāng)Si,j,e=0時,Wi,j,e=0。式(15)表達(dá)了在非第一階段的各個階段,每個批次的第一個子批只有在先前階段完成加工并到達(dá)后才能開始加工。式(16)定義了在非第一階段的各個階段,每個批次的第一個子批只有在相關(guān)的另一子批在前一階段完成加工并到達(dá)以及完成啟動操作后才能開始加工。式(17)表述了每個批次的子批(第一子批除外)是否能夠在相關(guān)子批的前一階段完成加工并到達(dá)后開始加工。式(18)表明對于給定的批次,對于其內(nèi)的子批,不能包含屬于在前一階段還沒有完成加工的子批內(nèi)的加工單元。式(16)~式(18)共同定義了應(yīng)用變分批之后的重要約束:對于一個給定的批次,其任一子批都不能包含在先前階段未完成或者沒有轉(zhuǎn)移到該階段子批中的加工單元。式(19)保證了優(yōu)先給予位列前面的子批去容納加工單元。式(20)~式(23)定義了4個決策變量的取值范圍。

    1.2 兩目標(biāo)的權(quán)衡關(guān)系

    變分批技術(shù)能夠有效降低最大完工時間,但其自身也有實現(xiàn)成本:分批之后,子批總數(shù)增加,需要管理更多的運輸作業(yè),從而加大了運輸成本。同時,不充分的分批會限制提升生產(chǎn)效率的效果,從而導(dǎo)致較大的最大完工時間。也就是說,最大完工時間和子批總數(shù)存在著權(quán)衡關(guān)系。為了進(jìn)一步解釋和評估它們之間的關(guān)系,這里考慮一個具有4個批次和2個階段(第一階段擁有3臺機(jī)器,第二階段擁有2臺機(jī)器)的測試實例。每個批次的最大子批數(shù)量設(shè)為5,其他相關(guān)的加工數(shù)據(jù)如下:

    fi,j=[12,10,10,11],Tj=[66,57,79,85]。

    事實上,一個多目標(biāo)優(yōu)化問題(Multi-objective Optimization Problem, MOP)的Pareto最優(yōu)解能夠成為MOP標(biāo)量子問題的最優(yōu)解[13]。因此,為了得到MOHFSP_VS的Pareto最優(yōu)解,利用50個均勻分布的權(quán)重向量對兩個目標(biāo)進(jìn)行線性加權(quán),生成50個不同的標(biāo)量子問題。采用IBM ILOG CPLEX12.7.1(著名的商用數(shù)學(xué)規(guī)劃模型求解器)求解50個標(biāo)量子問題的最優(yōu)解,并將收集到的非支配解標(biāo)注到圖1中。從圖1中可以看出,MS和NOS兩個目標(biāo)不能同時被優(yōu)化,即隨著子批總數(shù)的增加,最大完工時間在逐漸減少。此外,圖1中最優(yōu)MS和最優(yōu)NOS兩個解所對應(yīng)的調(diào)度方案如圖2和圖3所示。圖2為最優(yōu)NOS對應(yīng)的調(diào)度甘特圖,從圖中可以看出每個批次均只含有一個子批,NOS也就最小,MS相應(yīng)地也就最大,此調(diào)度方案相當(dāng)于不采用分批的HFSP調(diào)度。圖3為最優(yōu)MS對應(yīng)的調(diào)度甘特圖,從圖中可以看出每個批次均分割為若干子批,NOS最大,MS相應(yīng)地也就最小。綜上所述,變分批技術(shù)能夠有效地降低MS,同時,MS和NOS兩目標(biāo)間存在著權(quán)衡關(guān)系。

    2 針對問題特性的算法配置及自動算法設(shè)計

    MDABC主要包含種群初始化階段、基于VND的雇傭蜂階段、基于協(xié)作的旁觀者蜂階段以及基于解交換的偵查蜂階段4個階段[19]。在種群初始化階段,由于采用了分解策略,需要在解空間中隨機(jī)生成N個解(Xi,i=1,…,N),每個解都要分配一個特定的權(quán)重(Wi,i=1,…,N);在基于VND的雇傭蜂階段,每個解通過VND策略搜索鄰域結(jié)構(gòu)來改進(jìn)自己;在基于協(xié)作的旁觀者峰階段,它的核心思想在于利用優(yōu)良解探索更多的協(xié)作信息;在基于解交換的偵查蜂階段,會判定每個子問題的解是否在過去的L次連續(xù)迭代中得到了改進(jìn)。如果沒有,則尋找它所支配的鄰近子問題中的一個解,然后,兩個鄰近子問題交換它們的解。

    在MDABC中,存在3個需要配置的數(shù)值參數(shù),包括子問題的數(shù)量(N)、每個子問題鄰近子問題的數(shù)量(T)、交換解前連續(xù)不成功的代數(shù)(L)。對于可配置的類別參數(shù),它們與MOHFSP_VS的問題特征緊密相關(guān)。接下來,考慮到問題特性,本文先設(shè)計了問題的編碼方案和權(quán)重的產(chǎn)生方法,然后詳細(xì)介紹了4個可配置的類別參數(shù)和1個相關(guān)的數(shù)值參數(shù)。

    2.1 問題編碼與權(quán)重產(chǎn)生

    根據(jù)問題描述,求解MOHFSP_VS需要同時解決3個相互耦合的問題,即批次排序、機(jī)器分配以及批次分割。利用元啟發(fā)式算法求解優(yōu)化問題時,解的編碼需要承載必要的信息,能夠利用解碼規(guī)則翻譯成詳細(xì)的調(diào)度方案。在有限的計算成本限制下,批次序列編碼[21-23]在研究中得到了廣泛應(yīng)用且表現(xiàn)優(yōu)異。批次序列表示在第一階段的批次調(diào)度順序,而在后續(xù)階段中,批次的調(diào)度順序由相應(yīng)的啟發(fā)式規(guī)則得到,機(jī)器分配同樣如此。由于不允許來自不同批次的子批混合在一起,批次分割需要單獨處理。綜上所述,在本文中,解的編碼分為兩部分:①一個n維的向量π={π1,…,πj,…,πn},其中πj表示批次索引,n表示批次的數(shù)量;②批次分割矩陣的集合,即Δn={ψ1,…,ψj,…,ψn},其中ψj為具有m行L列的批次分割矩陣,

    2.2 動態(tài)解碼和可配置的解碼啟發(fā)式規(guī)則

    解碼過程是將解的編碼翻譯成可行調(diào)度方案的過程。為了求解MOHFSP_VS,需要同時考慮3個問題:批次序列,機(jī)器分配,以及批次分割。鑒于變分批技術(shù)的引入,為防止不可行解的產(chǎn)生,本文提出一種動態(tài)的解碼過程,如下所示:

    步驟1在第一個階段,即i=1,依次從序列π={π1,…,πj,…,πn}中取出πj。執(zhí)行以下流程:

    步驟 1.1根據(jù)可配置的啟發(fā)式規(guī)則,確定πj的分配機(jī)器和機(jī)器空閑時間。

    步驟 1.2計算批次πj的各子批在第一階段的加工時間。根據(jù)加工約束,依次調(diào)度各子批。有如下兩種情形:

    (1)若為第一子批,則子批的開始加工時間為機(jī)器的空閑時間和啟動時間之和。完工時間為開始加工時間和子批的加工時間之和。利用完工時間更新機(jī)器的空閑時間。

    (2)若不是第一子批,則子批的開始加工時間為機(jī)器的空閑時間。完工時間為開始加工時間和子批的加工時間之和。

    步驟 2.1根據(jù)可配置的啟發(fā)式規(guī)則,確定πj′的分配機(jī)器和機(jī)器空閑時間。

    步驟 2.2計算πj′的各子批在階段i的加工時間。定義4個臨時變量:變量ScheduledUnits記錄已調(diào)度過的加工單元數(shù)量、SchedulingUnits記錄可以調(diào)度的加工單元數(shù)量、ArrivedUnits記錄已到達(dá)的加工單元總數(shù)、ArrivedSublot記錄還沒到的最鄰近子批。根據(jù)加工約束,依次調(diào)度各子批。有如下兩種情形:

    (1)若為第一子批,執(zhí)行如下流程:

    步驟 2.2.1在調(diào)度時刻點,即機(jī)器的空閑時間和啟動時間之和,得到ArrivedUnits的值。具體方法如下:依次從ArrivedSublot遍歷到Tj,直到某一子批在調(diào)度時刻點還未達(dá)到階段i,利用這一子批更新ArrivedSublot。將在調(diào)度時刻點已經(jīng)達(dá)到階段i的子批所包含的加工單元數(shù)記錄到ArrivedUnits中。

    步驟 2.2.2得到SchedulingUnits的值,具體方法為SchedulingUnits=ArrivedUnits-ScheduledUnits。開始調(diào)度第1子批,有如下兩種情形:

    1)若第一子批在階段i所包含的加工單元數(shù)小于或等于SchedulingUnits,則在調(diào)度時刻點開始進(jìn)行加工,開始加工時間即為調(diào)度時刻點,完工時間為開始時間與加工時間之和。利用完工時間更新機(jī)器的空閑時間,利用該子批所包含的加工單元數(shù)更新SchedulingUnits和ScheduledUnits。

    2)若第一子批在階段i所包含的加工單元數(shù)大于SchedulingUnits,則需要等待足夠的加工單元數(shù)到來之后才能開始進(jìn)行加工。具體方法如下:依次從ArrivedSublot遍歷到Tj,將子批的加工單元數(shù)加到ArrivedUnits,得到SchedulingUnits,該遍歷到SchedulingUnits大于等于第一子批在階段i所包含的加工單元數(shù)停止,并更新ArrivedSublot。第一子批開始加工,開始時間為子批ArrivedSublot-1運輸?shù)诫A段i的時間,完工時間為開始時間與加工時間之和。利用完工時間更新機(jī)器的空閑時間,利用該子批所包含的加工單元數(shù)更新SchedulingUnits和ScheduledUnits。

    (2)若不是第一子批,執(zhí)行如下流程:

    步驟2.2.1在調(diào)度時刻點,即機(jī)器的空閑時間,得到ArrivedUnits的值。具體方法如下:依次從ArrivedSublot遍歷到Tj,直到某一子批在調(diào)度時刻點還未達(dá)到階段i,利用這一子批更新ArrivedSublot。將在調(diào)度時刻點,已經(jīng)達(dá)到階段i的子批所包含的加工單元數(shù)記錄到ArrivedUnits中。

    步驟 2.2.2得到SchedulingUnits的值,具體方法為SchedulingUnits=ArrivedUnits-ScheduledUnits。開始調(diào)度當(dāng)前子批,有如下兩種情形:

    1)如果當(dāng)前子批在階段i所包含的加工單元數(shù)小于或等于SchedulingUnits,則在調(diào)度時刻點開始進(jìn)行加工,開始時間即為調(diào)度時刻點,完工時間為開始時間與加工時間之和。利用完工時間更新機(jī)器的空閑時間,利用該子批所包含的加工單元數(shù)更新SchedulingUnits和ScheduledUnits。

    2)如果當(dāng)前子批在階段i所包含的加工單元數(shù)大于SchedulingUnits,則需要等待足夠的加工單元數(shù)到來之后才能開始進(jìn)行加工。具體方法如下:依次從ArrivedSublot遍歷到Tj,將子批的加工單元數(shù)加到ArrivedUnits,得到SchedulingUnits,該遍歷到SchedulingUnits大于等于當(dāng)前子批在階段i所包含的加工單元數(shù)停止,并更新ArrivedSublot。當(dāng)前子批開始加工,開始時間為子批ArrivedSublot-1運輸?shù)诫A段i的時間,完工時間為開始加時間與加工時間之和。利用完工時間更新機(jī)器的空閑時間,利用該子批所包含的加工單元數(shù)更新SchedulingUnits和ScheduledUnits。

    可配置的啟發(fā)式規(guī)則描述如下??紤]批次序列,本文引入了“先到先得”規(guī)則,因為其在求解以時間為目標(biāo)的調(diào)度問題[1]時表現(xiàn)出了良好的性能。具體來說,在第一階段,編碼中的批次序列可以直接反映批次的調(diào)度順序。而在后續(xù)階段的批次調(diào)度順序均按“先到先得”規(guī)則而定,即在上一階段較早完成的批次,可優(yōu)先在下一階段進(jìn)行加工??紤]到批次分割的特點,本文提出兩種方法來實現(xiàn)“先到先得”規(guī)則:①“子批優(yōu)先”(Sublot Preemption, SP),即在前一階段較早完成的子批所屬的批次具有優(yōu)先加工權(quán);②“批次優(yōu)先”(Lot Preemption, LP),即在前一階段較早完成的最后一個子批所屬的批次具有優(yōu)先加工權(quán)??紤]機(jī)器分配,本文采用“優(yōu)先可用”(First Available, FA)和“優(yōu)先完成”(First Completion, FC)兩種規(guī)則?!皟?yōu)先可用”表示具有較早可用時間的機(jī)器擁有優(yōu)先分配權(quán);“優(yōu)先完成”表示較早能夠加工完批次的機(jī)器擁有優(yōu)先分配權(quán)。

    綜上所述,針對問題的解碼過程,可得到4個可配置的解碼啟發(fā)式規(guī)則組合,即“批次優(yōu)先”和“優(yōu)先可用”的組合(LP_FA)、“批次優(yōu)先”和“優(yōu)先完成”的組合(LP_FC)、“子批優(yōu)先”和“優(yōu)先可用”的組合(SP_FA)以及“子批優(yōu)先”和“優(yōu)先完成”的組合(SP_FC)。

    2.3 可配置的初始解生成方法

    好的初始解生成方法有利于提高元啟發(fā)式算法搜索效率。本節(jié)基于問題編碼,設(shè)計了初始解的生成方法。首先,介紹了分割矩陣Δn的生成方法,然后給出了批次序列π的生成方法。對于初始化Δn,設(shè)計了3種方法,即均勻初始化(Uniform Initialization,UI)、隨機(jī)初始化(Random Initialization,RI)和混合初始化(Mixed Initialization,MI)。具體流程描述如下:

    (1)均勻初始化方法

    (2)隨機(jī)初始化方法

    步驟 1對于每個批次j(j=1,…,n)來說,首先將剩余規(guī)模rj的值設(shè)為Tj。對于批次j來說,在階段i(i=1,…,m)上,依次從子批e=1到子批e=L,確定它們的子批規(guī)模。

    步驟 2若e∈[1,L-1],批次j的子批e在階段i上的子批規(guī)模Si,j,e在區(qū)間[0,rj]內(nèi)隨機(jī)產(chǎn)生。

    步驟 3若e=L,批次j的子批e在階段i上的子批規(guī)模Si,j,e設(shè)置為rj。

    (3)混合初始化方法

    步驟 1以一種均勻的方式分割批次j(j=1,…,n)。

    步驟 2.1在區(qū)間[0,Si,j,e]得到一個隨機(jī)整數(shù)Random,然后以50%的概率執(zhí)行Si,j,e=Si,j,e+Random或者Si,j,e=Si,j,e-Random。

    步驟 2.2對于子批L+1-e,則以50%的概率執(zhí)行Si,j,L+1-e=Si,j,L+1-e-Random或者Si,j,L+1-e=Si,j,L+1-e+Random。

    步驟 2.3打亂子批排序。通過上述步驟,每個子批規(guī)模已被確定。為保證隨機(jī)性,子批序列被隨機(jī)打亂。

    一旦分割矩陣Δn生成,各批次中子批的加工時間就能夠確認(rèn),因此根據(jù)一些啟發(fā)式規(guī)則,批次序列πn的初始化也能夠完成。本文引入了文獻(xiàn)中用于初始化批次排列的6種啟發(fā)式規(guī)則,它們均在求解HFSP中表現(xiàn)出了較好的性能,分別為SPT(shortest processing time),VSPT(variant of SPT),NEH(Nawaz, Enscore, and Ham),GRASP(greedy randomized adaptive search procedure),GRASP_NEH,以及RI(random initialization)。除了RI之外,因為批量流的應(yīng)用,這些規(guī)則都不能直接用于MOHFSP_VS,具體操作見文獻(xiàn)[13]。

    綜上所述,本文采用了3種批次分割矩陣初始化方法和6種批次序列初始化方法。將它們結(jié)合起來,總共可以得到18種方法來進(jìn)行解的初始化。

    2.4 可配置的分解策略和目標(biāo)歸一化

    基于分解策略求解組合優(yōu)化問題,有兩種通用的策略去聚集多個目標(biāo):加權(quán)和方法(Weighted Sum)和切比雪夫方法(Tchebycheff)[24]。本文將這兩種分解方法設(shè)置為可配置的。此外,在先期實驗中,已知兩個目標(biāo)有不同的量綱。若不采取措施將導(dǎo)致算法偏向于量綱大的目標(biāo)進(jìn)行搜索。為解決這一問題,本文采用簡單的Max-Min方法對兩個目標(biāo)進(jìn)行歸一化,如式(24)所示。歸一化方法的使用和不使用在本文中被認(rèn)為是可配置的。

    (24)

    根據(jù)上述定義,兩目標(biāo)的上下界可以經(jīng)過下列公式得出:

    (25)

    (26)

    (27)

    (28)

    2.5 鄰域結(jié)構(gòu)設(shè)計及可配置的協(xié)同操作

    MDABC算法在雇傭蜂階段,采用了VND策略。因此,需要根據(jù)解的編碼來設(shè)計鄰域結(jié)構(gòu)。對于批次序列向量π={π1,…,πj,…,πn},本文采用兩種應(yīng)用廣泛的鄰域結(jié)構(gòu),即插入和交換策略。對于批次分割矩陣集合Δn={ψ1,…,ψj,…,ψn},本文提出一種批次分割矩陣ψj的變化操作。在此基礎(chǔ)上,提出兩種組合結(jié)構(gòu),分別組合插入操作和變化操作,以及交換操作和變化操作。5種鄰域結(jié)構(gòu)具體如圖4所示:①插入操作:從批次序列向量πn中隨機(jī)選擇一批次,然后將它隨機(jī)插入到一個隨機(jī)選擇的位置中。②交換操作:從批次序列向量πn中隨機(jī)選擇兩批次,然后交換它們的位置。③變化操作:從批次分割矩陣集合中隨機(jī)選取帶有至少兩個子批的批次ψj。針對ψj,在每一階段i,隨機(jī)選擇兩個子批,將一個子批的規(guī)??s減一個基于分布U[0,5]得到的一整數(shù),而相應(yīng)地,將另一子批的規(guī)模增加一個相同的整數(shù)。④組合結(jié)構(gòu)1:先執(zhí)行插入操作,再執(zhí)行變化操作。⑤組合結(jié)構(gòu)2:先執(zhí)行交換操作,再執(zhí)行變化操作。

    在MDABC算法的第二階段,兩個解之間需要執(zhí)行協(xié)同操作。對于車間調(diào)度問題,交叉算子具有良好的性能,能夠在保證遺傳優(yōu)良信息的基礎(chǔ)上,同時又有一定的全局搜索性。對于組合優(yōu)化問題,應(yīng)用廣泛的交叉算子有部分映射交叉(Partial Mapped Crossover,PMX)、順序交叉(Order Crossover,OX)、基于位置交叉(Position-based Crossover,PBX)、基于順序交叉(Order-Based Crossover,OBX)、循環(huán)交叉(Cycle Crossover,CX)和子環(huán)交換交叉(Subtour Exchange Crossover,SEX)。針對解編碼中的批次序列向量,圖5展示了上述交叉算子的示意圖。而對于批次分割矩陣,由于受固定批量大小的約束,上述交叉算子可能會產(chǎn)生不可行解。因此,為了能夠?qū)崿F(xiàn)信息共享,促進(jìn)它們之間的協(xié)作,本文引入了矩陣選取操作[13],如圖6所示。具體來說,當(dāng)確定一個批次在分割信息時,其在每一階段的批次分割,以一定的概率從兩個父解中的批次分割矩陣中選取(以下稱為選取概率)。從批次1到批次n,依次采取上述操作,確定完整的批次分割信息。

    2.6 自動算法配置問題

    本節(jié)給出自動算法配置問題,其形式化定義由BIRATTARI[16]給出。在配置問題中,存在4個可配置的數(shù)值參數(shù)和4個可配置的類別參數(shù)。數(shù)值參數(shù)包括交換解前連續(xù)不成功的代數(shù)、每個子問題鄰近子問題的數(shù)量、子問題的數(shù)量,以及選取概率。分類參數(shù)包括初始化方法、解碼策略、聚集方法,以及批次序列的交互方法。表3列出了可配置參數(shù)及其分布。

    表3 可配置參數(shù)及其分布

    由表3可知,在構(gòu)建自動MOEA的過程中,有8個可配置的參數(shù),標(biāo)記為Xd,d=1,…,8。這些參數(shù)取值范圍不同,其取值需要從相應(yīng)的參數(shù)取值空間中采樣。假設(shè)θ={x1,…,xd,…,xNparam}定義了一種算法配置,其中xd表示參數(shù)Xd的取值,同時假設(shè)Θ為所有的算法配置集合。當(dāng)考慮使用I/F-Race來構(gòu)建自動算法時,需要測試一組測試算例。設(shè)置c(θ)表示算法配置θ在測試算例集上的預(yù)期代價值。I/F-Race旨在找到具有最小代價值c(θ*)的最優(yōu)算法配置θ*。

    2.7 自動算法設(shè)計方法

    I/F-Race作為一種機(jī)器學(xué)習(xí)方法,首次被應(yīng)用于處理模型選擇問題[15],該方法包含多個F-Race流程。I/F-Race從一組有限的候選算法配置開始,在一組測試算例上進(jìn)行測試。一個F-Race流程包含幾個迭代步驟。在每個步驟中,候選配置將在單個測試算例上進(jìn)行評估。在每個步驟之后,將那些在數(shù)理統(tǒng)計上比至少一個算法配置表現(xiàn)差的候選配置拋棄掉,剩下的算法配置將繼續(xù)進(jìn)行評估。為求解MOHFSP_VS,本文采用文獻(xiàn)[13]所設(shè)計的F-Race的流程。算法1給出了I/F-Race算法流程,其中Race()表示F-Race流程。I/F-Race主要包括3個步驟:①根據(jù)給定的分布抽樣新配置;②從新抽樣的配置中選擇最佳配置;③更新抽樣分布使抽樣偏向于最佳配置。具體流程見文獻(xiàn)[16]。

    算法1I/F-Race流程。

    輸入:I={I1,…,Ii,…IG}

    參數(shù)空間:X={X1,…,X9}

    總預(yù)算成本:B

    1:Θk~SampleUniform(X)

    2:Θelite:=Race(Θ1,B1)

    3:j:=j+1

    4:WhileBused≤Bdo

    5: Θnew~Sample(X,Θelite)

    6: Θj=Θnew∪Θelite

    7: Θelite:=Race(Θj,Bj)

    8:j:=j+1

    9: EndWhile

    輸出:Θelite

    3 實驗設(shè)計

    本章通過與其他4種高性能的MOEAs以及CPLEX進(jìn)行比較,驗證自動算法的有效性。對于MOEAs來說,在可接受的時間內(nèi)獲得滿意解具有重要的實際意義,因此本文以運行時間作為算法終止準(zhǔn)則,運行時間設(shè)置為n×m×tms,其中n為批次的數(shù)量,m為階段數(shù),t為一固定值。這種終止準(zhǔn)則能夠為規(guī)模大的測試算例提供更多的計算時間。本文中,t設(shè)置為200,在這種時間限制下,本文所比較的算法在大多數(shù)情況下都能夠收斂。所有比較的MOEAs均采用C++語言編寫,仿真實驗運行在3.60 GHZ Intel Core i7處理器上。

    3.1 測試數(shù)據(jù)和性能指標(biāo)

    本文收集了15個小規(guī)模算例和400個中大規(guī)模算例,每個測試算例用批次數(shù)量、階段數(shù)和機(jī)器布局來標(biāo)識。小規(guī)模算例中,批次數(shù)量n來自集合{3,5,8,10,12},階段數(shù)m來自集合{2,3,4}。這樣,通過組合n和m,可得到15種不同的n×m。中大規(guī)模算例中,批次數(shù)量n來自集合{20,40,60,80,100},階段數(shù)m來自集合{3,5,8,10}。通過組合n和m,將得到20種不同的n×m。關(guān)于機(jī)器布局,本文采用了4種不同的類型,如下所示:

    (1)第一階段具有一臺機(jī)器,其他階段具有3臺機(jī)器。

    (2)第二階段具有一臺機(jī)器,其他階段具有3臺機(jī)器。

    (3)第二階段具有兩臺機(jī)器,其他階段具有3臺機(jī)器。

    (4)所有階段具有3臺機(jī)器。

    在中大規(guī)模算例中,通過組合4種不同機(jī)器布局的類型,會產(chǎn)生80種組合。對于每個組合,本文將隨機(jī)生成5個測試算例,總共可以獲得400個測試算例。在小規(guī)模算例中,為了直觀地反映CPLEX和MOEAs的性能隨問題規(guī)模增加而發(fā)生的變化,只組合類型(4),對于每種組合,隨機(jī)產(chǎn)生一個測試算例,總共得到15個測試算例。關(guān)于生產(chǎn)數(shù)據(jù)的生成,給出如下合理范圍:每個批次的加工單元數(shù)量取自均勻分布U[50,100],加工單元的加工時間取自均勻分布U[1,10],啟動時間和運輸時間分別由均勻分布U[50, 100]和U[10, 20]得出。另外,最大子批數(shù)量設(shè)置為30。

    本文選擇C-metric和D-metric兩個性能指標(biāo)[13]來評價MOEAs的性能。為了消除目標(biāo)值不同量綱的影響,在度量中采用歸一化處理。

    3.2 算法調(diào)優(yōu)階段

    為了進(jìn)行全局的調(diào)優(yōu)以確定最佳算法配置,從400個中大規(guī)模算例中隨機(jī)選擇100個具有不同問題規(guī)模的算例作為I/F-Race的測試算例。這100個算例構(gòu)成了算法1中的測試集合I={I1,…,Ii,…IG},它們的順序是隨機(jī)打亂的。本文將預(yù)算成本設(shè)置為實驗的數(shù)量,一次實驗是指利用一種算法配置求解一個測試算例??傤A(yù)算成本B設(shè)為2000,每次F-Race流程中候選配置的最小保留數(shù)目設(shè)為10。表4給出了I/F-Race算法執(zhí)行優(yōu)化的過程數(shù)據(jù)。

    表4 I/F-Race中產(chǎn)生的過程數(shù)據(jù)

    從表4可以看出,共存在5個迭代過程。隨著迭代數(shù)的增加,每代的預(yù)算成本逐漸增加。同時,迭代1用到了一個測試算例,迭代2、3、4、5分別用到了2、3、3、4個測試算例。這意味著在迭代初期,精英配置和劣質(zhì)配置比較容易識別,而在迭代后期,每個候選配置將需要更加細(xì)致地評估。這背后的原因是,在后續(xù)的迭代中生成的候選配置較為相似,因此需要更多的評估成本進(jìn)行識別。

    在測試了13個實例后,I/F-Race輸出了10個精英配置,如表5所示。從表5可以看出,每個配置都不同于其他配置。這意味著高性能算法可以通過配置不同的參數(shù)值組合來構(gòu)造。對于數(shù)值參數(shù)X1,10個精英配置的取值均大于1,這也證明了MDABC算法中重啟策略的有效性。對于數(shù)值參數(shù)X4,可以看出,在10個精英配置中,有9個配置取值大于0.5,這說明在執(zhí)行交互操作的時候,選擇優(yōu)良解中的信息更有利于尋優(yōu)。對于類別參數(shù)X5,可以看出,所有配置都選擇了RI來初始化批次分割矩陣,這證明RI表現(xiàn)明顯優(yōu)于其他兩種方法。在初始化批次排列時,9個精英配置選擇了RI來進(jìn)行初始化,只有一種配置選擇了VSPT,從而說明了RI方法的有效性。對于類別參數(shù)X6,所有精英配置均使用FA策略來選擇機(jī)器,這說明FA比FC更適合解決本文問題。所有配置使用SP策略來執(zhí)行批次排序,這是因為SP比LP更好地利用了批量流的特性。對于類別參數(shù)X7,所有算法配置均采用了加權(quán)和方法,同時均使用了目標(biāo)歸一化。這證明了加權(quán)和方法以及目標(biāo)歸一化為更加適合MOHFSP_VS的適應(yīng)度值評估方法。對于類別參數(shù)X8,10種精英配置中,出現(xiàn)了5個配置選擇了PBX,3個配置選擇了OBX,而TPX和CX各被1個配置選中。在接下來的算法測試階段,將使用最優(yōu)的算法配置來構(gòu)造自動算法求解MOHFSP_VS,即X1=21,X2=10,X3=245,X4=0.7,X5=RI_RI,X6=FA_SP,X7=WS_USE,X8=PBX。

    表5 輸出的10個精英配置

    3.3 算法測試階段

    為了評估由AAD自動構(gòu)建的MOEA的性能,將其與現(xiàn)有文獻(xiàn)中的4種MOEAs進(jìn)行比較,分別是MOCGWO[26]、MOEA/D[24]、PHMOEA/D[27]和NSGA-II[28]。選擇它們作為比較對象的原因如下:①MOEA/D和NSGA-II是解決多目標(biāo)調(diào)度問題和其他各種多目標(biāo)優(yōu)化問題的著名算法框架;②MOCGWO和PHMOEA/D已被證明在解決多目標(biāo)HFSPs時性能是優(yōu)異的,另外它們采用的解編碼都是兩層的,適合MOHFSP_VS的求解。本文也對比較算法中的參數(shù)進(jìn)行了適當(dāng)?shù)脑O(shè)置。對于PHMOEA/D中的數(shù)值參數(shù),本文采用文獻(xiàn)中所建議的田口法[25]進(jìn)行設(shè)置。對于MOCGWO、MOEA/D和NSGA-II中的數(shù)值參數(shù),在對應(yīng)的文獻(xiàn)中沒有找到具體的配置方法。因此,首先確定其數(shù)值參數(shù)的合理取值范圍,然后通過田口法進(jìn)行配置。對于比較算法中的類別參數(shù),為了進(jìn)行公平的比較,所有比較算法都采用了本文所提出的編碼方案。在此基礎(chǔ)上,對于其他的類別參數(shù),即初始化方法、解碼策略、聚集函數(shù)方法、目標(biāo)歸一化以及交叉算子,則根據(jù)表5輸出的最佳配置中出現(xiàn)的大多數(shù)進(jìn)行設(shè)置。

    3.3.1 MOEAs算法與CPLEX在小規(guī)模數(shù)據(jù)集上的對比分析

    對于每個算例,分配20個均勻分布的權(quán)重,CPLEX通過對兩個目標(biāo)線性加權(quán)的方式獨立運行20次,每次運行的時間限制設(shè)置為3 600 s。通過收集20次運行的解,得到一組非支配解。對于MOEAs,針對每個測試算例,獨立運行5次,每次運行時間設(shè)置為n×m×200 ms。表6和表7分別展示了基于C-metric和D-metric指標(biāo)的平均值(AVG)和標(biāo)準(zhǔn)差(SD)。此外,表7中還展示了MOEAs和CPLEX求解每個算例的運行時間。

    對比AAD算法和CPLEX,基于C-metric指標(biāo),從表6可以看出,CPLEX在問題3×2和3×3上取得了較大的C-metric均值,但隨著問題規(guī)模的增加,AAD算法在其他所有問題上均取得了更大的C-metric均值。對比于CPLEX的0.056,AAD算法取得了明顯大的總體平均值0.430。基于D-metric指標(biāo),從表7中可以看出,AAD算法在問題3×3上取得了更小的D-metric均值,這說明AAD算法在3×3問題上得到的Pareto解在解集上分布更加均勻。除了問題3×2,AAD算法在其他問題上均取得了更小的D-metric均值,并取得了更小的總體平均值0.107。此外,從表7中可以看出,隨著批次和階段數(shù)量的增加,由于問題的NP難特性,從問題5×2開始,所有權(quán)重下,CPLEX在3 600 s的運行時間內(nèi)都不能獲得最優(yōu)解。同時,MOEAs的運行時間遠(yuǎn)小于CPLEX。通過這些觀察,可以得出結(jié)論,利用CPLEX求解混合整數(shù)規(guī)劃模型很難得到包含所有最優(yōu)Pareto解的Pareto解集。此外,CPLEX的運行時間是難以接受的。綜上所述,對比于傳統(tǒng)的數(shù)學(xué)規(guī)劃求解方法,MOEAs的優(yōu)越性是可以得到體現(xiàn)的。與其他MOEAs相比,基于C-metric,AAD算法在所有問題上均可以取得較大的均值。在所有問題上,根據(jù)C-metric結(jié)果,MOEA/D、PHMOEA/D和NSGA-II這3種算法所獲得的Pareto解全部可以被AAD算法得到的Pareto解所支配?;贒-metric的均值,AAD算法同樣在所有問題上表現(xiàn)最好。由此說明,AAD算法在小規(guī)模測試算例上取得的Pareto解集具有良好的收斂性和高效性。通過與CPLEX和其他MOEAs的對比,在小規(guī)模數(shù)據(jù)集上,AAD算法的高效性和優(yōu)越性是可以得到驗證的。

    表6 小規(guī)模數(shù)據(jù)集上C-metric AVG(SD)值對比

    表7 小規(guī)模數(shù)據(jù)集上D-metric AVG(SD)值對比

    3.3.2 MOEAs算法在中大規(guī)模數(shù)據(jù)集上的對比分析

    對于中大規(guī)模數(shù)據(jù)集上的每個測試算例,分別計算得到C-metric和D-metric的平均值和標(biāo)準(zhǔn)差。然后在相同的問題規(guī)模下,再次進(jìn)行平均,結(jié)果統(tǒng)計在表8和表9中。此外,為了驗證C-metric和D-metric結(jié)果的統(tǒng)計有效性,采用單因素方差分析(ANOVA)對平均值進(jìn)行分析。圖7和圖8分別顯示了在95%置信水平上C-metric和D-metric結(jié)果的Tukey HSD區(qū)間圖。在區(qū)間圖中,若兩種算法之間沒有重疊,則它們之間存在統(tǒng)計意義上的顯著差異。

    根據(jù)表8中展示的C-metric結(jié)果可以看出,對于所有的15個問題,AAD相對于其他任何算法得到的C-metric均值都是最大的,并且所獲得的總體平均值遠(yuǎn)遠(yuǎn)大于其他算法。該結(jié)果意味著,AAD算法獲得的Pareto解中有很少一部分會被其他算法的Pareto解所支配,而其他算法獲得的Pareto解中大部分會被AAD算法所獲得的Pareto解所支配。由此證明AAD算法的收斂性在所有MOEAs中是最好的。從圖7中可以看出,基于C-metric均值數(shù)據(jù),AAD算法在數(shù)理統(tǒng)計上明顯優(yōu)于其他4種算法。對于C-metric標(biāo)準(zhǔn)差,可以看出AAD算法得到的值總是大于其他算法得到的值。這是因為其他算法得到的Pareto解很難支配AAD所取得的Pareto解。因此,其他算法得到的C-metric標(biāo)準(zhǔn)差值總是比AAD算法小?;贒-metric比較,從表9中可以看出,AAD的總體平均值(0.093)遠(yuǎn)小于MOCGWO(0.317)、MOEA/D(0.648)、PHMOEA/D(0.842)和NSGA-II(0.282)。由圖8可以看到,根據(jù)顯著性分析結(jié)果,AAD再次明顯優(yōu)于其他4種算法。由此證明AAD取得的Pareto解集不但具有最好的收斂性,而且解集的分布性也是最好的,所得的Pareto解集更加逼近真實的Pareto前沿。從D-metric標(biāo)準(zhǔn)差值來看,AAD算法對于大多數(shù)問題是能夠得到最小值的,這可以說明AAD算法具有良好的魯棒性。為了更加直觀、清晰地展示它們的性能,圖9展示了所有算法針對4個不同問題規(guī)模測試算例得到的Pareto解集。圖9顯示AAD算法的確可以得到質(zhì)量更好且分布更加均勻的Pareto解,這與數(shù)值分析所得的結(jié)論是一致的。綜上所述,AAD算法在解決MOHFSP_VS時的性能是優(yōu)越且高效的。

    表8 中大規(guī)模數(shù)據(jù)集上C-metric AVG(SD)值對比

    表9 中大規(guī)模數(shù)據(jù)集上D-metric AVG(SD)值對比

    4 結(jié)束語

    考慮變分批技術(shù),本文研究了以最小化最大完工時間和子批總數(shù)為目標(biāo)的MOHFSP_VS,并考慮了啟動和運輸操作。建立了一個多目標(biāo)混合整數(shù)規(guī)劃模型,并通過求解CPLEX模型來評估兩個目標(biāo)間的權(quán)衡關(guān)系。為了求解該一問題,本文在MDABC算法框架的基礎(chǔ)上,引入了AAD方法來自動構(gòu)造高性能的MOEA。針對問題特性,提出了動態(tài)解碼策略;針對具體問題特征和算法框架,對于可配置類別和數(shù)值參數(shù),給出了合理的取值區(qū)間;對于AAD方法,采用了I/F-Race方法;最后,通過實驗證明,自動生成的MOEA表現(xiàn)是非常突出的。

    對于MOHFSP_VS,未來的研究包括:①設(shè)計更高效的編碼和解碼策略;②基于問題特性開發(fā)啟發(fā)式規(guī)則進(jìn)一步改進(jìn)結(jié)果;③評估一些其他目標(biāo)(例如總流經(jīng)時間,總提前和延遲時間,和機(jī)器利用率等);④考慮車間動態(tài)事件的影響,研究動態(tài)和重調(diào)度策略。對于AAD方法,筆者將嘗試將算法框架視為一個可配置參數(shù),則具體參數(shù)將隸屬于算法框架,重新定義算法配置問題和I/F-Race流程。

    猜你喜歡
    算例機(jī)器調(diào)度
    機(jī)器狗
    機(jī)器狗
    《調(diào)度集中系統(tǒng)(CTC)/列車調(diào)度指揮系統(tǒng)(TDCS)維護(hù)手冊》正式出版
    一種基于負(fù)載均衡的Kubernetes調(diào)度改進(jìn)算法
    虛擬機(jī)實時遷移調(diào)度算法
    未來機(jī)器城
    電影(2018年8期)2018-09-21 08:00:06
    基于振蕩能量的低頻振蕩分析與振蕩源定位(二)振蕩源定位方法與算例
    互補(bǔ)問題算例分析
    無敵機(jī)器蛛
    基于CYMDIST的配電網(wǎng)運行優(yōu)化技術(shù)及算例分析
    国产精品国产高清国产av| 久99久视频精品免费| 欧美成人一区二区免费高清观看| 午夜福利在线观看吧| 十八禁人妻一区二区| 性色avwww在线观看| 亚洲精华国产精华精| 精品久久久久久久末码| 欧美xxxx黑人xx丫x性爽| 国产成人欧美在线观看| 在线国产一区二区在线| 国产男靠女视频免费网站| 国产成年人精品一区二区| 日韩欧美精品免费久久 | 成人三级黄色视频| а√天堂www在线а√下载| 日本撒尿小便嘘嘘汇集6| 亚洲三级黄色毛片| 天天一区二区日本电影三级| 亚洲av一区综合| 757午夜福利合集在线观看| 欧美+日韩+精品| 天堂网av新在线| 中文字幕久久专区| 国产亚洲精品av在线| 一本综合久久免费| 黄色日韩在线| 国产精品一区二区性色av| 欧美日本亚洲视频在线播放| 18禁黄网站禁片免费观看直播| 午夜a级毛片| 十八禁网站免费在线| 噜噜噜噜噜久久久久久91| 我要搜黄色片| 免费大片18禁| 欧美xxxx黑人xx丫x性爽| 午夜激情福利司机影院| 国产一区二区三区在线臀色熟女| 婷婷色综合大香蕉| 欧美在线黄色| 国产精品一及| 麻豆国产av国片精品| 国产在线精品亚洲第一网站| 三级国产精品欧美在线观看| 国产一区二区在线av高清观看| 麻豆国产av国片精品| 脱女人内裤的视频| 日本免费一区二区三区高清不卡| 亚洲国产欧美人成| 美女高潮的动态| 91狼人影院| 午夜影院日韩av| 国产一区二区三区在线臀色熟女| 桃色一区二区三区在线观看| 国内精品一区二区在线观看| 亚洲片人在线观看| 一本一本综合久久| 免费观看精品视频网站| 人人妻,人人澡人人爽秒播| 亚洲av日韩精品久久久久久密| 国产美女午夜福利| 在线国产一区二区在线| 国产av在哪里看| 乱人视频在线观看| 一级av片app| 欧美激情国产日韩精品一区| 久久婷婷人人爽人人干人人爱| 色播亚洲综合网| 一卡2卡三卡四卡精品乱码亚洲| 757午夜福利合集在线观看| 3wmmmm亚洲av在线观看| 免费人成视频x8x8入口观看| 亚洲国产精品久久男人天堂| 中文亚洲av片在线观看爽| 精品乱码久久久久久99久播| 日韩有码中文字幕| 在线国产一区二区在线| av欧美777| 欧美黑人巨大hd| 直男gayav资源| 欧美区成人在线视频| 亚洲激情在线av| 亚洲欧美清纯卡通| 在线国产一区二区在线| 欧美bdsm另类| 一本一本综合久久| 成人永久免费在线观看视频| avwww免费| 亚洲精华国产精华精| 精品人妻一区二区三区麻豆 | 国产欧美日韩一区二区精品| 国产熟女xx| 日韩欧美精品v在线| 搡老妇女老女人老熟妇| 国产大屁股一区二区在线视频| 午夜两性在线视频| 精品久久国产蜜桃| 免费在线观看成人毛片| 欧美精品啪啪一区二区三区| 国产主播在线观看一区二区| 亚洲欧美日韩高清专用| 9191精品国产免费久久| 少妇被粗大猛烈的视频| 成年人黄色毛片网站| 脱女人内裤的视频| 少妇人妻一区二区三区视频| 在线观看午夜福利视频| 美女被艹到高潮喷水动态| 久久久久亚洲av毛片大全| 日韩欧美免费精品| 中文字幕人妻熟人妻熟丝袜美| 成年女人看的毛片在线观看| 偷拍熟女少妇极品色| 蜜桃亚洲精品一区二区三区| 白带黄色成豆腐渣| 有码 亚洲区| 免费在线观看亚洲国产| 人妻制服诱惑在线中文字幕| 久久中文看片网| 久久久国产成人免费| 9191精品国产免费久久| 色综合亚洲欧美另类图片| 丝袜美腿在线中文| 免费在线观看日本一区| 国产午夜精品久久久久久一区二区三区 | 可以在线观看的亚洲视频| 成人精品一区二区免费| 久久这里只有精品中国| 国产人妻一区二区三区在| 免费av观看视频| 精品人妻视频免费看| 亚洲黑人精品在线| 国产精品一区二区免费欧美| 免费看a级黄色片| 免费搜索国产男女视频| 国内精品久久久久精免费| 久久久久亚洲av毛片大全| 亚洲七黄色美女视频| 亚洲久久久久久中文字幕| 全区人妻精品视频| 日韩欧美免费精品| 欧美一级a爱片免费观看看| 欧美+亚洲+日韩+国产| 国产伦人伦偷精品视频| 精品人妻一区二区三区麻豆 | 97超级碰碰碰精品色视频在线观看| 长腿黑丝高跟| 免费无遮挡裸体视频| 亚洲精品在线观看二区| 久久99热这里只有精品18| 嫩草影院精品99| 欧美乱妇无乱码| 丰满人妻熟妇乱又伦精品不卡| 欧美乱色亚洲激情| 欧美日韩综合久久久久久 | 少妇熟女aⅴ在线视频| 国产野战对白在线观看| 久久久久久大精品| 色尼玛亚洲综合影院| 日本黄大片高清| 久久久久久大精品| 又爽又黄a免费视频| 老熟妇仑乱视频hdxx| 国产伦人伦偷精品视频| 成人美女网站在线观看视频| 18禁黄网站禁片免费观看直播| 97热精品久久久久久| 国产av麻豆久久久久久久| 日韩成人在线观看一区二区三区| 男人和女人高潮做爰伦理| 国产在线男女| 久久婷婷人人爽人人干人人爱| 一级作爱视频免费观看| 亚洲va日本ⅴa欧美va伊人久久| 丰满人妻一区二区三区视频av| 亚洲人与动物交配视频| 日本成人三级电影网站| 亚洲av日韩精品久久久久久密| 老司机福利观看| 日本黄色视频三级网站网址| 嫩草影院新地址| 国产高清三级在线| 搡老岳熟女国产| 国产亚洲av嫩草精品影院| 赤兔流量卡办理| avwww免费| 99在线视频只有这里精品首页| 国产精品亚洲美女久久久| 亚洲综合色惰| 午夜激情欧美在线| 亚洲精品在线美女| 亚洲国产精品成人综合色| 亚洲在线观看片| 久久人人精品亚洲av| 久久午夜福利片| 真人做人爱边吃奶动态| 在线免费观看的www视频| 久久久久性生活片| 精品一区二区三区视频在线观看免费| 91久久精品国产一区二区成人| 国产色婷婷99| 黄色女人牲交| 老司机午夜十八禁免费视频| 亚洲经典国产精华液单 | 在线十欧美十亚洲十日本专区| 国产91精品成人一区二区三区| 非洲黑人性xxxx精品又粗又长| 国产精品98久久久久久宅男小说| 久久久久久国产a免费观看| 校园春色视频在线观看| 在线观看av片永久免费下载| 18禁裸乳无遮挡免费网站照片| 成人精品一区二区免费| 亚洲18禁久久av| 国产精品伦人一区二区| 91午夜精品亚洲一区二区三区 | 黄色丝袜av网址大全| 日韩欧美国产一区二区入口| 高清毛片免费观看视频网站| 少妇熟女aⅴ在线视频| 国产av不卡久久| 精品日产1卡2卡| 精品一区二区三区人妻视频| 亚洲av熟女| 国产精品电影一区二区三区| 丰满人妻一区二区三区视频av| 成人鲁丝片一二三区免费| 国产极品精品免费视频能看的| 男女之事视频高清在线观看| 国产亚洲精品综合一区在线观看| 欧美精品国产亚洲| 乱码一卡2卡4卡精品| 国产精品久久久久久亚洲av鲁大| 18禁裸乳无遮挡免费网站照片| 99精品在免费线老司机午夜| 亚洲一区二区三区色噜噜| 日本免费a在线| 色视频www国产| 熟妇人妻久久中文字幕3abv| 露出奶头的视频| 尤物成人国产欧美一区二区三区| av在线观看视频网站免费| 欧美成人一区二区免费高清观看| 日韩精品中文字幕看吧| 综合色av麻豆| 人妻丰满熟妇av一区二区三区| 亚洲自拍偷在线| 亚洲五月婷婷丁香| 亚洲av五月六月丁香网| 天美传媒精品一区二区| 午夜日韩欧美国产| 国产三级黄色录像| 日本一本二区三区精品| 丁香欧美五月| 欧美3d第一页| 神马国产精品三级电影在线观看| 99在线视频只有这里精品首页| 日韩精品中文字幕看吧| 舔av片在线| 亚洲av成人精品一区久久| 自拍偷自拍亚洲精品老妇| 精品欧美国产一区二区三| 99国产精品一区二区三区| 国产一区二区激情短视频| 蜜桃久久精品国产亚洲av| 日韩精品青青久久久久久| 免费观看的影片在线观看| 一个人看视频在线观看www免费| 久久人人爽人人爽人人片va | 国产野战对白在线观看| 给我免费播放毛片高清在线观看| 99国产精品一区二区三区| 久久久久久久午夜电影| 啦啦啦观看免费观看视频高清| 午夜福利欧美成人| 国产日本99.免费观看| 麻豆久久精品国产亚洲av| 欧美zozozo另类| 亚洲中文日韩欧美视频| 长腿黑丝高跟| 天堂网av新在线| 热99在线观看视频| 男人狂女人下面高潮的视频| 午夜福利高清视频| 国产成人影院久久av| 日日摸夜夜添夜夜添av毛片 | 熟女人妻精品中文字幕| 亚洲人成网站在线播放欧美日韩| 女人十人毛片免费观看3o分钟| 欧美最黄视频在线播放免费| 欧美在线黄色| 午夜老司机福利剧场| 日本一本二区三区精品| 真实男女啪啪啪动态图| 九九在线视频观看精品| 香蕉av资源在线| 最近最新免费中文字幕在线| 精品午夜福利视频在线观看一区| 国产伦一二天堂av在线观看| 欧美在线黄色| 亚洲精品影视一区二区三区av| 午夜久久久久精精品| 欧美三级亚洲精品| 国产三级黄色录像| 国产中年淑女户外野战色| 中文资源天堂在线| 美女大奶头视频| 日本 欧美在线| 国产av麻豆久久久久久久| 国产一区二区在线观看日韩| 女人被狂操c到高潮| 日韩人妻高清精品专区| 精品人妻熟女av久视频| 99视频精品全部免费 在线| 岛国在线免费视频观看| 日韩国内少妇激情av| 国产一区二区在线av高清观看| 日本一本二区三区精品| 色吧在线观看| 国产成人啪精品午夜网站| 亚洲乱码一区二区免费版| 午夜激情福利司机影院| 我的老师免费观看完整版| 日韩高清综合在线| 三级男女做爰猛烈吃奶摸视频| 欧美激情在线99| 日日摸夜夜添夜夜添av毛片 | 精品一区二区三区视频在线| 精品一区二区三区视频在线观看免费| 毛片女人毛片| 中文亚洲av片在线观看爽| 国产精品久久久久久人妻精品电影| 国产午夜精品论理片| 琪琪午夜伦伦电影理论片6080| 精品一区二区三区av网在线观看| 美女高潮喷水抽搐中文字幕| 夜夜躁狠狠躁天天躁| 色综合亚洲欧美另类图片| 亚洲av不卡在线观看| 久久国产乱子免费精品| 女人被狂操c到高潮| 此物有八面人人有两片| 午夜激情福利司机影院| 免费看a级黄色片| 欧美xxxx性猛交bbbb| 一进一出抽搐gif免费好疼| 亚洲最大成人手机在线| 国内精品美女久久久久久| 日本一二三区视频观看| 亚洲精品在线美女| 国产亚洲av嫩草精品影院| 熟女电影av网| 99riav亚洲国产免费| 国产精品1区2区在线观看.| 两个人视频免费观看高清| 免费看光身美女| 偷拍熟女少妇极品色| 9191精品国产免费久久| 免费观看人在逋| 9191精品国产免费久久| 俄罗斯特黄特色一大片| 欧美日韩国产亚洲二区| 亚洲七黄色美女视频| 欧美+日韩+精品| 免费大片18禁| 日本熟妇午夜| 亚洲欧美日韩卡通动漫| .国产精品久久| 99久久无色码亚洲精品果冻| 在线观看66精品国产| 亚洲黑人精品在线| 黄色日韩在线| 国产亚洲av嫩草精品影院| 午夜两性在线视频| 欧美乱妇无乱码| 三级国产精品欧美在线观看| 麻豆成人午夜福利视频| ponron亚洲| bbb黄色大片| av在线蜜桃| 美女cb高潮喷水在线观看| 欧美三级亚洲精品| 久9热在线精品视频| 国产精品久久久久久久电影| 欧美乱妇无乱码| 亚洲精品在线美女| 久久久色成人| 日韩人妻高清精品专区| 亚洲成a人片在线一区二区| 日韩欧美国产一区二区入口| 麻豆av噜噜一区二区三区| 精品人妻视频免费看| 久久久国产成人精品二区| 自拍偷自拍亚洲精品老妇| 性欧美人与动物交配| 日韩成人在线观看一区二区三区| 精品久久久久久成人av| 日韩欧美一区二区三区在线观看| 亚洲av成人精品一区久久| 欧美黑人欧美精品刺激| 丁香六月欧美| 露出奶头的视频| 好看av亚洲va欧美ⅴa在| 欧美性感艳星| 熟妇人妻久久中文字幕3abv| 69人妻影院| 成人高潮视频无遮挡免费网站| 欧美成人性av电影在线观看| 国产精品98久久久久久宅男小说| 毛片女人毛片| 日韩免费av在线播放| bbb黄色大片| 亚洲av成人不卡在线观看播放网| 成人鲁丝片一二三区免费| 国产真实伦视频高清在线观看 | 成人高潮视频无遮挡免费网站| 亚洲av熟女| 国产乱人伦免费视频| 色精品久久人妻99蜜桃| 永久网站在线| 亚洲成人久久爱视频| 久久久久亚洲av毛片大全| 日本黄色片子视频| 国产高清激情床上av| 亚洲第一电影网av| 日本精品一区二区三区蜜桃| 国产欧美日韩精品一区二区| 俄罗斯特黄特色一大片| 欧美激情久久久久久爽电影| 男插女下体视频免费在线播放| 欧美日韩黄片免| 欧美xxxx性猛交bbbb| 亚洲真实伦在线观看| 欧美中文日本在线观看视频| 国产蜜桃级精品一区二区三区| 乱码一卡2卡4卡精品| 五月玫瑰六月丁香| 在线国产一区二区在线| 日本a在线网址| 日韩精品中文字幕看吧| 国产亚洲精品久久久com| 1000部很黄的大片| aaaaa片日本免费| 美女大奶头视频| 色综合欧美亚洲国产小说| 精品久久久久久久久亚洲 | 老熟妇乱子伦视频在线观看| 97热精品久久久久久| 国产精品1区2区在线观看.| 男人的好看免费观看在线视频| 成人毛片a级毛片在线播放| 熟女人妻精品中文字幕| 亚洲精品一区av在线观看| 日韩亚洲欧美综合| 夜夜看夜夜爽夜夜摸| 一本一本综合久久| 波多野结衣高清无吗| 免费看日本二区| 少妇被粗大猛烈的视频| 九色国产91popny在线| 国产精品日韩av在线免费观看| 午夜日韩欧美国产| 少妇裸体淫交视频免费看高清| 国语自产精品视频在线第100页| 欧美成人a在线观看| 搡老妇女老女人老熟妇| 欧美激情国产日韩精品一区| 亚洲黑人精品在线| 欧美激情久久久久久爽电影| 舔av片在线| 99久久精品一区二区三区| av福利片在线观看| 一级毛片久久久久久久久女| 国产成人a区在线观看| 国产精品一及| 国产久久久一区二区三区| 2021天堂中文幕一二区在线观| 亚洲最大成人手机在线| 特级一级黄色大片| 久久精品影院6| 精品久久久久久成人av| 此物有八面人人有两片| 成人无遮挡网站| 久久久久国产精品人妻aⅴ院| 少妇裸体淫交视频免费看高清| 中文字幕av在线有码专区| 日本精品一区二区三区蜜桃| 国产亚洲欧美98| 中文亚洲av片在线观看爽| 一区二区三区四区激情视频 | 日韩中文字幕欧美一区二区| 中亚洲国语对白在线视频| 天天一区二区日本电影三级| 深爱激情五月婷婷| 韩国av一区二区三区四区| 九九热线精品视视频播放| 在线播放无遮挡| 99国产精品一区二区蜜桃av| 日本黄大片高清| 亚洲一区高清亚洲精品| 丰满的人妻完整版| 看免费av毛片| 51午夜福利影视在线观看| 九九在线视频观看精品| 在线看三级毛片| 久久亚洲精品不卡| 国内精品久久久久精免费| 露出奶头的视频| 亚洲va日本ⅴa欧美va伊人久久| 久久久久国内视频| 在线观看av片永久免费下载| 男人狂女人下面高潮的视频| 免费电影在线观看免费观看| 91九色精品人成在线观看| 18禁在线播放成人免费| 日韩国内少妇激情av| 毛片女人毛片| 国产av在哪里看| 中文字幕人妻熟人妻熟丝袜美| 亚洲国产欧美人成| 欧美一级a爱片免费观看看| 日韩欧美免费精品| 欧美区成人在线视频| 三级毛片av免费| 精品国产三级普通话版| 欧美一级a爱片免费观看看| 午夜亚洲福利在线播放| av福利片在线观看| 久久午夜亚洲精品久久| 久久香蕉精品热| 国产美女午夜福利| 少妇人妻一区二区三区视频| 天堂网av新在线| 欧美性猛交╳xxx乱大交人| 变态另类成人亚洲欧美熟女| 亚洲欧美激情综合另类| 草草在线视频免费看| 小蜜桃在线观看免费完整版高清| 一区二区三区四区激情视频 | 国产中年淑女户外野战色| 五月伊人婷婷丁香| 日日夜夜操网爽| 一夜夜www| 三级国产精品欧美在线观看| 欧美中文日本在线观看视频| 国产免费av片在线观看野外av| 色综合婷婷激情| 男女视频在线观看网站免费| 国产高清视频在线播放一区| 欧洲精品卡2卡3卡4卡5卡区| 亚洲熟妇熟女久久| 看十八女毛片水多多多| 1024手机看黄色片| 亚洲成人中文字幕在线播放| 成人欧美大片| а√天堂www在线а√下载| 12—13女人毛片做爰片一| 男人狂女人下面高潮的视频| 亚洲国产欧洲综合997久久,| 国内精品一区二区在线观看| 最近在线观看免费完整版| 亚洲成人精品中文字幕电影| 国产精品永久免费网站| 国产精品日韩av在线免费观看| 免费av不卡在线播放| 99热6这里只有精品| 色吧在线观看| 中文资源天堂在线| 日本一二三区视频观看| 亚洲成人中文字幕在线播放| 欧美最黄视频在线播放免费| 亚洲国产精品成人综合色| 免费在线观看影片大全网站| 99热这里只有精品一区| 亚洲国产欧美人成| 欧美激情久久久久久爽电影| 国产成人av教育| 男女做爰动态图高潮gif福利片| 中文字幕高清在线视频| 在线观看午夜福利视频| 男人舔奶头视频| av在线老鸭窝| 亚洲av一区综合| 91久久精品电影网| 久久伊人香网站| 最近视频中文字幕2019在线8| 久久国产精品影院| 老司机午夜十八禁免费视频| 亚洲av美国av| 特级一级黄色大片| 午夜精品久久久久久毛片777| 男女做爰动态图高潮gif福利片| 国产av麻豆久久久久久久| 在线观看午夜福利视频| 午夜免费成人在线视频| 高潮久久久久久久久久久不卡| 观看美女的网站| 国产高潮美女av| 又爽又黄a免费视频| 国产精品精品国产色婷婷| 日本黄大片高清| 欧美成人免费av一区二区三区| 九九热线精品视视频播放| 国产亚洲精品久久久久久毛片| 国产精品伦人一区二区| 久久久久久久午夜电影| 网址你懂的国产日韩在线| 国产日本99.免费观看| 丰满人妻一区二区三区视频av| 黄色配什么色好看| 热99re8久久精品国产| 丰满人妻一区二区三区视频av| 免费看光身美女| 麻豆国产av国片精品| 久久久久久久久大av|