資源受限下單批耦合混合流水車間調(diào)度問題研究

唐紅濤，劉子豪，官思佳

(1.武漢理工大學(xué) 機(jī)電工程學(xué)院，湖北 武漢 430070；2.武漢理工大學(xué) 湖北省數(shù)字制造重點(diǎn)實(shí)驗(yàn)室，湖北 武漢 430070；3.航天科工空間工程發(fā)展有限公司，北京 100854)

混合流水車間調(diào)度問題 (hybrid flow shop scheduling problem,HFSP) 是車間調(diào)度領(lǐng)域中基礎(chǔ)且重要的問題[1]，廣泛存在于鑄造[2]、汽車[3]等領(lǐng)域?；旌狭魉囬g中包含多道工序且至少一個工序中包含一臺或多臺并行機(jī)器，同時不同加工階段之間有嚴(yán)格的加工順序約束[4]。在生產(chǎn)制造企業(yè)中，生產(chǎn)制造過程會發(fā)生機(jī)器阻塞[5]、資源受限[6]等動態(tài)事件，實(shí)際生產(chǎn)調(diào)度過程中不僅要考慮工序排序和機(jī)器選擇的問題，還要考慮加工設(shè)備附屬資源的分配等約束問題[7]，因此研究多約束下的混合流水車間調(diào)度問題具有很重要的現(xiàn)實(shí)意義，資源受限的混合流水車間調(diào)度問題 (resource constrained hybrid flow shop scheduling problem,RCHFSP) 正是為解決這一問題而被提出的。

目前，多約束車間調(diào)度問題研究獲得了較大進(jìn)展。Costa等[8]提出一種離散回溯搜索算法求解勞動力有限的混合流水車間調(diào)度問題。唐紅濤等[9]提出一種帝國競爭算法求解砂型鑄造車間中噪音和能耗約束問題。但是這些研究主要集中在機(jī)器柔性和加工約束上，沒有考慮機(jī)器附屬資源的約束問題，如實(shí)際生產(chǎn)中機(jī)加工的刀具、鑄造生產(chǎn)中合箱使用的翻斗機(jī)、熔煉澆筑時需要的除塵機(jī)等資源都有數(shù)量上的約束。崔航浩等[10]建立有機(jī)器準(zhǔn)備時間和附屬資源約束的多資源受限的車間調(diào)度模型，并提出一種多種群粒子群算法解決該問題。Tao等[11]針對最小化完工時間和能源消耗的RCHFSP提出一種改進(jìn)的帝國競爭算法進(jìn)行求解。但是這些研究忽略了實(shí)際生產(chǎn)過程中存在批處理工序的生產(chǎn)情況，沒有對包含批處理的資源受限流水車間調(diào)度進(jìn)行研究。Zhou等[12]設(shè)計(jì)一種自適應(yīng)差分進(jìn)化算法來求解批調(diào)度問題。Li等[13]研究工作惡化的并行批處理分布式流水車間問題。這些研究討論了帶批處理的混合流水車間調(diào)度問題，但沒有考慮附屬資源約束的情況。資源受限下單批耦合混合流水車間是混合流水車間的擴(kuò)展，單批耦合、附屬資源約束增加了調(diào)度問題的求解難度。

因此，本文首次建立以最大完工時間和總能耗為目標(biāo)的資源受限下單批耦合混合流水車間調(diào)度模型，并提出一種改進(jìn)的離散蛙跳算法 (improved shuffled frog leaping algorithm,ISFLA) 對模型進(jìn)行求解，設(shè)計(jì)一種針對資源約束解碼方式，改進(jìn)了一種適用于單批耦合的NEH初始化策略提高算法性能，并設(shè)計(jì)了一種改進(jìn)的模因組搜索策略提高算法的搜索能力，最后通過實(shí)驗(yàn)驗(yàn)證了算法的有效性。

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

1.1 問題描述

