考慮設備可靠性與能耗的平行機調(diào)度

許顯楊， 陳 璐

(上海交通大學 工業(yè)工程與管理系，上海 200240)

制造業(yè)是社會發(fā)展的重要支柱，而制造業(yè)的發(fā)展帶來了巨大的能源消耗.2016年我國制造業(yè)能源消耗量達 247 792.83 萬噸標準煤，占我國能源消費總量的56.9%[1].在保證生產(chǎn)能力的同時降低企業(yè)能耗，是制造企業(yè)構(gòu)建核心競爭力的關鍵，而通過生產(chǎn)調(diào)度手段降低生產(chǎn)系統(tǒng)能耗已成為近年來的研究熱點[2].如：Liu等[3]的研究結(jié)果表明延長1.3%的完成時間可節(jié)約22.5%的能耗；Yan等[4]列舉的包含7個加工任務的生產(chǎn)案例中，通過調(diào)度手段節(jié)約了1.88 kW·h 的電能，且節(jié)省的電能會隨著加工任務數(shù)量的增加而成比例遞增.以較低的優(yōu)化成本、較短的更新周期節(jié)約可觀的加工能耗方面，調(diào)度手段具有巨大的潛力.

從需求端降低能耗的調(diào)度問題可以分為考慮非加工能耗與考慮加工能耗兩類[2].針對降低非加工能耗問題的研究大多采用開關機(On-Off)機制，即關閉長時間不作業(yè)的設備以降低其空轉(zhuǎn)能耗.Che等[5]考慮開關機造成的額外能耗與時間浪費，并以此確定最小可關機時間間隔，建立了同時最小化延遲和能耗的多目標優(yōu)化模型.王君[6]考慮開機能耗與關機能耗，建立了以任務分配、任務起始加工時間、設備關機節(jié)點為決策變量的調(diào)度模型.Yildirim等[7]考慮啟動能耗，建立了以最小化完成時間和能耗為目標的混合整數(shù)模型.Cheng等[8]則僅考慮開機能耗，建立了分時電價下考慮開關機機制的調(diào)度模型.

從加工能耗角度建立模型多采用加工速度可變(Speed-Scaling)機制，即考慮不同加工速度對系統(tǒng)能耗及生產(chǎn)能力的影響.Fang等[9]針對流水線車間建立優(yōu)化模型，除調(diào)度序列外將加工速度也作為決策變量之一.吳秀麗等[10]則研究了柔性作業(yè)車間內(nèi)的多轉(zhuǎn)速策略,以最小化加工完成時間與總能耗.加工速度可變機制的內(nèi)涵可以進行拓展，如考慮刀具規(guī)格、切削速度、進給速率、切削深度等[11]在內(nèi)的切削參數(shù)，以及不同設備類型對于能耗及加工能力的影響.Wang等[12]考慮不同切削條件對能耗及加工能力的影響，利用兩階段啟發(fā)式算法降低了平行機車間的加工能耗.He等[13]考慮設備類型對能耗的影響，將設備選擇與調(diào)度序列作為決策變量建立了數(shù)學模型.李聰波與何彥等[14-15]研究柔性作業(yè)車間，在調(diào)度模型中考慮工藝路線對于能耗的影響，提出了節(jié)能調(diào)度方法.

Yan等[16]的研究表明隨著可靠性的下降，加工能耗隨之升高.Dahmus等[17]對實際數(shù)據(jù)的分析結(jié)果表明，設備老化將帶來更高的加工能耗.然而，目前考慮能耗的調(diào)度研究中多將設備健康狀態(tài)視為穩(wěn)定的且在調(diào)度過程中不發(fā)生改變，這與實際加工的情況偏差較大.Nezami等[18]提出的三目標優(yōu)化問題，利用開關機機制同時最小化能耗、完成時間與最大化可靠性，但模型中將能耗與可靠性視為完全無關的變量.Yildirim等[19]提出設備可靠性的下降導致加工時間延長，但忽略了可靠性對加工能耗的影響.

