基于混合禁忌搜索算法的分時電價下并行機調(diào)度優(yōu)化

吳宇娟

（安徽工業(yè)大學(xué)管理科學(xué)與工程學(xué)院，馬鞍山243032）

0 引言

全球經(jīng)濟的發(fā)展導(dǎo)致了能源消耗的增加，能源短缺成為許多國家經(jīng)濟發(fā)展的瓶頸。國際能源署（International Energy Agency，IEA）2015 年發(fā)布的研究報告指出，2040 年全球的能源需求總量將比2015 年增長37%[1]。在產(chǎn)生和消耗能源的過程中，大量溫室氣體被排放到大氣中，給環(huán)境造成了嚴重污染[2]。作為最大的制造業(yè)國家，我國正面臨著能源節(jié)約和環(huán)境保護的嚴峻挑戰(zhàn)，采取充分考慮節(jié)能的生產(chǎn)決策顯得尤為重要。

電能作為二次能源廣泛應(yīng)用于生產(chǎn)生活中，同時也是大部分制造業(yè)使用的主要能源[3-4]。但電能很難存儲，用電方在不同的時段對電力的需求不同[5]。為了使電力供需達到平衡，供電方往往會采取分時電價（Time of Use，ToU）機制來引導(dǎo)用電方降低高峰時期用電需求從而降低高峰時期電網(wǎng)負荷[6]。分時電價機制是指根據(jù)電網(wǎng)負荷和用電需求將一天分為多個時段，對于不同的時段采取不同的定價方案。分時電價的實施不僅可以提高電網(wǎng)系統(tǒng)的穩(wěn)定性，同時也可促使用電方將高峰時段的加工任務(wù)調(diào)整到用電平段及低谷時段，進而減少電力消耗總成本[7-8]。

為了更好地適應(yīng)分時電價機制，生產(chǎn)管理者需要通過調(diào)度來調(diào)整他們的生產(chǎn)任務(wù)。調(diào)度是指將有限的資源分配到不同的任務(wù)中，以此來優(yōu)化一個或者多個目標的決策過程[9]。其中，單機調(diào)度是一類基本的調(diào)度問題，相關(guān)研究可以為解決并行機調(diào)度問題提供參考。Zhang 等人[10]研究了分時電價下最小化總用電成本的單機調(diào)度問題，構(gòu)建了混合整數(shù)線性規(guī)劃（MILP）模型并設(shè)計了帶有多級過濾機制的貪婪插入算法來進行求解。

相同并行機調(diào)度不僅是單機調(diào)度問題的泛化，而且是流水車間調(diào)度的一個特例[9],在制造過程中應(yīng)用廣泛，是學(xué)者們的研究熱點。曹江北等[11]研究了最小化加工周期相同并行機的工件排序問題，并提出了一個基于螞蟻系統(tǒng)的算法。Su[12]研究了帶有工件交貨期及機器能力約束的相同并行機調(diào)度問題，目標為最小化最大完工時間，采用啟發(fā)式算法及分支定界算法進行求解。Xu 等人[13]研究了以最小化加權(quán)完成時間和最大完工時間總和為目標的相同并行機調(diào)度問題，構(gòu)建了一個混合整數(shù)規(guī)劃模型并采用帶有Dantzig-Wolfe 分解的列生成方法來進行求解。

現(xiàn)有的相同并行機調(diào)度問題基本上都是以時間相關(guān)的標準作為優(yōu)化目標，如最小拖期量，最大完工時間。然而，隨著綠色制造的深入實踐，考慮能耗的并行機調(diào)度問題逐漸成為研究熱點，尤其是，分時電價機制作為有效調(diào)節(jié)能耗的一種方法，已被廣泛應(yīng)用[14-15]。因此，如何結(jié)合分時電價機制，優(yōu)化相同并行機總用電成本的調(diào)度問題，對制造業(yè)的節(jié)能減排具有重要意義。

1 問題描述與模型建立

考慮一組工件N={1,2,…,n}需要在M={1,2，…,m}臺相同并行機上進行加工。其中，工件i ∈N 在所有機器上的加工時間為ti，單位電耗率為pi，每臺機器在同一時刻最多只能加工一個工件，每個工件只能選擇在一臺機器上進行加工，加工過程中不允許中斷。所有的工件都在零時刻到達，所有的機器在零時刻都是可用的，不考慮機器的故障和預(yù)防性維護。

