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

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

SCIENCE CHINA PRESS

tech.scichina.com

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

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

①

①

②

①

① 西安交通大學(xué)系統(tǒng)工程研究所, 機(jī)械制造系統(tǒng)工程國家重點(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

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

摘要 “即時消費(fèi)”類生產(chǎn)制造系統(tǒng)的優(yōu)化調(diào)度具有重要學(xué)術(shù)和應(yīng)用價值. 滿足此類系統(tǒng)對產(chǎn)量的實(shí)時需求, 考慮調(diào)度計劃的可實(shí)現(xiàn)性具有挑戰(zhàn)性. 如何得到精確滿足累積產(chǎn)量實(shí)時需求的最優(yōu)調(diào)度目前尚無系統(tǒng)方法, 迫切需要研究. 本文建立了含積分約束的生產(chǎn)制造系統(tǒng)優(yōu)化調(diào)度新模型. 通過對生產(chǎn)量變化率約束的深入分析, 證明了該類優(yōu)化問題等價于光滑非線性規(guī)劃問題. 生產(chǎn)設(shè)備在各時段的產(chǎn)量上下界可表述為時段初、末時刻瞬時生產(chǎn)率的二元函數(shù), 且為精確可達(dá)的上下界. 本文結(jié)合梯度映射的單調(diào)性, 證明了上下界函數(shù)的凸性(凹性), 在生產(chǎn)成本為凸函數(shù)時, 進(jìn)一步證明了此類優(yōu)化調(diào)度問題等價于凸規(guī)劃問題. 本文以上述分析為基礎(chǔ), 針對含積分約束的生產(chǎn)制造系統(tǒng)優(yōu)化調(diào)度問題, 提出了兩階段數(shù)值求解方法, 在許多情況下可以迅速獲得調(diào)度問題的全局最優(yōu)解. 新模型和相應(yīng)求解方法克服了生產(chǎn)量變化率約束帶來的困難, 獲得了精確滿足累積產(chǎn)量實(shí)時需求的最優(yōu)調(diào)度. 本文同時以電力生產(chǎn)優(yōu)化調(diào)度問題為例, 進(jìn)行數(shù)值求解, 并對結(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)度能夠在不改變基本工藝過程、不更動裝備的情況下實(shí)現(xiàn)節(jié)能降耗, 降低成本, 獲得巨大的社會經(jīng)濟(jì)效益, 在當(dāng)前能源、環(huán)境問題日趨嚴(yán)峻的形勢下, 具有特別重大的意義. 因此, 生產(chǎn)調(diào)度理論與方法長期以來一直是一個活躍的研究領(lǐng)域, 受到眾多學(xué)者關(guān)注[1~6].

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

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

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

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

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

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

42

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

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

1 積分約束的必要性舉例

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

某臺發(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ā)電計劃.

如果按傳統(tǒng)模型, g(1), g(2)表示第1和2 h內(nèi)機(jī)組的平均發(fā)電功率(單位: MW). 如每個離散調(diào)度時段長度為1 h, g(1), g(2)在數(shù)值上等于機(jī)組在對應(yīng)時段的發(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)無法達(dá)到450 MWh, 見圖1所示.

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

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

因機(jī)組在第1 h末發(fā)電功率為150 MW, 對應(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, 對應(yīng)圖中C點(diǎn), 此后

保持不變. 因此機(jī)組在第2 h內(nèi)最大可實(shí)現(xiàn)的發(fā)電量為五邊形 ACDFE 的面積, 對應(yīng)為 325 MWh, 遠(yuǎn)低于450 MWh(對應(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)度模型

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

gi(t)dt, (4)

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

i j k

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

第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時段允許消耗的第j種原料總量; 連續(xù)時間變量, 從0時刻開始計時, 調(diào)度周期總時間長度為K?τ;

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

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

設(shè)備i在第k時段的生產(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)度初始及終止時刻生產(chǎn)率約束:

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

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