閆建濤，肖繼明

（西安理工大學(xué) 機(jī)械與精密儀器工程學(xué)院，西安 710048）

0 引言

工業(yè)部門消耗的能源占到了全球能源消耗的一半，而工業(yè)中90%的電力都是由制造業(yè)消耗的。電能作為制造業(yè)的主要能源，如何節(jié)約電能是制造業(yè)不得不考慮的問(wèn)題。合理的生產(chǎn)調(diào)度是可以降低電能消耗、降低生產(chǎn)成本的有效途徑之一[1]。為了維護(hù)電網(wǎng)穩(wěn)定，不同的電價(jià)政策被實(shí)施，引導(dǎo)著電力用戶改變其電力消費(fèi)模式[2]?？紤]不同電價(jià)政策的生產(chǎn)調(diào)度可以在不減少產(chǎn)出的情況下，達(dá)到企業(yè)降低電力成本的目的。

傳統(tǒng)的生產(chǎn)調(diào)度側(cè)重于提高生產(chǎn)效率，是以最小化最大完工時(shí)間、成本、交貨率等為優(yōu)化目標(biāo)，近十年來(lái)，考慮能耗的生產(chǎn)調(diào)度成為了國(guó)內(nèi)外學(xué)者研究熱點(diǎn)之一。李龍[3]等以車間的生產(chǎn)運(yùn)作時(shí)間，生產(chǎn)成本以及車間能耗為目標(biāo)，采用遺傳算法解決了流水車間綠色生產(chǎn)調(diào)度問(wèn)題，并以流水車間齒輪類零件加工為例，驗(yàn)證了模型的有效性與準(zhǔn)確性。孟磊磊[4]等針對(duì)不相關(guān)并行機(jī)調(diào)度問(wèn)題，以能耗最小化為目標(biāo)，建立5個(gè)考慮關(guān)機(jī)/重啟策略的混合整數(shù)規(guī)劃模型，并對(duì)比分析了模型的優(yōu)缺點(diǎn)。Zhang[5]等在考慮機(jī)器的加工速度基礎(chǔ)上，以加工過(guò)程的總加權(quán)延遲時(shí)間最短和總能耗最小為目標(biāo)建立模型，并采用多目標(biāo)遺傳算法對(duì)其求解。lei[6]等研究了在給定總能耗的情況下，使得完工時(shí)間和總延遲時(shí)間最小，對(duì)柔性作業(yè)車間進(jìn)行建模，并采用帝國(guó)競(jìng)爭(zhēng)算法對(duì)問(wèn)題求解。

分時(shí)電價(jià)政策是促使電能需求曲線趨于平衡，減少高峰時(shí)段用電的一項(xiàng)電力措施[7]?？紤]分時(shí)電價(jià)的生產(chǎn)調(diào)度可以改變用電時(shí)段，進(jìn)而有效的減少生產(chǎn)所需的電力成本，達(dá)到降低能耗的目的。吳宇娟[8]研究了分時(shí)電價(jià)下，以最小化總用電成本為目標(biāo)的相同并行機(jī)調(diào)度問(wèn)題，建立了連續(xù)時(shí)間混合整數(shù)線性規(guī)劃模型，采用禁忌搜索-多級(jí)過(guò)濾貪婪插入啟發(fā)式混合算法對(duì)問(wèn)題求解。Moon[9]以最小化完工時(shí)間和最小化電力成本為目標(biāo)，并使用混合遺傳算法解決了考慮分時(shí)電價(jià)的無(wú)關(guān)并行機(jī)調(diào)度問(wèn)題。Zhang[10]研究了分時(shí)電價(jià)下混合流水車間的調(diào)度問(wèn)題，建立了機(jī)床的能耗模型，以最大完工時(shí)間和電力成本最小化為目標(biāo)，采用改進(jìn)的強(qiáng)度Pareto進(jìn)化算法進(jìn)行求解。Wang[11]研究了雙機(jī)流水車間調(diào)度問(wèn)題，以分時(shí)電價(jià)下的總電力成本最小化為目標(biāo)，將問(wèn)題表示為混合整數(shù)線性規(guī)劃，然后基于Johnson規(guī)則和動(dòng)態(tài)規(guī)劃方法設(shè)計(jì)兩種啟發(fā)式算法對(duì)問(wèn)題進(jìn)行求解。Mao[12]在分時(shí)電價(jià)下針對(duì)并行機(jī)調(diào)度問(wèn)題，建立了經(jīng)濟(jì)批量調(diào)整和調(diào)度模型，其目標(biāo)是最小化生產(chǎn)中的電力成本，實(shí)現(xiàn)最優(yōu)的經(jīng)濟(jì)調(diào)度，最后通過(guò)實(shí)驗(yàn)結(jié)果證明了所提出的模型顯著降低了電力成本，并促進(jìn)了電網(wǎng)的峰值負(fù)荷調(diào)節(jié)。

