中國(guó)科學(xué): 技術(shù)科學(xué) 2010年 第40卷 第1期: 41 ~ 51

《中國(guó)科學(xué)》雜志社

SCIENCE CHINA PRESS

tech.scichina.com

一類含積分約束的生產(chǎn)制造系統(tǒng)優(yōu)化調(diào)度

管曉宏, 翟橋柱*, 馮泳翰, 高峰

①

①

②

①

① 西安交通大學(xué)系統(tǒng)工程研究所, 機(jī)械制造系統(tǒng)工程國(guó)家重點(diǎn)實(shí)驗(yàn)室, 智能網(wǎng)絡(luò)與網(wǎng)絡(luò)安全教育部重點(diǎn)實(shí)驗(yàn)室, 西安 710049; ② 西安交通大學(xué)理學(xué)院, 西安 710049 * E-mail: qzzhai@sei.xjtu.edu.cn

收稿日期: 2009-04-21; 接受日期: 2009-08-03

國(guó)家自然科學(xué)基金(批準(zhǔn)號(hào): 60704033, 60736027)、國(guó)家高技術(shù)研究發(fā)展計(jì)劃(“863”計(jì)劃)(批準(zhǔn)號(hào): 2007AA04Z154)和教育部新世紀(jì)優(yōu)秀人才計(jì)劃(批準(zhǔn)號(hào): NCET-08-0432)資助項(xiàng)目

摘要 “即時(shí)消費(fèi)”類生產(chǎn)制造系統(tǒng)的優(yōu)化調(diào)度具有重要學(xué)術(shù)和應(yīng)用價(jià)值. 滿足此類系統(tǒng)對(duì)產(chǎn)量的實(shí)時(shí)需求, 考慮調(diào)度計(jì)劃的可實(shí)現(xiàn)性具有挑戰(zhàn)性. 如何得到精確滿足累積產(chǎn)量實(shí)時(shí)需求的最優(yōu)調(diào)度目前尚無(wú)系統(tǒng)方法, 迫切需要研究. 本文建立了含積分約束的生產(chǎn)制造系統(tǒng)優(yōu)化調(diào)度新模型. 通過對(duì)生產(chǎn)量變化率約束的深入分析, 證明了該類優(yōu)化問題等價(jià)于光滑非線性規(guī)劃問題. 生產(chǎn)設(shè)備在各時(shí)段的產(chǎn)量上下界可表述為時(shí)段初、末時(shí)刻瞬時(shí)生產(chǎn)率的二元函數(shù), 且為精確可達(dá)的上下界. 本文結(jié)合梯度映射的單調(diào)性, 證明了上下界函數(shù)的凸性(凹性), 在生產(chǎn)成本為凸函數(shù)時(shí), 進(jìn)一步證明了此類優(yōu)化調(diào)度問題等價(jià)于凸規(guī)劃問題. 本文以上述分析為基礎(chǔ), 針對(duì)含積分約束的生產(chǎn)制造系統(tǒng)優(yōu)化調(diào)度問題, 提出了兩階段數(shù)值求解方法, 在許多情況下可以迅速獲得調(diào)度問題的全局最優(yōu)解. 新模型和相應(yīng)求解方法克服了生產(chǎn)量變化率約束帶來的困難, 獲得了精確滿足累積產(chǎn)量實(shí)時(shí)需求的最優(yōu)調(diào)度. 本文同時(shí)以電力生產(chǎn)優(yōu)化調(diào)度問題為例, 進(jìn)行數(shù)值求解, 并對(duì)結(jié)果進(jìn)行了討論, 驗(yàn)證了新模型和相應(yīng)方法的有效性.

關(guān)鍵詞 生產(chǎn)調(diào)度 積分約束 最優(yōu)控制 凸規(guī)劃

生產(chǎn)調(diào)度是生產(chǎn)制造系統(tǒng)運(yùn)行最重要的任務(wù)之一. 通常, 調(diào)度的主要目的是合理調(diào)配資源和設(shè)備, 在滿足需求、確保安全等運(yùn)行約束的前提下降低成本、節(jié)約資源、減少污染. 優(yōu)化生產(chǎn)調(diào)度能夠在不改變基本工藝過程、不更動(dòng)裝備的情況下實(shí)現(xiàn)節(jié)能降耗, 降低成本, 獲得巨大的社會(huì)經(jīng)濟(jì)效益, 在當(dāng)前能源、環(huán)境問題日趨嚴(yán)峻的形勢(shì)下, 具有特別重大的意義. 因此, 生產(chǎn)調(diào)度理論與方法長(zhǎng)期以來一直是一個(gè)活躍的研究領(lǐng)域, 受到眾多學(xué)者關(guān)注[1~6].