資源受限的單批耦合混合流水車間在混合流水車間的基礎(chǔ)上增加了批處理階段與附屬資源約束。包括工序排序、機(jī)器選擇、工件分批和資源分配4個子問題。問題描述為n個工件需要按相同的工藝進(jìn)行s個加工階段，每個階段至少有兩臺并行機(jī)，其中一個階段為批處理階段。前一階段加工完成才能進(jìn)行下一階段的加工。工件可以在后續(xù)階段機(jī)器集合中的任意一臺機(jī)器上加工，且加工開始后不能中斷。工廠有r種資源，包括{R1,R2,…,Rr}。每種類型的資源數(shù)目預(yù)先給出，每道工序開始加工前必須保證機(jī)器可用且資源數(shù)目足夠。模型建立之前作出如下假設(shè)。

1) 機(jī)器在在首個工件到達(dá)后啟動，不加工時處于待機(jī)狀態(tài)，完成最后一個工件加工后停機(jī)；

2) 不同的工件之間沒有加工任務(wù)的優(yōu)先級；

3) 每個工件的工序加工順序不可改變，工件開始加工后不可中斷；

4) 同一個資源在同一時刻只能服務(wù)一臺機(jī)器，除批處理機(jī)外同一機(jī)器同一時刻只能加工一道工序；

5) 資源在機(jī)器開始加工時被占用，加工結(jié)束時進(jìn)行釋放；

6) 批處理過程中不能增加或減少該批次工件數(shù)目；

7) 所有工件在零時刻都可以被加工，所有機(jī)器和資源在零時刻都可以被使用。

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

為建立數(shù)學(xué)模型，定義如下模型參數(shù)、決策變量、目標(biāo)函數(shù)和約束條件。

1) 模型參數(shù)。

參數(shù)設(shè)置見表1。

表1 參數(shù)設(shè)置Table 1 Parameters settings

2) 決策變量。

3) 目標(biāo)函數(shù)。

式(1) 表示最小最大完工時間makespan；式(2)和式(3) 表示總能耗EC，由機(jī)器加工能耗與待機(jī)能耗組成。

4) 約束條件。

式(4) 表示所有工序存在嚴(yán)格的加工順序；式(5) 表示任意一個工序只能與一臺機(jī)器上加工；式(6) 表示每一個工序不能屬于多個批次；式 (7)表示批處理階段的每一個批次總重量為該批次加工工件的重量之和；式 (8) 表示每一個加工的總重量不能超過批處理機(jī)的最大承受重量；式 (9) 表示批處理的最早開工時間不早于該批次中工件的前驅(qū)工序完工時間；式 (10) 表示同一時刻資源的使用量不得超過資源總數(shù)。

2 算法設(shè)計(jì)

蛙跳算法 (shuffled frog leaping algorithm,SFLA)是2003年由Eusuff等[14]提出的一種仿生物學(xué)的智能優(yōu)化算法，具有概念簡單、參數(shù)少、計(jì)算速度快、全局搜索尋優(yōu)能力強(qiáng)、易于實(shí)現(xiàn)等特點(diǎn)。算法的主要步驟包括種群劃分、模因組搜索和種群重構(gòu)。目前，SFLA在車間調(diào)度方面有著廣泛應(yīng)用[15-16]。

2.1 編碼與解碼

對RCHFS問題，本文采用基于機(jī)器選擇與工序排序的雙層整數(shù)編碼方式，以一組向量V=[Vj|Vm]來表示模型的一個解。第1段Vj為工序加工順序編碼，第2段Vm表示該工件對應(yīng)工序可供選擇的機(jī)器集中的機(jī)器順序。解碼是將矢量還原成實(shí)際問題信息的過程，為了提高算法的有效性，本文針對批處理時工件分批和資源分配兩個子問題在解碼過程中通過貪婪選擇進(jìn)行分配。

在解碼過程中，機(jī)器的開始加工時間需要滿足3個條件：1) 工件前驅(qū)工序完成加工；2) 指定的機(jī)器空閑；3) 指定機(jī)器所需的資源足夠。本文在解碼過程中首先針對向量V得到工件加工順序與機(jī)器分配，計(jì)算前驅(qū)工序的完成時間與機(jī)器可用時間，得到最早開工時間，然后計(jì)算資源準(zhǔn)備時間，得到實(shí)際開工時間。因此，Sij+1可以由式(11)計(jì)算得到。

