中國科學: 技術科學 2010年 第40卷 第1期: 41 ~ 51

《中國科學》雜志社

SCIENCE CHINA PRESS

tech.scichina.com

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

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

①

①

②

①

① 西安交通大學系統(tǒng)工程研究所, 機械制造系統(tǒng)工程國家重點實驗室, 智能網絡與網絡安全教育部重點實驗室, 西安 710049; ② 西安交通大學理學院, 西安 710049 * E-mail: qzzhai@sei.xjtu.edu.cn

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

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

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

關鍵詞 生產調度 積分約束 最優(yōu)控制 凸規(guī)劃

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

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

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

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

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

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

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

應該指出, 本文提出的模型和求解方法可以推

42

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

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

1 積分約束的必要性舉例

我們以電力生產調度的簡單例子, 說明積分約束的必要性.

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

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

150≤g(2)≤450,

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

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

中國科學: 技術科學 2010年 第40卷 第1期

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

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

i=1

I

(b) 原料限制:

I

處達到最大發(fā)電功率450 MW, 對應圖中C點, 此后

保持不變. 因此機組在第2 h內最大可實現的發(fā)電量為五邊形 ACDFE 的面積, 對應為 325 MWh, 遠低于450 MWh(對應于矩形 BDFE 的面積). 因此, 如果要進行電量的調度, 應該考慮發(fā)電功率的積分和相應的約束.

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

i=1

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

(c) 產量-生產率關系:

pi(k)=∫

kτ(k?1)τ

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

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

gi(t)dt, (4)

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

i j k

設備編號,i=1,2,",I; 生產原料編號, j=1,2,",J; 調度時段編號, k=1,2,",K; 每個調度時段的時間長度;

第i臺設備生產每單位的產品, 需消耗的第j種原料量;

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

i,gi

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

(d) 生產率-生產率變化率關系:

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

0t

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

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

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

τ aj,i

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

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

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

設備i在第k時段的生產量; 設備i的生產率變化率上限; 設備i的最大、最小生產率;

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

(f) 生產率界約束:

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

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

(g) 調度初始及終止時刻生產率約束:

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

其中gi?,0和gi?,K是給定常數. 該組約束中的后一個可