在生產(chǎn)制造系統(tǒng)中, 有一類生產(chǎn)所謂不可存儲(chǔ)產(chǎn)品, 即“即時(shí)消費(fèi)”或“鮮活”(Perishable)類產(chǎn)品的系統(tǒng)[1], 其顯著特點(diǎn)是產(chǎn)品必須立即消費(fèi)而不能存儲(chǔ), 最

典型的例子是電力生產(chǎn). 在電力生產(chǎn)調(diào)度問題中[7,8], 每個(gè)瞬時(shí)生產(chǎn)的電量必須與系統(tǒng)負(fù)載需求保持平衡. 其它類似的系統(tǒng)包括管道輸送天然氣生產(chǎn)和許多服務(wù)業(yè)的即時(shí)服務(wù)等. 這類系統(tǒng)的優(yōu)化調(diào)度問題不但會(huì)有實(shí)時(shí)系統(tǒng)需求等, 還可能有十分復(fù)雜的離散和連續(xù)的動(dòng)態(tài)運(yùn)行約束, 幾乎不可能按連續(xù)時(shí)間求解. 目前廣泛采用的建模方式是將時(shí)間離散化, 在一個(gè)調(diào)度時(shí)段內(nèi), 假設(shè)系統(tǒng)需求為恒定值, 用生產(chǎn)設(shè)備的平均生產(chǎn)量滿足這一時(shí)段恒定的需求. 將平均生產(chǎn)量作為優(yōu)化決策變量, 求解離散時(shí)間點(diǎn)的生產(chǎn)量, 可將調(diào)度問題由連續(xù)時(shí)間最優(yōu)控制問題轉(zhuǎn)化為數(shù)學(xué)規(guī)劃問題, 從而大大降低問題的復(fù)雜性[2,7~10].

引用格式: Guan X H, Zhai Q Z, Feng Y H, et al. Optimization based scheduling for a class of production systems with integral constraints. Sci China Ser E-Tech Sci,

2009, 52(12): 3533?3544, doi: 10.1007/s11431-009-0359-y

管曉宏等: 一類含積分約束的生產(chǎn)制造系統(tǒng)優(yōu)化調(diào)度

時(shí)間離散化的生產(chǎn)制造系統(tǒng)優(yōu)化調(diào)度問題一般模型為整數(shù)規(guī)劃或混合規(guī)劃問題, 國(guó)內(nèi)外研究者對(duì)此類問題進(jìn)行了大量研究[2~19], 取得了許多重要成果. 基于Lagrange松弛的優(yōu)化方法是解決此類問題最有效的方法之一[3,5,9,11]. 近年來, 隨著通用整數(shù)規(guī)劃或混合規(guī)劃算法效率和計(jì)算機(jī)性能的大幅度提高, 通用離散和混合優(yōu)化方法求解此類生產(chǎn)制造系統(tǒng)優(yōu)化調(diào)度問題也取得了很大成功[10,12~14].

由于滿足“即時(shí)消費(fèi)”類生產(chǎn)制造系統(tǒng)的實(shí)時(shí)需求是對(duì)調(diào)度計(jì)劃的基本要求, 按離散時(shí)間模型獲得的調(diào)度方案的可實(shí)現(xiàn)性就十分重要. 許多生產(chǎn)設(shè)備產(chǎn)量的變化率受物理限制, 如發(fā)電機(jī)組出力的爬升率有限, 不可能每個(gè)時(shí)間段起點(diǎn)突變, 完全按上述離散時(shí)間模型得到的調(diào)度計(jì)劃不可能操作實(shí)現(xiàn), 也不一定有必要. 實(shí)際上很多情況下, 我們只要求這類生產(chǎn)系統(tǒng)在一個(gè)時(shí)段內(nèi)的累積產(chǎn)量, 即生產(chǎn)率對(duì)時(shí)間的積分精確等于實(shí)時(shí)需求. 例如電力生產(chǎn)系統(tǒng)的生產(chǎn)率是出力(功率), 我們只要求系統(tǒng)在一個(gè)時(shí)段內(nèi)交付的能量(功率的積分)滿足實(shí)時(shí)需求. 然而, 在復(fù)雜調(diào)度問題中“不多不少”精確滿足累積產(chǎn)量的實(shí)時(shí)需求絕非易事. 我們?cè)谇捌诠ぷ髦性敿?xì)闡述了電力生產(chǎn)中離散時(shí)間最優(yōu)調(diào)度即使?jié)M足出力爬升約束, 也可能存在能量不可交付性, 并給出了判定能量可交付性或調(diào)度計(jì)劃可實(shí)現(xiàn)性的充分必要條件[16]. 然而, 如何取得精確滿足累積產(chǎn)量實(shí)時(shí)需求的最優(yōu)調(diào)度目前還沒有答案, 迫切需要研究.