本文研究平行機調(diào)度問題，考慮可靠性對加工能耗的影響，建立了以最小化能耗成本與延遲成本加權(quán)和為優(yōu)化目標的數(shù)學規(guī)劃模型，設計開發(fā)了蟻群算法對問題進行求解，最后利用算例實驗證明了算法的有效性及具有的較高效率.

1 能耗與設備可靠性關系的定義

可靠性是指產(chǎn)品在規(guī)定條件下和規(guī)定時間內(nèi)完成規(guī)定功能的能力[20]，用可靠度函數(shù)R(t)表示，定義為系統(tǒng)或部件在時間t內(nèi)正常工作的概率.本文采用指數(shù)型可靠度函數(shù)對設備的可靠性進行建模，其在系統(tǒng)或部件的可靠性研究領域是最常用的分布函數(shù)之一[20].可靠度函數(shù)

Rk(Lk)=exp(-λLk),t≥0

(1)

式中：λ為故障率；Lk為設備k經(jīng)過上一次維護變?yōu)槿聽顟B(tài)后的累積加工時間.

在設備的一個維護周期內(nèi)，隨著設備使用時間的累積，其可靠性rk隨之逐漸下降(見圖1(a))，而任務i的加工功率Ei隨之逐漸增加[16](見圖1(b)).

圖1 設備加工功率與可靠性的關系

基于圖1中設備加工功率與可靠性的定性映射關系，本文定義設備加工任務i的實際加工功率與設備可靠性rk的定量關系為

(2)

2 模型建立

在加工車間內(nèi)有平行機集合M，且各設備的初始狀態(tài)是不同的.需要對集合N中的任務進行加工，目標設定為最小化能耗成本與延遲成本.模型假設：① 所有的任務在0時刻即可以開始加工；② 每臺設備在同一時刻僅能加工1個任務；③ 加工過程不允許被打斷；④ 任務不允許使用多臺設備進行加工；⑤ 在單個任務的加工過程中，設備的可靠性不發(fā)生變化.

模型中的基本符號：N′為包含虛擬任務“0”的任務序號集合；pi為任務i的加工時間；di為任務i的交付期；L0k為設備k在調(diào)度開始前的累計加工時間；B為一個極大的正數(shù)；γ為單位延遲時間的成本系數(shù)；ε為單位能耗的成本系數(shù)；δ為能耗成本的權(quán)重系數(shù).

模型的決策變量xijk為0/1變量，如果在設備k上任務j緊隨任務i后進行加工，則取1，否則取0.

輔助決策變量：Ci為任務i的加工完成時間；Lik為設備k在任務i加工開始前的累計時間；rik為設備k在任務i開始加工前的可靠性；ei為任務i的實際加工功率.

由此建立數(shù)學模型如下：

(3)

(4)

(5)

(6)

(7)

(8)

?i∈N,k∈M

Cj-Ci+B(1-xijk)≥pj

(9)

?j∈N,i∈N′,i≠j,k∈M

Ljk-Lik+B(1-xijk)≥pi

(10)

?j∈N,i∈N′,i≠j,k∈M

(11)

?j∈N,k∈M

(12)

?j∈N,k∈M

(13)

?i∈N,j∈N,k∈M

目標函數(shù)即式(3)包含兩部分：第一部分為能耗成本，由單位能耗成本系數(shù)與總能耗的乘積來表示；第二部分為延遲成本，由單位延遲時間成本系數(shù)與總延遲時間乘積表示.式(4)與(5)保證一臺設備的虛擬任務“0”前后至多只能有1個任務進行加工.式(6)與(7)保證任務僅能在1臺設備上進行加工.式(8)保證每個任務僅能有1個前序任務和1個后序任務.式(9)描述了任務與其前序任務完成時間的關系，式(10)表示了任務與前序任務設備累計加工時間的關系.式(11)與(12)分別為可靠性及能耗的計算關系.式(13)定義了模型中各個變量的取值范圍.