從已有研究來(lái)看，大多數(shù)學(xué)者都只考慮了分時(shí)電價(jià)，并對(duì)不同的調(diào)度車間問(wèn)題進(jìn)行了建模求解，有效的降低了能耗。但僅考慮分時(shí)電價(jià)有其局限性，可能會(huì)導(dǎo)致峰谷時(shí)段的偏移，分時(shí)階梯電價(jià)作為一種新的基于價(jià)格的需求側(cè)管理措施被提出[13,14]，是在分時(shí)電價(jià)的基礎(chǔ)上加入了階梯電價(jià)，結(jié)合了分時(shí)電價(jià)的特點(diǎn)（均衡峰谷時(shí)段用電量）和階梯電價(jià)的特點(diǎn)（激勵(lì)用戶節(jié)能，提高能源利用率），可以更有效地促進(jìn)用戶節(jié)能。

流水車間是常見(jiàn)的一種車間生產(chǎn)方式，在復(fù)雜度上，2臺(tái)機(jī)器以上的流水車間調(diào)度問(wèn)題被證明是NP-hard問(wèn)題[15]，因此本文針對(duì)流水車間的節(jié)能生產(chǎn)調(diào)度問(wèn)題，考慮分時(shí)階梯電價(jià)，采用連續(xù)時(shí)間建模方式，建立生產(chǎn)調(diào)度的數(shù)學(xué)模型，設(shè)計(jì)算法進(jìn)行求解，并通過(guò)實(shí)例驗(yàn)證所建數(shù)學(xué)模型的正確性以及求解算法的有效性。

1 問(wèn)題描述

考慮分時(shí)階梯電價(jià)的流水車間問(wèn)題描述如下：有多個(gè)多種類的待加工工件，需要依次經(jīng)過(guò)相同的工序進(jìn)行加工，但不同種類的工件加工時(shí)間各不相同，每道工序只有一臺(tái)機(jī)器可以加工。已知工件各道工序在各機(jī)器上的加工時(shí)間和功率需求，要求在考慮分時(shí)階梯電價(jià)的情況下，確定工件的加工順序及每道工序的開始加工時(shí)間，保證在規(guī)定的時(shí)間內(nèi)完成加工任務(wù)，同時(shí)使得加工消耗的電力成本最小。

分時(shí)階梯電價(jià)[14]按照電力用戶的用電習(xí)慣劃分時(shí)段，將一天時(shí)間分為高峰段、平段、低谷段三個(gè)時(shí)段，并在每個(gè)時(shí)段設(shè)定多級(jí)階梯電價(jià)，以兩級(jí)階梯電價(jià)為例，在低于用電量標(biāo)準(zhǔn)時(shí)執(zhí)行第一階梯電價(jià)，高于用電量標(biāo)準(zhǔn)時(shí)，超出部分執(zhí)行第二階梯電價(jià)，如圖1所示。

圖1 分時(shí)階梯電價(jià)示意圖

針對(duì)該問(wèn)題進(jìn)行如下假設(shè)：1）同一時(shí)刻，每臺(tái)機(jī)器只能加工一道工序；2）每道工序的加工時(shí)間是確定的；3）加工是非搶占式的，每道工序一旦開始加工不能中斷；4）夾具裝卸等準(zhǔn)備時(shí)間計(jì)入每道工序的加工時(shí)間；5）工件的工序固定，每道工序必須在其緊前工序完成之后才能進(jìn)行后續(xù)工序。

2 模型建立

為建立考慮分時(shí)電價(jià)的流水車間調(diào)度模型，引入數(shù)學(xué)符號(hào)定義如下：

n：待加工工件總數(shù)；

m：加工設(shè)備數(shù)，即工件的加工工序數(shù)；

s：分時(shí)電價(jià)劃分時(shí)段總數(shù)；

i：機(jī)器編號(hào)，i∈[1，m]；