其中，Tm是機(jī)器最小可用時間；TR是資源準(zhǔn)備時間。若資源充足，則資源R將在時間段Sij+1至ETij+1被工序Oij+1占用，并在Oij+1完成后被釋放，否則推遲加工，直至資源充足再加工，此時TR為資源最小等待時間，示例如圖1所示。

圖1 解碼Figure 1 Decoding

批處理階段內(nèi)有批處理機(jī)對工件進(jìn)行組批加工，目前常用的批處理策略有兩種。一種是閾值法，針對不同類型的工件，在未達(dá)到批處理加工閾值的情況下，將不斷完成前驅(qū)工序的工件劃為一個批次，直至到達(dá)批處理機(jī)的加工閾值。另一種為前瞻窗口法，針對前驅(qū)工序的完成時間和批處理機(jī)的加工閾值Q，定義窗口開始時間以及窗口大小。本文針對模型設(shè)計(jì)一種改進(jìn)的前瞻窗口法，開窗時間為首先到達(dá)該批處理機(jī)的工件前驅(qū)工序完工時間，窗口大小為批處理機(jī)器的加工閾值，假設(shè)第j+1道工序?yàn)榕幚砉ば颍琻個工件在批處理工序的前驅(qū)工序完工時間集合為ET={ET1j,ET2j,…,ETnj}，且n個工件的工件重量和達(dá)到批處理機(jī)器加工閾值，則此時在前瞻窗口內(nèi)有n個工件到達(dá)，可以形成n個方案，計(jì)算每個方案的資源準(zhǔn)備時間并得到實(shí)際開工時間Sij+1，用兩個指標(biāo)評價方案的好壞，裝載率與延誤率。

裝載率f1表示機(jī)器的利用率，計(jì)算公式為

延誤率f2表示該批次工件的批處理加工階段延誤時間和的倒數(shù)，越大說明延誤時間越短，計(jì)算公式為

其中，Sij+1-ETij表示工件批處理工序的前道工序的完工時間與批處理開工時間的差值。

由于量綱不同，對兩個指標(biāo)進(jìn)行歸一化處理，用于確定每個批處理批次的劃分依據(jù)f。其計(jì)算公式為

圖2 分批Figure 2 Batch division

2.2 種群初始化

種群初始化是進(jìn)化算法獲得快速收斂速度和高效求解質(zhì)量的關(guān)鍵。本文針對單批耦合問題，設(shè)計(jì)一種改進(jìn)NEH初始化方式。具體的步驟如下。

步驟1隨機(jī)生成一組基因V=[Vj|Vm]，按照上文的解碼方式計(jì)算每個工件的在機(jī)器上的加工時間相加得到總加工時間，按照非增順序排列，得到初始排列ST={ST1,ST2,…,STn}。

步驟2取出前g個工件，直到在能達(dá)到批處理階段的機(jī)器加工閾值，按原始順序排列這部分調(diào)度，記錄為當(dāng)前調(diào)度，記為ST'=

步驟3取出初始排列ST中的第 (g+1) 個工件，將其插到ST'所有可能的位置，共得到g種排列，評價所有排列，將最大完工時間最小的排位，作為當(dāng)前排列。

步驟4循環(huán)執(zhí)行步驟3，直至輸出最夠調(diào)度基因。

步驟5執(zhí)行步驟1～ 4，直至形成種群P。

2.3 模因組劃分

對生成的初始化種群P進(jìn)行非支配與擁擠度排序，按下列過程構(gòu)建w個模因組：將第1個個體分到第1個模因組，第2個分到第2個模因組，以此類推，第w個分到第w個模因組，第w+1個分到第1個模因組，依次進(jìn)行，直到所有個體分配完。同時為了保證搜索過程中搜索資源的充分利用，引入外部種群 ?，容量與種群數(shù)目相同，用于保存迭代過程中被替換的較好的解。

2.4 模因組搜索