本文建立了含積分約束的生產(chǎn)制造系統(tǒng)優(yōu)化調(diào)度新模型. 通過對(duì)生產(chǎn)量變化率約束的深入分析, 證明了該類優(yōu)化問題等價(jià)于光滑的非線性規(guī)劃問題. 生產(chǎn)設(shè)備在各時(shí)段的產(chǎn)量上下界可表述為時(shí)段初、末時(shí)刻瞬時(shí)生產(chǎn)率的二元函數(shù), 且為精確可達(dá)的上下界. 本文結(jié)合梯度映射的單調(diào)性, 證明了上下界函數(shù)的凸性(凹性), 在生產(chǎn)成本為凸函數(shù)時(shí)進(jìn)一步證明了此類優(yōu)化調(diào)度問題等價(jià)于凸規(guī)劃問題. 本文以上述分析為基礎(chǔ), 針對(duì)含積分約束的生產(chǎn)制造系統(tǒng)優(yōu)化調(diào)度問題, 提出了兩階段數(shù)值求解方法, 在許多情況下可以迅速獲得全局最優(yōu)解. 新模型和相應(yīng)求解方法克服了生產(chǎn)量變化率約束帶來的困難, 獲得了精確滿足累積產(chǎn)量實(shí)時(shí)需求的最優(yōu)調(diào)度. 本文以電力生產(chǎn)優(yōu)化調(diào)度問題為例, 進(jìn)行了數(shù)值求解, 并對(duì)結(jié)果進(jìn)行了討論, 進(jìn)而驗(yàn)證了新模型和相應(yīng)方法的有效性.

應(yīng)該指出, 本文提出的模型和求解方法可以推

42

廣到求解有庫(kù)存或存儲(chǔ)的生產(chǎn)系統(tǒng)調(diào)度問題[2]. 限于篇幅, 此類問題未在本文中討論.

本文結(jié)構(gòu)安排如下: 第1節(jié)用一個(gè)簡(jiǎn)單例子說明了目前文獻(xiàn)中通用的建模方式存在的缺陷; 第2節(jié)給出了按連續(xù)時(shí)間方式表述生產(chǎn)率及產(chǎn)量積分約束的精確調(diào)度模型; 第3節(jié)對(duì)模型的約束結(jié)構(gòu)特征, 尤其是積分約束的結(jié)構(gòu)特征進(jìn)行了深入分析, 得到了一些重要理論結(jié)果; 第4節(jié)證明了新模型等價(jià)于一個(gè)可行域?yàn)殚]凸集的光滑非線性規(guī)劃問題, 特別當(dāng)生產(chǎn)成本為凸函數(shù)時(shí)進(jìn)一步等價(jià)于一個(gè)簡(jiǎn)單的凸規(guī)劃問題, 提出了兩階段數(shù)值求解框架; 第5節(jié)以電力生產(chǎn)優(yōu)化調(diào)度問題為例驗(yàn)證了本文提出的有關(guān)理論和方法; 第6節(jié)對(duì)全文進(jìn)行了總結(jié).

1 積分約束的必要性舉例

我們以電力生產(chǎn)調(diào)度的簡(jiǎn)單例子, 說明積分約束的必要性.

某臺(tái)發(fā)電機(jī)組最小發(fā)電功率為150 MW, 最大發(fā)電功率為450 MW, 最大爬升速率為6 MW/min, 假定第1 h內(nèi)的發(fā)電功率恒定為g(1) = 150 MW, 現(xiàn)確定第2 h的發(fā)電計(jì)劃.

如果按傳統(tǒng)模型, g(1), g(2)表示第1和2 h內(nèi)機(jī)組的平均發(fā)電功率(單位: MW). 如每個(gè)離散調(diào)度時(shí)段長(zhǎng)度為1 h, g(1), g(2)在數(shù)值上等于機(jī)組在對(duì)應(yīng)時(shí)段的發(fā)電量或產(chǎn)出的能量(單位: MWh), 并滿足以下約束:

150≤g(2)≤450,