以最小化總延遲成本為優(yōu)化目標的平行機調(diào)度問題是NP-Hard問題[21]，而相較于傳統(tǒng)的平行機調(diào)度問題，本文在平行機調(diào)度問題中考慮了設備可靠性對能耗的影響，引入了計算可靠性的非線性約束(式(11))，更增加了求解難度.如當設備數(shù)量為3，任務數(shù)量為10時，模型共有462個變量，757個約束，Lingo求解器在24 h內(nèi)無法得到最優(yōu)解.因此，為了求解大規(guī)模問題，本文開發(fā)了更為高效的蟻群算法.

3 算法設計

為了解決提出的調(diào)度問題，本文設計開發(fā)了一個蟻群算法(ACO).首先，基于ATC(拖期成本)規(guī)則提出了新的啟發(fā)式規(guī)則用于生成初始解，以確定蟻群算法的參數(shù)及構(gòu)造流程；然后，通過設備選擇，任務選擇，任務分配3個過程構(gòu)造調(diào)度解，將任務分配到設備上，完成調(diào)度序列的構(gòu)造，并提出了創(chuàng)新的蟻群搜索啟發(fā)因子，定義了蟻群的搜索過程；最后，引入了局部搜索算法提升解的質(zhì)量.具體的算法流程如下.

3.1 初始解生成

本文提出了新的啟發(fā)式規(guī)則用于生成初始解，用于確定蟻群搜索流程及算法參數(shù).

步驟1設U為所有未加工任務的集合，tk是設備k上所有已分配任務的加工完成時間.初始時，U=N,tk=0,k∈M.

(14)

步驟4將任務j*分配到設備k*的加工序列的下一個位置.更新tk*=tk*+pj*，令U=U/j*.

步驟5重復步驟2～4，直到所有任務分配完成，即U=?.

步驟6對每一臺設備的加工序列進行相鄰任務交換操作，提升解的質(zhì)量.

3.2 蟻群算法調(diào)度序列的構(gòu)造

在傳統(tǒng)的以最小化延遲成本為目標函數(shù)的平行機調(diào)度問題中，多將解的構(gòu)造分為兩個階段：分配與排序[22].本文的模型需要同時最小化能耗成本與延遲成本，因此提出了一個三階段的構(gòu)造方式，即設備選擇、任務選擇與任務分配，得到|M|維向量表征得到的調(diào)度序列.

3.2.1設備選擇 構(gòu)造調(diào)度序列首先需要選擇一個設備，選擇方式由初始解能耗成本與延遲成本的關系確定.首先生成一個符合[0,1]均勻分布的隨機數(shù)qa，qa0是用戶定義的表征探索偏好的常數(shù)，且 0≤qa0≤1.當qa≤qa0時，選擇所有設備中累積加工時間最短的設備，或是選擇最先可用的設備；否則，基于概率分布Pk隨機選擇設備k.

(15)

(16)

(17)

(18)

如果初始解能耗成本高于延遲成本，則依據(jù)式(15)和(16)，即根據(jù)設備累計加工時間選擇設備；反之，則依據(jù)式(17)和(18)，即基于設備最早可用時間選擇設備.

3.2.2任務選擇 設備選擇完成后，蟻群需要基于所選設備k*選擇一個任務.在這個階段，選擇任務基于信息素強度τk*j與啟發(fā)因子ηk*j，重要程度分別為α與β.其中，啟發(fā)因子ηk*j=Ik*j.任務選擇的步驟具體如下：生成符合[0,1]均勻分布的隨機數(shù)qs，當qs≤qs0時，選擇使得(τk*j)α(σηk*j)β最大化的任務j*，其中σ為比例系數(shù)；否則，基于概率分布Pk*j選擇任務j.選擇過程為

(19)

(20)

3.2.3任務分配 考慮到各個設備的可靠性不同，帶來的額外能耗有所差別，因此在第3階段根據(jù)下式為第2階段中選擇的任務j*分配設備，采用貪心策略選擇使目標函數(shù)值最小的設備.

k**=arg min[δεEj*(e-λ(L0k+tk))+

(1-δ)γmax{tk+pj-dj,0}]

(21)

基于這樣的重選過程選擇了任務與設備，代表任務分配到設備進行加工.

3.3 局部搜索