蛙跳算法主要通過模因組的搜索進(jìn)行迭代跟新，通常是對所有模因組內(nèi)的最差解進(jìn)行優(yōu)化，但是不同模因組個體的特點(diǎn)不同，用相同的搜索方式會忽略不同個體的特性。因此，本文將模因組分為兩類，采用不同的更新策略來使其朝著最優(yōu)解的可能方向進(jìn)行搜索。第1類由組內(nèi)存在單個目標(biāo)最小值的模因組構(gòu)成，第2類由其他模因組構(gòu)成。通過分配給第1類模因組個體更多的搜索次數(shù)來加強(qiáng)算法的搜索有效性，避免搜索資源的浪費(fèi)。同時加工過程中，總批次數(shù)目越少，批加工機(jī)器的利用率越高，工藝流程更為簡單，所以在進(jìn)行迭代更新過程盡量保留批次數(shù)目較少的解。

模因組的具體搜索過程如下。

步驟1定義模因組內(nèi)搜索次數(shù)μ，最優(yōu)解限制次數(shù)λ，將種群的非支配解放入外部種群 ?，種群的每個目標(biāo)的最優(yōu)解為Xb1和Xb2。

步驟2將模因組進(jìn)行非支配排序排序，隨機(jī)選擇一個非支配解為模因組內(nèi)的最好解Xbb，從除Xbb外的解中隨機(jī)挑選一個解作為優(yōu)化對象Xb，搜索次數(shù)t=1。

步驟3對優(yōu)化對象Xb與Xbb進(jìn)行交叉，交叉方式采用POX與TPX兩種方式，兩種方式的選擇概率相同，交叉生成新的個體Xbn。如果新解Xbn支配Xb，則替換解Xb；若互不支配，則判斷兩個解的批次總數(shù)目，保留總批次數(shù)目少的解，用另一個解更新外部種群 ?，若為第1類模因組，執(zhí)行步驟4，否則執(zhí)行步驟5，t=t+1。

步驟4若新解被舊解支配，則隨機(jī)選擇外部解集一個解與模因組最優(yōu)解Xbb生成新解Xb'，如若Xb'不被Xb支配，則替換Xb且更新外部種群 ?。若模因組組內(nèi)最優(yōu)解集沒有進(jìn)行改變，則對最優(yōu)解進(jìn)行鄰域搜索，定義3種鄰域結(jié)構(gòu)，如圖3所示。

圖3 鄰域結(jié)構(gòu)示意圖Figure 3 Schematic diagram of neighborhood structure

1) 批處理工序交換鄰域。隨機(jī)選擇若干個批次(選擇批次數(shù)目不大于總批次數(shù)目)，并按照工件重量升序重新分配工序位置。

2) 基于關(guān)鍵路徑的鄰域。選擇一個關(guān)鍵路徑，交換前兩個與后兩個關(guān)鍵塊。

3) 資源重選鄰域。隨機(jī)選擇若干道資源準(zhǔn)備時間大于0的工序，為選擇的工序重新分配加工機(jī)器。

步驟5若新解被舊解支配，重新生成新解Xb'，如若Xb'不被Xb支配，則替換Xb且更新外部種群 ?。若模因組組內(nèi)最優(yōu)解μ次沒有改變，將最優(yōu)解與單個目標(biāo)最優(yōu)值的解Xbb1或Xbb2交叉進(jìn)行全局搜索。

步驟6t=μ，搜索結(jié)束。

外部種群的更新方式為：解Xb進(jìn)入外部種群時，先檢索是否存在相同的解，若不存在，則加入外部種群，將所有解進(jìn)行Pareto排序和擁擠度，保留非支配解，剔除支配解，若數(shù)目超過外部總?cè)喝萘繛関，則舍棄擁擠度最小解。

2.5 算法流程

算法的流程圖如圖4所示，詳細(xì)步驟描述如下。

圖4 算法流程圖Figure 4 Flow chart of the algorithm

1) 初始化種群規(guī)模N、模因組個數(shù)w等參數(shù)。

2) 改進(jìn)的NEH方法進(jìn)行初始化種群。

3) 對種群進(jìn)行Pareto和擁擠度排序，從而進(jìn)行模因組構(gòu)建。

4) 執(zhí)行模因組搜索。

5) 將外部總?cè)号c模因組進(jìn)行合并，重新進(jìn)行Pareto和擁擠度排序，進(jìn)行種群重構(gòu)。

6) 判斷是否達(dá)到終止條件，達(dá)到則輸出種群非支配解集合，否則執(zhí)行3)。

3 仿真實(shí)驗(yàn)