分時電價機制下，不同時段對應(yīng)的電價是不同的。本文將一整天分為K 個時段,每個時段k ∈K 都有其對應(yīng)的電價ck及開始時間bk。時段k 的時間間隔可由[bk,bk+1]表示，時段 k 的持續(xù)時間表示為Tk(Tk=bk+1-bk)。為了便于求解，設(shè)置b1=0，同時bK+1不小于加工所有工件的最大完工時間，以保證該問題始終會存在可行解。

本文所研究的問題是要在給定的時間范圍內(nèi)，將每一個工件分配到合適的機器上同時確定其加工位置，使得加工所有工件的總用電成本最小。每個工件可能在一個或多個時段內(nèi)加工，這就需要確定每個工件在所有時段內(nèi)實際的加工時間，基于對問題的分析，定義以下決策變量：

xijk:工件i 在機器 j 的時段 k 內(nèi)的加工時間

根據(jù)以上的符號以及定義，建立如下的混合整數(shù)線性規(guī)劃（MILP）模型：

模型優(yōu)化目標為最小化加工所有工件的總用電成本。式（1）確保每一工件分配到所有機器各個時段的加工時間之和應(yīng)當(dāng)?shù)扔诠ぜ募庸r長。式（2）表示如果工件i 在機器j 上加工（即uij=1），那么這個工件在該機器上的所有時段內(nèi)的加工時間之和不能超過其實際的加工時間。式（3）指如果工件i 不在機器j 的時段k 內(nèi)加工（即oijk=1），那么工件i 在機器j 的時段k 內(nèi)的加工時間為0。式（4）表示在某臺機器的某個時段內(nèi)所有工件的加工時間之和不超過這個時段的持續(xù)時間。

式（5）表示的是兩個0-1 變量之間的包含關(guān)系，如果oijk=1,那么uij=1 必然成立。式（6-8）表示任一工件都以不可中斷的方式被加工。式（9）是確保每一個工件只能在一臺機器上進行加工。式（10-11）是決策變量的二元約束。Zhang 等人[12]證明其研究的分時電價下單機調(diào)度問題是NP-hard 問題，本文在其研究基礎(chǔ)上增加了一個機器選擇的問題，因此，本文所研究的問題同樣是NP-hard 問題。此外，可知在本文構(gòu)建的連續(xù)時間混合整數(shù)線性規(guī)劃模型中，變量的數(shù)目為2NMK+NM，約束的數(shù)目為O(N2Mk)+O(MNK2)。

2 禁忌搜索-多級過濾貪婪插入啟發(fā)式算法

并行機調(diào)度問題一般可以分為兩個子問題，第一個子問題是將工件分配到機器上，第二個子問題是在每臺機器上調(diào)度已經(jīng)分配的工件。當(dāng)?shù)谝粋€子問題解決之后，第二個子問題變?yōu)槊颗_機器上的單機調(diào)度問題。對于工件機器分配這個子問題，本文利用負載平衡原則進行處理，而對于每臺機器上的工件調(diào)度，采取多級過濾貪婪插入啟發(fā)式算法來進行求解。

基于負載平衡原則的工件機器分配方法如下：對每臺機器，計算出已分配到該機器的所有工件的加工時間總和，待分配工件選擇總加工時間最小的那臺作為加工機器，然后更新加工機器的總加工時間，迭代循環(huán)，直到所有工件分配完成。通過這個規(guī)則，不僅可以將工件分配到機器上，同時可以計算出加工這些工件所需要的總時間，確定加工時間下界。

首先所有工件按其加工電耗率從大到小排序得到一個初始序列，通過負載平衡原則將序列中的工件分配到機器上，接著采取多級過濾貪婪插入啟發(fā)式計算出所有機器的總用電成本。由于每個工件在每臺機器上的加工時間及電耗率都是相同的，其加工次序決定了工件所分配的機器及最終加工位置。即工件的加工序列決定了解的質(zhì)量，因此，為了得到理想解，本文利用禁忌搜索算法對初始序列進行迭代優(yōu)化，選出使總電成本最小的加工序列。

2.1 多級過濾貪婪插入啟發(fā)式算法

（1）基于負荷均衡的工件分配