當所有任務均已分配完成時，一個完整的調(diào)度序列已構(gòu)造完成.為進一步提升解的質(zhì)量，采用如下兩個局部搜索算法規(guī)則對現(xiàn)有調(diào)度序列進行改進.

規(guī)則1同一設備上的任務交換.隨機選擇設備k，選擇在設備k上加工的任務j1與j2，交換j1與j2.

規(guī)則2任務在不同設備之間的交換.選擇目標函數(shù)值最高的設備和目標函數(shù)值最低的設備，在設備k1加工的任務中選擇任務j1，在設備k2加工的任務中選擇任務j2，交換j1與j2.

3.4 信息素更新

在所有螞蟻找到可行解后，需要對信息素進行更新，以便于對后續(xù)循環(huán)中的螞蟻進行指導，獲得更優(yōu)的目標函數(shù)值.當一次循環(huán)內(nèi)所有螞蟻完成搜索后，分以下3種情況進行信息素更新：① 若在當前的全局最優(yōu)調(diào)度中任務j在設備k上進行加工，則增加信息素τkj強度；② 若在本次循環(huán)內(nèi)的最優(yōu)調(diào)度中任務j在設備k上進行加工，則增加信息素τkj強度，但增加的信息素少于全局最優(yōu)調(diào)度；③ 其余路徑信息素τkj強度不增加.

τkj(t+1)=(1-ρ)τkj(t)+ρΔτkj,best

(22)

(23)

式中：Sbest及Obest表示全局最優(yōu)調(diào)度方案及其目標函數(shù)值；Slbest及Olbest表示本次搜索最優(yōu)調(diào)度方案及其目標函數(shù)值.

3.5 ACO算法流程

設當前螞蟻搜索得到的調(diào)度方案為Sants，目標函數(shù)值為Oants，綜合以上各階段的流程，本文提出的ACO算法具體步驟如下.

步驟1算法參數(shù)α、β、qa0、qs0、ρ、ITER、ANTS初始化，令iter=1.

步驟2令ants=1，U=N，tk=0,k∈M.

步驟3設備選擇.根據(jù)初始解中延遲成本與能耗成本的比例，依據(jù)式(15)～(18)選取設備k*.

步驟4任務選擇.基于信息素強度τk*j與啟發(fā)因子ηk*j，根據(jù)式(19)和(20)選取任務j*.

步驟5任務分配.貪心策略，選擇使目標函數(shù)值最小的設備k**加工j*，如式(21).

步驟6令U=U/j*，tk**=tk**+pj*，如果U=?，則轉(zhuǎn)入步驟7；否則，轉(zhuǎn)入步驟 3.

步驟7執(zhí)行局部搜索算法提升解的質(zhì)量.

步驟8若Oants

步驟9令ants=ants+1，如果ants>ANTS，那么轉(zhuǎn)入步驟 10；否則，令U=N，tk=0,k∈M，轉(zhuǎn)入步驟 3.

步驟10若Olbest

步驟11令iter=iter+1，如果iter>ITER，那么轉(zhuǎn)入步驟 12；否則，轉(zhuǎn)入步驟 2.

步驟12算法終止.

4 算例驗證與分析

4.1 參數(shù)設置

為了驗證ACO算法的性能，本節(jié)應用1組小規(guī)模算例和3組大規(guī)模算例對算法進行了測試.采用Python 2.7.13 測試算法，所有的計算實驗均在配置為Intel(R)Core(TM)i5-7200U(2.50 GHz)處理器、8 GB內(nèi)存的個人電腦上進行.

表1 算法參數(shù)水平值設置

4.2 小規(guī)模算例驗證

為求得小規(guī)模問題的最優(yōu)解，采用Lingo17.0對數(shù)學模型進行求解，如果1 h內(nèi)無法算出最優(yōu)解，則終止求解器并以當前求得的可行解作為最終解.取T=0.5，R=0.8生成各任務交付期.設備、任務數(shù)量，以及設備初始累積加工時間L0k設置如表2所示.共設置12種不同組合的小規(guī)模算例，每種組合均以參數(shù)生成規(guī)則隨機生成10組算例，分別利用Lingo與ACO算法求得最優(yōu)解，并取結(jié)果平均值進行比較.以ACO算法與Lingo求解器的偏差程度作為評價指標，即

