閆建濤，肖繼明

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

0 引言

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

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

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

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

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

1 問題描述

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

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

圖1 分時階梯電價示意圖

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

2 模型建立

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

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

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

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

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

k：工件編號，k∈[1，n] ；

j：加工時段編號，j∈[1，s]；

Ej：加工時段j的耗電量；

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

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

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

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

Emax：最大完工時間；

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

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

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

Pjv：j時段的第v檔電價，v∈[1，V]；

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

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

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

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

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

考慮約束條件如下：

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

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

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

3.1 編碼

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

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

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

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

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

3.3 交叉算子

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

3.4 變異算子

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

3.5 選擇算子

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

3.6 算法流程

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

4 實(shí)例分析

圖3 算法流程圖

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

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

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

表2 分時階梯電價時段及價格表

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

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

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

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

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

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

5 結(jié)語

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