在該階段，算法在于實現(xiàn)以機器負荷均衡為原則將工件分配到相應(yīng)的機器上，而Davis 和Jaffe[16]設(shè)計的列表調(diào)度（List Scheduling，LS）啟發(fā)式算法可以有效地實施這個分配規(guī)則。主要步驟包括：首先，所有工件按照其電耗率從大到小進行排序，然后，工件按照列表的順序分配給具有最小總加工時間的第一臺可用機器。最后，更新機器的總加工時間，并重復(fù)上述步驟，直到分配完所有工件。具體流程如算法1 所示，算法中涉及的相關(guān)定義如下：

定義1機器j 的總加工時間用TPj表示，指已分配到機器j 上的所有工件的加工時間之和。設(shè)Sj表示在機器j 上加工的工件集，

設(shè)l 表示工件的加工順序列表。tij，pij分別表示工件i 在機器j(1 ≤j ≤M)上的加工時間及電耗率，且其值可提前確定。同時，變量 Pj，用來儲存機器j(1 ≤j ≤M)上已分配的工件。

算法1列表調(diào)度啟發(fā)式

1.設(shè)TPj?0,for 1 ≤j ≤M,

2.設(shè)l 表示工件的加工順序列表，

//初始解的l 是工件按其電耗率從大到小排序得來的，之后的l 是通過對初始的l 變換得到。

3.for i=1 to N do

4.end for

5.輸出Pj,for 1 ≤j ≤M。

（2）基于貪婪插入啟發(fā)式的工件調(diào)度

在第一階段完成之后，所有工件已經(jīng)分配到了相應(yīng)的機器上，此時，問題變?yōu)槿绾螌γ恳粰C器上已分配的工件進行調(diào)度優(yōu)化，即分時電價下的單機調(diào)度問題。為解決該問題，本文提出了一個帶有多級過濾的貪婪插入啟發(fā)式算法，以此最小化加工所有工件的電耗總成本。

該算法的思想是將調(diào)度過程分為粗粒度過濾以及細粒度過濾兩個階段，在調(diào)度之前，所有插入位置按照電價分為低、中、高三個層次,記為layer1、layer2、layer3。在粗粒度階段，工件首先按照電耗率從大到小排序，然后將每個工件依次分配到不同的電價層次；在細粒度階段，分析每個工件所在的電價層次、加工時間、電耗率、時段電價來確定最終工件的插入位置。具體流程如算法2 所示。

算法2帶有多級過濾機制的貪婪插入啟發(fā)式算法

1.設(shè)Tcost ?0,

2.for j=1 to M do

2.1.設(shè) l*? Pj,

2.2.將 l*中工件按電耗率從大到小排序，得到新的排序列表lj，

2.3.設(shè) ，

2.4.for i=1 to N do

a.if i ∈layer1 do

a.1.工件i 選擇layer1層插入成本最低的位置，計算出電成本cost1,

a.2.計算cost ?cost+cost1,

a.3.工件i 插入到這個位置并更新機器上layer1層的所有工件的插入位置layoutj,

b.elseif i ∈layer2 do

b.1.工件i 選擇layer2層插入成本最低的位置，計算出電成本cost2,

b.2.計算cost ?cost+cost2,

b.3.工件 i 插入到這個位置并更新機器上layer2層的所有工件的插入位置layoutj,

c.elseif i ∈layer3 do

c.1.工件i 選擇layer3層插入成本最低的位置，計算出電成本cost3,

c.2.計算cost ?cost+cos t3,

c.3.工件 i 插入到這個位置并更新機器上layer3層的所有工件的插入位置layoutj,

d.endif

2.5.end for

2.6.Tcost ?Tcost+cost,

3.end for

4.輸出Tcost,layoutjfor 1 ≤j ≤M。

2.2 算法總體框架

基于以上分析，算法的整體流程如算法3 所示。

算法3禁忌搜索-多級過濾貪婪插入啟發(fā)式算法

1.所有工件按其電耗率從大到小排序,記為l，

2.由算法1 確定每臺機器上的加工工件，

3.由算法2 計算所有工件的總用電成本及加工位置,記為X,并設(shè)置禁忌表為空，

4.判斷是否滿足終止條件，若是，便結(jié)束算法并輸出優(yōu)化結(jié)果；否則，繼續(xù)以下步驟，

5.利用X、l、算法1 以及算法2 計算產(chǎn)生若干個鄰域解，并從中選擇若干個候選解，

6.判斷候選解是否滿足藐視準則，若是，跳轉(zhuǎn)到步驟8，若不是，繼續(xù)以下步驟，