k：工件編號(hào)，k∈[1，n] ；

j：加工時(shí)段編號(hào)，j∈[1，s]；

Ej：加工時(shí)段j的耗電量；

Pik：工件k在機(jī)器i上的加工時(shí)間；

qik：機(jī)器i加工工件k時(shí)所需功率；

Sik：工件k在機(jī)器i的開始加工時(shí)間；

Eik：工件k在機(jī)器i的加工完成時(shí)間；

Emax：最大完工時(shí)間；

ST：計(jì)劃開始時(shí)間；

ET：計(jì)劃結(jié)束時(shí)間；

PCSjv：j時(shí)段第v檔階梯用電量的分界點(diǎn)（單位：千瓦時(shí)）；

Pjv：j時(shí)段的第v檔電價(jià)，v∈[1，V]；

如何實(shí)現(xiàn)這一突破，實(shí)現(xiàn)華裔青少年族群意識(shí)的恢復(fù)、華族文化的認(rèn)同、華語(yǔ)能力的掌握及華語(yǔ)水平的提高，數(shù)年來(lái)一直是老一輩華族、中國(guó)政府及華文教育者所思考的問(wèn)題。中國(guó)國(guó)務(wù)院僑辦“尋根之旅”活動(dòng)的推出，為我們提供了一條解決這一難題的極好途徑。俗語(yǔ)說(shuō)：讀萬(wàn)卷書，行萬(wàn)里路，百聞不如一見(jiàn)。“中國(guó)尋根之旅”就是培養(yǎng)文化認(rèn)同最直接、最有效的途徑之一。因?yàn)?，開展此類活動(dòng)，可以讓華裔青少年身臨祖籍國(guó)，通過(guò)耳聞目睹，解決祖籍認(rèn)同問(wèn)題，恢復(fù)華族自信心，提高民族自豪感，進(jìn)而自覺(jué)地?fù)?dān)當(dāng)起華族優(yōu)秀文化學(xué)習(xí)和傳承的重任，做一個(gè)名副其實(shí)的華人。

xjv：j時(shí)段用電量是否在第v檔范圍，若在值為1，否則值為0，v∈[2，V]；

yijk：機(jī)器i加工工件k時(shí)是否在j時(shí)段進(jìn)行加工，若加工，值為1，否則值為0；

tijk：機(jī)器i加工工件k時(shí)在j時(shí)段加工時(shí)長(zhǎng)，當(dāng)=1時(shí)，值為pik，否則，說(shuō)明機(jī)器i跨時(shí)段加工工件k，需根據(jù)工件開始加工時(shí)間Sik、所需加工時(shí)長(zhǎng)Pik和所在時(shí)段j的上下限計(jì)算該時(shí)段內(nèi)的加工時(shí)長(zhǎng)。

本文采用連續(xù)時(shí)間建模，xjv與yijk為布爾變量，是為了便于確定加工時(shí)段用電量處于第幾檔電價(jià)和機(jī)器i加工工件k時(shí)在j時(shí)段的加工時(shí)間而引入的，因此，不考慮照明等日常用電，只考慮生產(chǎn)機(jī)器耗電，建立電力成本最小化的目標(biāo)函數(shù)如下：

考慮約束條件如下：

其中，（1）表示生產(chǎn)過(guò)程不被打斷，工件k在機(jī)器i上的開始時(shí)間加上加工時(shí)長(zhǎng)等于結(jié)束時(shí)間，保證生產(chǎn)的連續(xù)性；（2）表示同一工件同一時(shí)刻不能在不同的機(jī)床上加工，每件工件k在當(dāng)前機(jī)器i的結(jié)束加工時(shí)間小于在下一臺(tái)機(jī)器i+1的開始時(shí)間，同一工件的前道工序完成加工后才開始后一道工序；（3）表示同一時(shí)間一臺(tái)機(jī)器只能加工一個(gè)工件，每臺(tái)機(jī)器i加工當(dāng)前工件k的結(jié)束時(shí)間小于加工下一件工件k+1的開始時(shí)間，同一臺(tái)機(jī)器加工完上一件工件后才能加工下一件工件；（4）、（5）、（6）、（7）表示要在規(guī)定時(shí)間內(nèi)完成加工任務(wù)，開始加工時(shí)間和結(jié)束加工時(shí)間都必須在規(guī)劃時(shí)間內(nèi)。

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