g(2)?g(1)≤6×60=360.顯然在滿足上述約束的情況下, g(2)的最大取值為g(2) = 450 MW. 然而, 容易說明機(jī)組在第2 h內(nèi)的最大發(fā)電量或能量遠(yuǎn)遠(yuǎn)無(wú)法達(dá)到450 MWh, 見圖1所示.

圖1 機(jī)組發(fā)電功率與電量

中國(guó)科學(xué): 技術(shù)科學(xué) 2010年 第40卷 第1期

因機(jī)組在第1 h末發(fā)電功率為150 MW, 對(duì)應(yīng)于圖1中A點(diǎn), 由于爬升速率有限, 發(fā)電功率不可能在第2 h初突變, 即便按最大爬升速率上升, 至多在1 h 50 min

k=1,2,",K; (2) ∑pi(k)=D(k),

i=1

I

(b) 原料限制:

I

處達(dá)到最大發(fā)電功率450 MW, 對(duì)應(yīng)圖中C點(diǎn), 此后

保持不變. 因此機(jī)組在第2 h內(nèi)最大可實(shí)現(xiàn)的發(fā)電量為五邊形 ACDFE 的面積, 對(duì)應(yīng)為 325 MWh, 遠(yuǎn)低于450 MWh(對(duì)應(yīng)于矩形 BDFE 的面積). 因此, 如果要進(jìn)行電量的調(diào)度, 應(yīng)該考慮發(fā)電功率的積分和相應(yīng)的約束.

∑aj,ipi(k)≤Rj,k, (3)

i=1

其中j=1,2,",J, k=1,2,",K. 約束(3)具有通用性, 可以表示許多形式的約束, 除原料限制約束外, 還可表示電力生產(chǎn)調(diào)度中的系統(tǒng)備用約束、傳輸容量約束(均可視為廣義的原料限制約束)等.

(c) 產(chǎn)量-生產(chǎn)率關(guān)系:

pi(k)=∫

kτ(k?1)τ

2 含積分約束生產(chǎn)制造系統(tǒng)優(yōu)化調(diào)度模型

考慮一個(gè)生產(chǎn)制造系統(tǒng)有I臺(tái)生產(chǎn)設(shè)備, 生產(chǎn)過

gi(t)dt, (4)

程需消耗J種原料、調(diào)度周期為K時(shí)段. 本文采用的變量和符號(hào)定義及說明如下:

i j k

設(shè)備編號(hào),i=1,2,",I; 生產(chǎn)原料編號(hào), j=1,2,",J; 調(diào)度時(shí)段編號(hào), k=1,2,",K; 每個(gè)調(diào)度時(shí)段的時(shí)間長(zhǎng)度;

第i臺(tái)設(shè)備生產(chǎn)每單位的產(chǎn)品, 需消耗的第j種原料量;

Rj,k t gi(t) ui(t) pi(k) Δi

i,gi

其中i=1,2,",I, k=1,2,",K.

(d) 生產(chǎn)率-生產(chǎn)率變化率關(guān)系:

gi(t)=gi(0)+∫ui(ξ)dξ,?t∈[0,Kτ], (5)

0t

其中i=1,2,",I. 在本文考慮的調(diào)度問題中, ui(t)為決策變量, gi(t)和pi(k)為狀態(tài)變量.

(e) 生產(chǎn)率變化率界約束(生產(chǎn)率爬升約束):

?Δi≤ui(t)≤Δi,?t∈[0,Kτ], (6)

τ aj,i

第k時(shí)段允許消耗的第j種原料總量; 連續(xù)時(shí)間變量, 從0時(shí)刻開始計(jì)時(shí), 調(diào)度周期總時(shí)間長(zhǎng)度為K?τ;

設(shè)備i在t時(shí)刻的生產(chǎn)率, 是時(shí)間的連續(xù)函數(shù);

設(shè)備i在t時(shí)刻的生產(chǎn)率變化率, ui(t)是分段連續(xù)函數(shù);

設(shè)備i在第k時(shí)段的生產(chǎn)量; 設(shè)備i的生產(chǎn)率變化率上限; 設(shè)備i的最大、最小生產(chǎn)率;

其中i=1,2,",I.

(f) 生產(chǎn)率界約束:

gi≤gi(t)≤i,?t∈[0,Kτ], (7)

其中i=1,2,",I.

(g) 調(diào)度初始及終止時(shí)刻生產(chǎn)率約束:

gi(0)=gi?,0,gi(Kτ)=gi?,K, (8)

其中g(shù)i?,0和gi?,K是給定常數(shù). 該組約束中的后一個(gè)可