小規(guī)模算例的實驗結(jié)果如表3所示，其中ti(i=ACO,Lingo)為采用i時的求解時間.結(jié)果表明：當Lingo可以在規(guī)定時間內(nèi)求得最優(yōu)解時，ACO算法求得的最優(yōu)解與Lingo求得的最優(yōu)解完全一致.而隨著任務數(shù)量增加，Lingo在有限時間內(nèi)無法獲得全局最優(yōu)解，此時ACO算法得到的最優(yōu)解優(yōu)于Lingo在規(guī)定時間內(nèi)得到的最優(yōu)解.同時，在求解時間上，ACO算法明顯優(yōu)于Lingo，在求解效率上更具優(yōu)勢.

表2 小規(guī)模算例參數(shù)設置

表3 小規(guī)模算例實驗結(jié)果

4.3 大規(guī)模算例驗證

當可靠性函數(shù)中參數(shù)λ=0.000 3，可靠性閾值為0.4時，計算可得設備的一個維修周期內(nèi)的可用壽命為 3 054 h.為了定義各臺設備在初始狀態(tài)時可靠性的偏差程度，引入系數(shù)b表征設備初始累計使用時間L0k的偏差程度.取所有設備L0k的中位數(shù)為 1 500 h，初始可靠性最低及最高的設備L0k分別取 1 500(1-b)和 1 500(1+b)，其余設備分別取分位數(shù).b值越大，則各設備初始可靠性的偏差程度越大.考慮到ACO算法的隨機性，在進行算法求解效率分析、調(diào)度方法比較與敏感性分析時，每種參數(shù)組合的實驗均按條件生成10組隨機算例，并取10組算例計算結(jié)果的平均值進行對比和分析.

4.3.1算法表現(xiàn)分析 問題參數(shù)設置與小規(guī)模算例相同，取b=0.5，驗證蟻群算法在解決大規(guī)模問題時的效率，同時與3.1節(jié)中提出的啟發(fā)式規(guī)則得到的初始解Oinit進行比較，驗證ACO算法的求解優(yōu)勢.求解結(jié)果如表4所示，表中數(shù)據(jù)為10個隨機算例計算時間的均值.從表中的結(jié)果可以看出，ACO算法在求解大規(guī)模問題時效率較高，可以在較短的時間內(nèi)求得滿意解，且解的質(zhì)量較之于初始解有明顯改善.

表4 ACO算法的效率與表現(xiàn)

4.3.2考慮可靠性的調(diào)度方法與不考慮可靠性的調(diào)度方法比較 為了驗證本文所提出的調(diào)度方法對于降低生產(chǎn)成本的有效性，隨機生成9組算例，分別計算考慮設備可靠性與不考慮設備可靠性時的目標函數(shù)值.b分別取0.1、0.3、0.5，代表了設備初始可靠性不同偏差程度的3種加工場景，計算結(jié)果如圖2所示.圖中：D′=(OCon-ONon)/ONon，OCon為利用本文調(diào)度方法得到的目標函數(shù)值，ONon為不考慮設備可靠性時的目標函數(shù)值.本文提出的ACO算法可以用于不考慮設備可靠性時的平行機調(diào)度問題.

圖2 考慮設備可靠性的調(diào)度方法所節(jié)約的成本

比較9組算例的成本值可以得出以下結(jié)論：

(1)相對于不考慮設備可靠性的調(diào)度方法，本文所提出的調(diào)度決策成本較低.隨著設備初始可靠性偏差程度的增大，節(jié)約的成本值也隨之增加，當b分別取0.1，0.3，0.5時，總成本分別降低了0.60%，1.29%，2.04%.這主要是因為考慮了設備可靠性后所得到的調(diào)度序列更加合理地分配了加工任務.

圖3 可靠性偏差程度b對應的總成本

圖4 可靠性偏差程度b對應的延遲成本比例