考慮分時(shí)階梯電價(jià)的流水作業(yè)車間調(diào)度問(wèn)題具有較高的復(fù)雜性，從流水作業(yè)車間生產(chǎn)調(diào)度的角度分析，需要考慮多個(gè)工件的加工順序，并計(jì)算各工件每道工序的開始加工時(shí)間和完工時(shí)間；考慮分時(shí)階梯電價(jià)后，不僅需要考慮加工順序，更需要在規(guī)定的時(shí)間范圍內(nèi)針對(duì)各工件的開工時(shí)間進(jìn)行合理的錯(cuò)峰安排，才能最終確定各工件的開始加工時(shí)間，使得問(wèn)題更加復(fù)雜。因此，針對(duì)該問(wèn)題，本文采用具有強(qiáng)大全局尋優(yōu)能力的遺傳算法進(jìn)行求解。

3.1 編碼

考慮分時(shí)階梯電價(jià)的流水作業(yè)車間問(wèn)題需要考慮工件的加工順序和作業(yè)開始時(shí)間，因此采用實(shí)數(shù)編碼，將整條染色體分為兩部分：工序碼+時(shí)間碼，第一部分是工序碼，基于工件的加工順序進(jìn)行編碼，第二部分是時(shí)間碼，表示工件在每臺(tái)機(jī)器上的開始加工時(shí)間。

假設(shè)有4個(gè)代加工工件，每種工件有3道工序，對(duì)應(yīng)的有3臺(tái)機(jī)器可以進(jìn)行加工，設(shè)計(jì)一個(gè)可行解[3 3 3 2 2 2 1 1 1 4 4 4 | 0 5 11 5 11 18 6 13 21 7 15 24]，可行解分為兩部分，豎線前面的為工序碼，采取基于工序的編碼方式；豎線后面的為時(shí)間碼，表示與工序碼相對(duì)應(yīng)的開始加工時(shí)間。本文編碼設(shè)計(jì)將工序碼和時(shí)間碼結(jié)合起來(lái)，工序碼確定工件的加工順序，時(shí)間碼確定機(jī)器開始加工時(shí)間，方便統(tǒng)計(jì)機(jī)器在某個(gè)時(shí)段內(nèi)的加工時(shí)間和電力需求。

3.2 初始種群產(chǎn)生

圖2 染色體工序碼交叉操作

初始種群產(chǎn)生，在產(chǎn)生能在規(guī)定時(shí)間內(nèi)的工序碼后，時(shí)間碼有兩種產(chǎn)生方式，前50%的種群采取完工時(shí)間盡可能短的方案，首件工件的首道工序從計(jì)劃開始時(shí)間加工；后50%的種群采取完工時(shí)間盡可能長(zhǎng)的方案，末件工件的末道工序在計(jì)劃結(jié)束時(shí)間完工。兩種不同的時(shí)間碼產(chǎn)生方式，保證種群時(shí)間碼的多樣性。

3.3 交叉算子

交叉算子分為兩種，針對(duì)工序碼的交叉采用POX（precedence operation crossover）交叉算子，POX交叉算子可以很好的保留父代優(yōu)良特征，繼承父代的加工順序，并且保證子代的可行性，如圖2所示；針對(duì)時(shí)間碼的交叉采用兩點(diǎn)交叉，隨機(jī)選中兩點(diǎn)，互換兩點(diǎn)之間的部分，時(shí)間碼交叉后可行性不易保證，因此采用后期修復(fù)的方法，保證子代的可行性。

3.4 變異算子

變異算子分為兩部分，第一部分對(duì)基于工序的工序碼變異，第二部分是針對(duì)時(shí)間碼變異，本文采用兩點(diǎn)互換操作，在相應(yīng)部分任意選擇兩個(gè)互換點(diǎn)，然后互換對(duì)應(yīng)位置的編碼，并對(duì)時(shí)間碼進(jìn)行修復(fù)，此變異操作方法可以保證編碼的合法性。

3.5 選擇算子

選擇算子需要將本代種群中適應(yīng)值較高的染色體保留到下一代以保證種群朝著更優(yōu)的方向進(jìn)化，本文編碼包含工序碼和時(shí)間碼，因此以目標(biāo)函數(shù)電力成本的倒數(shù)作為適應(yīng)度函數(shù)，采用輪盤賭法進(jìn)行選擇，保證符合要求的染色體可以保留到下一代。

3.6 算法流程