7.判斷候選解對應(yīng)的各對象的禁忌屬性，選出新的當(dāng)前解，更新禁忌表，

8.轉(zhuǎn)到步驟4。

3 實驗結(jié)果分析

為了驗證本文所構(gòu)建的MILP 模型和禁忌搜索-多級過濾貪婪插入啟發(fā)式算法的有效性，本部分將隨機生成一組算例來對比模型以及算法求解的質(zhì)量。算法是在MATLAB 2018a 中編碼，MILP 模型由AMPL（版本3.1.0）的CPLEX 求解器求解。具體實驗環(huán)境為:3.60 GHz 的Intel Core i7-4790 CPU、16 GB 內(nèi)存、Windows 7 64 位操作系統(tǒng)個人計算機。

實驗的所有測試都采用中國安徽省執(zhí)行的ToU 方案，如表1 所示。該ToU 定價方案將一天分為六個時段，其中包含三種類型的電價：高峰期、中高峰期、低谷期，并假設(shè)第一天上午8 點作為時間范圍的零點。

表1 實驗采用的分時電價方案

在產(chǎn)生隨機案例時，每個工件在機器上的電耗率遵循[30,100]Kw 之間的均勻分布，每個工件的加工時間同樣服從[30,210]min 的均勻分布。在這組實驗中，工件數(shù)設(shè)置為N=30,50,70,90,100，機器數(shù)設(shè)置為M=5,10,20。CPLEX 求解器的時間設(shè)置為3600s，如果在該時間點內(nèi)無法獲得最佳目標值，則輸出當(dāng)前解。算法中禁忌搜索算法的相關(guān)參數(shù)由算例規(guī)模確定，由于初始解的結(jié)果較好，本文采用固定禁忌長度15，終止步數(shù)50 進行實驗。每組實驗結(jié)果均為10 次隨機實驗計算的平均值，實驗天數(shù)由加工時間下界確定，機器數(shù)為5，工件數(shù)為60-100 時天數(shù)設(shè)為2，其他規(guī)模的算例天數(shù)均為1。GMT=(TECT-TECM)/TECM×100%，用來評估模型和算法的解的質(zhì)量，其中TECT表示算法求出的最優(yōu)解，TECM表示模型求出的最優(yōu)解。

表2 模型與算法的實驗對比

由表2 可知，本文所構(gòu)建的算法和CPLEX 求解器計算的目標值之間的差距不超過0.15%，計算結(jié)果非常相近，而算法的計算時間總體上要比CPLEX 的計算時間短，尤其是當(dāng)工件數(shù)超過70，差距更加明顯。同時，從表2 可以發(fā)現(xiàn)，當(dāng)工件數(shù)不超過90 時，CPLEX 求得的解要優(yōu)于算法求得的解，并且工件數(shù)越少，CPLEX計算時間的變化越平穩(wěn)。當(dāng)工件數(shù)達到100，加工機器數(shù)為5 和10 時，CPLEX 求得的解比算法求得的解要差。此時，CPLEX 在3600s 內(nèi)不能輸出最優(yōu)解，而算法在10.18s 及21.03s 時就輸出了求得的最優(yōu)解，不僅解的質(zhì)量較好，而且求解的時間非常短。綜上所述，本文構(gòu)建的模型以及算法都是可行且有效的，模型適合求解小規(guī)模問題，而算法更加適合解決大規(guī)模問題。

4 結(jié)語

針對分時電價下相同并行機調(diào)度問題，本文構(gòu)建了一個以總用電成本最小化為目標的連續(xù)時間的MILP 模型，模型中采用工件在時段內(nèi)的加工時間作為決策變量，解決了離散模型造成大量0-1 變量的問題，進而降低了模型的復(fù)雜度。同時，針對分時電價下相同并行機調(diào)度模型的特點，本文提出了一種有效的禁忌搜索-多級過濾貪婪插入啟發(fā)式算法。算法采用負載平衡原則進行工件機器分配，大大降低了計算的難度。實驗結(jié)果證明了該方法的在求解質(zhì)量及求解速度方面的有效性。

后續(xù)研究中，將會進一步探討如何將本文構(gòu)建的算法用于分時電價下多工序多階段的工件調(diào)度問題，并嘗試將本文構(gòu)建的MILP 模型及算法擴展到其他調(diào)度環(huán)境，如柔性作業(yè)車間和混合流水車間。