(2)相對于不考慮設備可靠性的調(diào)度方法，本文方法所節(jié)約的成本隨著問題規(guī)模的增加而增大.如設備數(shù)量為5時，加工任務取50，60，70時分別節(jié)約了1.17%，1.49%，1.66%的總成本.這表明當問題規(guī)模增大時，在生產(chǎn)調(diào)度中考慮設備可靠性更有意義.

4.3.3敏感性分析

(1)設備初始可靠性對調(diào)度決策的影響.首先取9組不同算例驗證初始可靠性的偏差程度對加工任務分配的影響，取T=0.4代表交付期較緊的情況.每組算例分別計算b取0.1，0.2，0.3，0.4，0.5時的結(jié)果，對比5種情況下總成本O，以及延遲成本在總成本中的占比Γ，結(jié)果如圖3和4所示.

從結(jié)果中可以看出，隨著b的增加，生產(chǎn)總成本幾乎保持不變，但延遲成本的占比隨之升高.這是由于，隨著設備初始可靠性的偏差程度增加，對任務進行分配時會更加優(yōu)先考慮設備可靠性.初始可靠性較低的設備將會加工數(shù)量更少的任務或者工時較短的任務，且初始可靠性偏差程度越大，設備間的加工時間差異越大.這樣的任務分配方式犧牲了一定的交付期限，帶來了更高的延遲成本，但卻降低了更多的能耗成本.相較于傳統(tǒng)不考慮可靠性的調(diào)度，這樣的任務分配原則更加有利于降低生產(chǎn)總成本.

此外，當b由0.4變?yōu)?.5時，延遲成本比例變化較大，這表明當設備初始可靠性偏差程度很大時，任務分配對設備初始可靠性偏差程度的變化更敏感.

(2)交付期對調(diào)度決策的影響.為了分析交付期松緊程度對于調(diào)度決策的影響，取b=0.5，令R=0.4，分別計算T取0.1，0.2，0.3，0.4，0.5時，延遲成本在總成本中的占比Γ′，結(jié)果如圖5所示.

圖5 交付期松緊對于調(diào)度決策的影響

由圖5可見，隨著T的增大，任務交貨期變緊，延遲成本比例隨之升高，各設備累積加工時間趨于一致，且T越大變化趨勢越明顯.分析結(jié)果可以得出以下結(jié)論：

當T≤0.3 時，加工任務的交付期較松，產(chǎn)能壓力較小，此時初始可靠性較高的設備承擔了更多的加工任務，大幅降低了能耗成本，有效地節(jié)約了生產(chǎn)總成本.

當T>0.3時，交付期較緊，過度關注能耗成本將會帶來較高的延遲成本.

以上分析表明：在實際生產(chǎn)調(diào)度決策時，當交付期較松時，交付期不是降低成本的瓶頸因素，此時關注設備可靠性對生產(chǎn)調(diào)度的影響可以有效降低生產(chǎn)成本；而當交付期較緊時，則應主要關注延遲成本對于總成本的影響.

5 結(jié)語

本文研究在平行機調(diào)度問題中設備可靠性對設備能耗成本的影響，建立了最小化延遲成本和加工能耗成本的數(shù)學模型，設計開發(fā)了蟻群算法求解問題，為車間降低總生產(chǎn)成本提供了新的思路.實驗結(jié)果證明，本文提出的算法能夠快速有效地求解所研究問題，相比不考慮能耗成本的調(diào)度方法，最多可降低2.5%的生產(chǎn)總成本，具有實際應用價值.此外，敏感性分析表明：當交貨期較松時，將加工任務分配給可靠性較高的設備可以有效地降低系統(tǒng)成本；而當交貨期較緊時，則應在保證不造成過高延遲的情況下進行任務分配.這一結(jié)論為車間基于設備可靠性進行生產(chǎn)調(diào)度決策提供了理論依據(jù).在后續(xù)的研究中，將增加維護決策，以達到改善設備狀態(tài)，提高設備的可靠性的目的，但是增加維護決策將進一步增加模型的復雜度和求解難度.