因?yàn)榫幋a包含了基于工序的工序碼和工序開始加工時(shí)間的時(shí)間碼，因此算法分為兩部分，首先是工序碼的迭代，在工序碼能保證在規(guī)定時(shí)間內(nèi)完成任務(wù)后，再對(duì)時(shí)間碼進(jìn)行迭代，促使電力成本最低。因此，設(shè)計(jì)算法流程圖如圖3所示。

4 實(shí)例分析

圖3 算法流程圖

針對(duì)某考慮分時(shí)階梯電價(jià)的流水車間調(diào)度問(wèn)題：某車橋加工車間共有6臺(tái)機(jī)器，現(xiàn)有4種工件，每種各5件，共20件工件需要加工，計(jì)劃從早上7點(diǎn)開始加工，要求40個(gè)小時(shí)內(nèi)完成加工任務(wù)（包括一個(gè)低谷時(shí)段，四個(gè)平峰時(shí)段，四個(gè)高峰時(shí)段）。每種類型工件的加工時(shí)間和功率需求如表1所示。

表1 各機(jī)器加工時(shí)間及功率

參考現(xiàn)行的陜西省分時(shí)電價(jià)和居民階梯電價(jià)，假設(shè)每個(gè)時(shí)段有兩檔電價(jià)，構(gòu)建本文的分時(shí)階梯電價(jià)模型。第一檔為正常用電，第二檔為高標(biāo)準(zhǔn)用電，假設(shè)每時(shí)段電力價(jià)格如表2所示。

表2 分時(shí)階梯電價(jià)時(shí)段及價(jià)格表

分時(shí)階梯電價(jià)的分界點(diǎn)根據(jù)每天峰平谷三個(gè)時(shí)段的長(zhǎng)度確定，取高峰段，平段，低谷時(shí)段用電量第二檔電價(jià)分界點(diǎn)分別為750千瓦時(shí)/天、850千瓦時(shí)/天、800千瓦時(shí)/天。

在考慮分時(shí)階梯電價(jià)下，本文以電力成本最小化為目標(biāo)，設(shè)置種群規(guī)模為50，種群迭代次數(shù)為600，時(shí)間碼迭代次數(shù)為300。迭代10次得到最優(yōu)調(diào)度方案甘特圖如圖4所示，同時(shí)以最小最大完工時(shí)間為目標(biāo)作為對(duì)照組，得到最優(yōu)調(diào)度方案甘特圖如圖5所示。對(duì)比兩組的電力成本如表3所示。

圖4 以電力成本最小化為目標(biāo)的最優(yōu)調(diào)度方案甘特圖

圖5 以最小最大完工時(shí)間為目標(biāo)的最優(yōu)調(diào)度方案甘特圖

表3 考慮不同目標(biāo)的調(diào)度結(jié)果對(duì)比

從圖4中可以看出，考慮分時(shí)階梯電價(jià)的生產(chǎn)調(diào)度可以在規(guī)定的時(shí)間內(nèi)完成加工任務(wù)并有效的進(jìn)行錯(cuò)峰生產(chǎn)，從表3的對(duì)比數(shù)據(jù)中可以看出，考慮分時(shí)階梯電價(jià)的情況下，以本文所建立出的模型，求解出的調(diào)度方案使得電力成本降低了34%，有效的降低生產(chǎn)所需的能耗。

5 結(jié)語(yǔ)

本文綜合考慮了分時(shí)電價(jià)和階梯電價(jià)，針對(duì)流水車間調(diào)度問(wèn)題建立了數(shù)學(xué)模型，并針對(duì)建立的數(shù)學(xué)模型設(shè)計(jì)了基于工序編碼和時(shí)間編碼的遺傳算法，最后以實(shí)例驗(yàn)證了該問(wèn)題數(shù)學(xué)模型的正確性和求解算法的有效性。結(jié)果表明，在分時(shí)階梯電價(jià)下，以最小化電力成本為目標(biāo)，進(jìn)行生產(chǎn)調(diào)度決策，可以有效的進(jìn)行錯(cuò)峰生產(chǎn)，顯著的降低電力成本。本文只考慮了工件加工過(guò)程中的能耗，在未來(lái)的研究中，將考慮加入非加工過(guò)程產(chǎn)生的能耗，如等待能耗，開關(guān)機(jī)能耗等，進(jìn)一步提高問(wèn)題的實(shí)際意義。