為測試算法的有效性，將參考Carlier算例[17]設(shè)計(jì)20個擴(kuò)展算例和鑄造企業(yè)的一組實(shí)際算例來進(jìn)行仿真計(jì)算。用2個性能指標(biāo)來衡量Pareto前沿。研究了每個改進(jìn)措施的有效性，最后和其他的優(yōu)化算法進(jìn)行了對比。所有的實(shí)驗(yàn)在Matlab 2016上進(jìn)行運(yùn)行，代碼的運(yùn)行環(huán)境為2.7 GHz CPU,8 GB內(nèi)存,64位Win10系統(tǒng)計(jì)算機(jī)。

3.1 測試算例和對比算法

測試算例用Carlier算例基礎(chǔ)上擴(kuò)展的20個算例和鑄造企業(yè)的一組實(shí)際算例來進(jìn)行仿真計(jì)算。20個擴(kuò)展算例中的工件數(shù)目為 (15,30,50,100)，加工階段數(shù)目為 (4,6,8,10,12)，工件重量在[10,50]上均勻分配，加工機(jī)器除了批處理階段外，其他階段都有3臺加工機(jī)器，加工時間在[2,10]上進(jìn)行分布。以算例1為例，總共有15個工件、4道工序，其中第3道工序?yàn)榕幚?，總共?類加工附屬資源，每種資源總數(shù)為10，另外還規(guī)定了每臺機(jī)器的加工與待機(jī)能耗，機(jī)器加工所需要的附屬資源數(shù)目在[1,3]上隨機(jī)分配。實(shí)際算例以某批次砂型鑄件為對象，該批次有12件鑄件，每個工件都要進(jìn)行11道加工工序，可加工機(jī)器有24臺。加工流程為混砂、造型、制芯、合箱、熔煉澆筑、落砂、拋丸、打磨、機(jī)加工、清整及出庫檢查，其中第5道工序熔煉澆注為批處理工序階段，其他工序?yàn)閱渭庸すば?；加工附屬資源數(shù)目為4種，分別為在造型與制芯工序的砂箱，在熔煉澆筑階段需要的保溫爐，熔煉、混砂、拋丸、落砂需要的除塵設(shè)備與工序之間的運(yùn)輸設(shè)備。

為說明算法的有效性，選擇在車間調(diào)度問題中常用的非支配排序遺傳算法 (non-dominated sorting genetic algorithm,NSGAⅡ)、帝國競爭算法(imperialist competitive algorithm,ICA)[18]以及灰狼算法 (grey wolf optimizer,GWO)[19]作為對比算法。其中NSGAⅡ的交叉率為0.7，變異率為0.3，其余算法參數(shù)與算法參考文獻(xiàn)一致，對比算法采用隨機(jī)編碼的方式進(jìn)行種群初始化。為驗(yàn)證算法的有效性和避免結(jié)果的隨機(jī)性，每個算例下的算法獨(dú)立運(yùn)行30次，結(jié)果采用30次運(yùn)行的平均值。

3.2 評價指標(biāo)與實(shí)驗(yàn)參數(shù)

為了綜合評價算法的收斂性和穩(wěn)定性，用兩個指標(biāo)來評價算法的性能。

1) IGD指標(biāo)，等同于衡量算法的收斂性和多樣性，值越小，收斂性和多樣性越好，計(jì)算公式為

其中，di表示歐氏距離，PF為參考集。

2) RAS目標(biāo)完成率，計(jì)算同時達(dá)到每個目標(biāo)的概率，越小說明解質(zhì)量越好，計(jì)算公式為

其中Ui是每個目標(biāo)的最小值。

算法的主要參數(shù)有3個：種群規(guī)模N，模因組數(shù)目w，模因組內(nèi)搜索次數(shù)μ。采用實(shí)驗(yàn)設(shè)計(jì)考察不同的參數(shù)對算法性能的影響，以“J15-10b8”為測試算例，選擇規(guī)模為 (33) 的正交試驗(yàn)對算法參數(shù)進(jìn)行優(yōu)化，為避免結(jié)果的隨機(jī)性，每組算法獨(dú)立運(yùn)行30次，取IGD值作為評價指標(biāo)，實(shí)驗(yàn)結(jié)果如表2所示。根據(jù)正交試驗(yàn)表繪制如圖5所示的參數(shù)水平趨勢圖，由圖可以確定本文算法的參數(shù)選擇種群規(guī)模N=90，模因組數(shù)目w=10和模因組內(nèi)搜索次數(shù)μ=30，此外算法運(yùn)行時間取1.8×103s。

