吳宇娟

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

0 引言

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

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

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

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

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

1 問(wèn)題描述與模型建立

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

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

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

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

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

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

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

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

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

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

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

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

（1）基于負(fù)荷均衡的工件分配

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

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

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

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

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

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

//初始解的l 是工件按其電耗率從大到小排序得來(lái)的，之后的l 是通過(guò)對(duì)初始的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)的機(jī)器上，此時(shí)，問(wèn)題變?yōu)槿绾螌?duì)每一機(jī)器上已分配的工件進(jìn)行調(diào)度優(yōu)化，即分時(shí)電價(jià)下的單機(jī)調(diào)度問(wèn)題。為解決該問(wèn)題，本文提出了一個(gè)帶有多級(jí)過(guò)濾的貪婪插入啟發(fā)式算法，以此最小化加工所有工件的電耗總成本。

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

算法2帶有多級(jí)過(guò)濾機(jī)制的貪婪插入啟發(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層插入成本最低的位置，計(jì)算出電成本cost1,

a.2.計(jì)算cost ?cost+cost1,

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

b.elseif i ∈layer2 do

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

b.2.計(jì)算cost ?cost+cost2,

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

c.elseif i ∈layer3 do

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

c.2.計(jì)算cost ?cost+cos t3,

c.3.工件 i 插入到這個(gè)位置并更新機(jī)器上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禁忌搜索-多級(jí)過(guò)濾貪婪插入啟發(fā)式算法

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

2.由算法1 確定每臺(tái)機(jī)器上的加工工件，

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

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

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

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

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

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

3 實(shí)驗(yàn)結(jié)果分析

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

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

表1 實(shí)驗(yàn)采用的分時(shí)電價(jià)方案

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

表2 模型與算法的實(shí)驗(yàn)對(duì)比

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

4 結(jié)語(yǔ)

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

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