圖5 參數(shù)水平變化趨勢圖Figure 5 Trends of parameter levels

表2 正交試驗(yàn)結(jié)果表Table 2 Results of orthogonal test

3.3 計(jì)算結(jié)果與分析

3.3.1 擴(kuò)展算例結(jié)果分析

20個測試算例的比較結(jié)果見表3和表4，其中粗體表示各算例算法所得最優(yōu)值。從表3給出的20個算例仿真結(jié)果在最小化最大完工時間、機(jī)器總能耗兩個目標(biāo)值上來看，在規(guī)模較小的算例中，算法的目標(biāo)平均值差距不大，隨著算例規(guī)模的增加，本文所提出的算法所求結(jié)果明顯優(yōu)于其他算法，在較多算例上能得到最低的平均值。從表4給出的不同算例下算法性能指標(biāo)來看，在規(guī)模較小時，NSGAⅡ和ICA能得到較低的IGD與RAS值，但綜合來看ISFLA在獲得較好IGD值的同時，能減小RAS值，說明算法得到的解能更好地接近最優(yōu)解，因此綜合分析所提算法具有明顯的優(yōu)越性。

表3 算例仿真結(jié)果對比Table 3 Comparison of simulation results of calculation examples

表4 算例仿真指標(biāo)對比Table 4 Comparison of simulation indicators of calculation examples

3.3.2 實(shí)際算例結(jié)果分析

為了更好地體現(xiàn)算法的實(shí)用性，使用某砂型鑄造企業(yè)的一組實(shí)際加工訂單作為實(shí)際案例來驗(yàn)證算法的有效性，在砂型鑄造生產(chǎn)流程中主要分為鑄造前階段，熔煉澆筑和鑄造后處理3個階段。圖6為4種算法的目標(biāo)值隨著時間變化的收斂曲線，圖6 (a)與圖6 (b) 分別展示了最小完工時間與機(jī)器總能耗隨著運(yùn)行時間的迭代圖，從圖中可以看出，ISFLA算法收斂性最好。由于ISFLA算法采用了本文提出的初始化策略和更適應(yīng)模型的解碼方式，因此初始種群的質(zhì)量較其他幾種算法更好，同時算法采用改進(jìn)的模因組搜索方式，因此能更好地收斂到最優(yōu)解。圖7為該實(shí)際算例求得的一組解中的序號最前的調(diào)度甘特圖，圖中矩形的每種顏色表示一個工件，數(shù)字表示加工階段，例如1 203可以描述為工件J12的第3個加工階。該算例中工序5為批處理工序，從圖中可以看出工件被分為4個批次，由批處理機(jī)M12與M13進(jìn)行加工，經(jīng)優(yōu)化后其最大完工時間為195 min。

圖7 調(diào)度甘特圖Figure 7 The scheduling Gantt chart

4 結(jié)論

本文以資源受限下的混合流水車間為對象，針對資源約束和單批耦合特征，建立了以最大完工時間和機(jī)器能耗為目標(biāo)的數(shù)學(xué)模型。提出一種改進(jìn)的離散蛙跳算法，在蛙跳算法的基礎(chǔ)上增加了一種改進(jìn)的NEH初始化策略，提高了初始種群質(zhì)量，改進(jìn)了模因組的進(jìn)化方式并增加了外部種群，增加了算法的全局搜索能力和局部搜索能力。最后通過擴(kuò)展算例與實(shí)際算例驗(yàn)證了算法的可行性與有效性。

但是本文未考慮動態(tài)因素與分布式生產(chǎn)的影響，在未來的研究中，重點(diǎn)可以放在動態(tài)約束與分布式生產(chǎn)上。此外，將深度學(xué)習(xí)、強(qiáng)化學(xué)習(xí)和大數(shù)據(jù)分析與車間調(diào)度結(jié)合也是一個重要的研究方向。