選, 某些系統(tǒng)可能不需要.

由(1)~(8)式描述的具有實際背景的生產(chǎn)制造系Ci(pi(k)) 設(shè)備i在第k時段生產(chǎn)量為pi(k)時的生

統(tǒng)優(yōu)化調(diào)度問題十分復(fù)雜, 既包括了離散時間約束, 產(chǎn)成本, 假定成本僅與生產(chǎn)量有關(guān);

也包括了連續(xù)時間積分關(guān)系, 難以直接應(yīng)用現(xiàn)有的D(k) 第k時段的總需求或合同供貨量.

非線性規(guī)劃或最優(yōu)控制理論求解, 本文通過深入研

本文考慮的生產(chǎn)調(diào)度可描述為以下優(yōu)化問題.

究約束(4)~(7)及目標(biāo)函數(shù)(1)的結(jié)構(gòu)特征, 找到了將

目標(biāo): 生產(chǎn)成本最小

此類調(diào)度問題轉(zhuǎn)化為光滑凸規(guī)劃問題的系統(tǒng)方法.

IK

minJ=∑∑Ci(pi(k)). (1) 受篇幅限制, 模型(1)~(8)中未引入描述設(shè)備開

ui(t),gi(t),pi(k)

i=1k=1關(guān)機狀態(tài)的離散決策變量和約束. 作者已結(jié)合本文

約束條件: 的理論結(jié)果和前期研究成果[9], 在上述模型中考慮了

(a) 即時產(chǎn)需平衡: 離散決策變量和約束, 將在以后報告.

43

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

3 問題轉(zhuǎn)化為光滑凸規(guī)劃的理論基礎(chǔ)

(14)式中的兩式相減可得:

gi,k?gi,k?1=∫

kτ(k?1)τ

本節(jié)給出將問題(1)~(8)轉(zhuǎn)化為光滑凸規(guī)劃的理論基礎(chǔ). 為使表述簡潔, 引入下述符號:

gi,k=gi(kτ),k=0,1,2,",K,i=1,2,",I, (9)

ui(ξ)dξ, (15)

再根據(jù)(6)式, 結(jié)合(15)式即可得(10)式, 結(jié)論(i)因此成立.

(ii) 當(dāng)t∈[(k?1)τ,kτ]時, 對比約束(5)和(6)式, 可得如下結(jié)論:

gi(t)=gi,k?1+∫

t(k?1)τt(k?1)τ

表示設(shè)備i在kτ時刻的瞬時生產(chǎn)率.

首先, 可以證明單臺生產(chǎn)設(shè)備在各時段的產(chǎn)量上下限可表示為該設(shè)備在相應(yīng)時段初、末時刻生產(chǎn)率的二元函數(shù).

定理 1. 設(shè) pi(k), gi(t), ui(t)滿足約束(4)~(7), 則有下述結(jié)論成立:

(i)

ui(ξ)dξΔidξ

≥gi,k?1?∫

(16)

gi,k?gi,k?1≤Δiτ; (10)

=gi,k?1?Δi(t?(k?1)τ),

kτtkτt

(ii) (gi,k?1,gi,k)≤pi(k)≤i(gi,k?1,gi,k). (11) (11)式中的產(chǎn)量上下限二元函數(shù)i(?,?)和i(?,?)解析表達(dá)式如下:

P(gi,k?1,gi,k)=

?(gi,k?1?g)2+(gi,k?g)2

i?+gi?τ,2Δ?i

?

ifgi,k?1+gi,k<2gi+Δiτ, ?

?2

?(gi,k?1?gi,k)τΔ

+?(gi,k?1+gi,k)?i?τ2,?

4Δi24?

?ifgi,k?1+gi,k≥2gi+Δiτ,(12)?

i(gi,k?1,gi,k)=

?(i?gi,k?1)2+(i?gi,k)2

+i?τ,??

2Δ?i

?ifgi,k?1+gi,k≥2i?Δiτ, ??2

Δ?(gi,k?1?gi,k)τ

+?(gi,k?1+gi,k)+i?τ2,??4Δi24?

?ifgi,k?1+gi,k<2i?Δiτ.(13)?

gi(t)=gi,k?∫

≥gi,k?∫

ui(ξ)dξ

Δids=gk?Δi(kτ?t),

(17)

因此結(jié)合(7)式可知, 當(dāng)t∈[(k?1)τ,kτ]時下式成立:

gi(t)≥gimin,k(t)

=max{gi,k?1?Δi(t?(k?1)τ),gi,k?Δi(kτ?t),g}, (18)

上式右端給出的gimin,k(t)實際上是在給定第k時段初、末時刻生產(chǎn)率為gi,k?1和gi,k的前提下, 在第k時段設(shè)備i的最低可達(dá)生產(chǎn)率曲線. 根據(jù)產(chǎn)量-生產(chǎn)率積分關(guān)系約束(4)式, 從而得到: pi(k)=∫

k?τ(k?1)?τ

k?τ(k?1)?τ

gi(t)dt≥∫

gimin,k(t)dt

(iii) (11)式給出的pi(k)的上下界是可以達(dá)到的, 即分別存在適當(dāng)?shù)纳�產(chǎn)率函數(shù)gi(t)和生產(chǎn)率變化率函數(shù)ui(t)使得(11)式中的兩個不等式成為等式.

證明:

(i) 在(5)式中分別令t=(k?1)τ和t=kτ可得:

?(gi,k?1?g)2+(gi,k?g)2

i?+g?τ,2Δi?

?

ifgi,k?1+gi,k<2gi+Δiτ,?

=?

2

?(gi,k?1?gi,k)τΔ

+?(gi,k?1+gi,k)?i?τ2,?

4Δi24?

?(19)ifgi,k?1+gi,k≥2gi+Δiτ.?

(19)式的結(jié)果基于(18)式, 通過圖2中最左邊一列的兩幅圖(最小可達(dá)生產(chǎn)率曲線)能夠更好說明. 圖2中

的Case 1和Case 2分別對應(yīng)于(19)式中的第一種情況(k?1)τ?

gi,k?1=gi((k?1)τ)=gi(0)+∫ui(ξ)dξ,?和第二種情況. 0?

(14) ?

kτ基于完全類似的推理分析, 可以得到當(dāng)t∈

?g=g(kτ)=g(0)+u(ξ)dξ,i,kii∫0i?[(k?1)τ,kτ]時有下式成立: ?

44

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

圖2 設(shè)備i在時段k的最低/最高可達(dá)生產(chǎn)率曲線及其對應(yīng)的生產(chǎn)爬升率

gi(t)≤gimax,k(t)

=min{gi,k?1+Δi(t?(k?1)τ), (gi,k+Δikτ?t),i}, (20)

將變?yōu)榈忍? 本文僅指出對應(yīng)于圖2中與gimin,k(t)對應(yīng)

上式右端給出的gimax,k(t)實際上是在給定第k時段初、末時刻設(shè)備生產(chǎn)率為gi,k?1和gi,k的前提下, 在第k時段設(shè)備i的最高可達(dá)生產(chǎn)率曲線. 根據(jù)產(chǎn)量-生產(chǎn)率積分關(guān)系式(4), 得到:

pi(k)=∫

k?τ(k?1)?τ

的Case 1情況下, ui(t)與gi(t)的對應(yīng)關(guān)系, 其余情況完全類似.

在所考慮的情況下有下式成立:

gi,k?1+gi,k<2gi+Δiτ, (22)

此時有: t∈[(k?1)τ,kτ]時

?gi,k?1?Δi(t?(k?1)τ), if(k?1)τ≤t≤tk,1,??

gimin(t)=?gi, iftk,1≤t≤tk,2,,k

???gi,k?Δi(kτ?t), iftk,2≤t≤kτ,

(23)

其中的tk,1, tk,2由下式得到:

gi(t)dt≤∫

k?τ(k?1)?τ

gimax,k(t)dt

?(i?gi,k?1)2+(i?gi,k)2

+i?τ,??

2Δi?

?ifgi,k?1+gi,k≥2i?Δiτ,?=?

2

?()ggΔ?τi,k?1i,k

+?(gi,k?1+gi,k)+i?τ2,??4Δi24?

?ifgi,k?1+gi,k<2i?Δiτ,(21)?

??tk,1=(k?1)τ+(gi,k?1?gi)/Δi,

(24) ?

tkτgg()/,=??Δi,ki?i?k,2

(21)式的積分基于(20)式, 通過圖2中的中間一列兩

幅圖(最高可達(dá)生產(chǎn)率曲線)能夠更好說明. 圖2中的Case 1和Case 2分別對應(yīng)于(21)式中的第一種情況和第二種情況. 結(jié)論(ii)因此成立.

(iii) 顯然, 在(ii)的證明中, 如果當(dāng)t∈[(k?1)τ,kτ]

不難驗證(22)式滿足時, (24)中給出的兩個時刻tk,1, tk,2均位于第k時段. 與gimin,k(t)對應(yīng)的ui(t)為: t∈[(k?1)τ, kτ]時

??Δi,if(k?1)τ≤t<tk,1,

?

(25) ui(t)=?0,iftk,1≤t<tk,2,

?

?Δi,iftk,2≤t≤kτ.

時取gi(t)=gimin,k(t), 則(19)式中的不等號將變?yōu)榈忍? 同理, 如果取gi(t)=gimax,k(t), 則(21)式中的不等號

(23)~(25)式的結(jié)果可以用圖2中第3列的兩幅圖

45

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

來解釋. 注意(25)式中給出的生產(chǎn)率變化率(控制量)曲線呈階梯狀. 定理1至此全部證完.

定理1是將具有積分約束的調(diào)度問題(1)~(8)轉(zhuǎn)化為非線性規(guī)劃問題的基礎(chǔ). 定理2進(jìn)一步指出當(dāng)(11)~(13)式中給出已知時段初、末時刻生產(chǎn)率時, 時段內(nèi)產(chǎn)量上下界函數(shù)為凸或凹.

(29)式的證明可基于對x1, x2和超平面H間的所有可能位置關(guān)系進(jìn)行分析來完成. 所有可能位置關(guān)系全部在表1中列出.

表1 x1, x2和超平面H間的所有可能位置關(guān)系

關(guān)系分類

αTx2<β

Case 1 Case 1 Case 2

αTx2=β

Case 1 Case 1 Case 1

αTx2>β

Case 2 Case 1 Case 1

定理2. 定理1中給出的二元函數(shù)i(?,?)是光

αTx1<β αTx1=β αTx1>β

滑的(即連續(xù)可導(dǎo))凸函數(shù), i(?,?)是光滑的凹函數(shù).

為證明定理2, 需要兩個引理.

引理1. 假設(shè)f1:R→R, f2:R→R均為連

nn

續(xù)可導(dǎo)函數(shù), H={x|αTx=β,x∈Rn}是Rn中的一個超平面, 其中α∈Rn, β∈R為給定向量和實數(shù). 如果f1(x)=f2(x)且?f1(x)=?f2(x) 對所有x∈H成立, 即兩個函數(shù)在超平面H上光滑銜接, 則下述函數(shù)在Rn上連續(xù)可導(dǎo).

在表1中, 所有可能的位置關(guān)系被分為兩大類, 第一類為:

Case 1. αTx1≤β,αTx2≤β或αTx1≥β,αTx2≥β, (30)

在這種類型中, 兩個點x1, x2位于超平面H的同一側(cè), 因此由(27)式可知

??f(x1)=?f1(x1),?f(x2)=?f1(x2),?

ifαTx1≤β,αTx2≤β,?

?1122

??f(x)=?f2(x),?f(x)=?f2(x),?

ifαTx1≥β,αTx2≥β,?

T??f1(x),ifαx≤β,

(26) f(x)=?

T ??f2(x),ifαx>β.

(31)

證明: 根據(jù)導(dǎo)數(shù)和光滑函數(shù)的定義, 引理1的

結(jié)論是顯然的.

引理2. 所有條件同引理1, 再假定f1, f2在Rn

中均為凸函數(shù), 則(26)中給出的函數(shù)f(x)也是Rn中的凸函數(shù).

證明: 首先, 根據(jù)已知條件可得下式成立:

再結(jié)合(28)式即可知(29)式成立.

第二類為: Case 2.

αTx1<β,αTx2>β或αTx1>β,αTx2<β, (32)

在這種類型中, 兩個點x1, x2位于超平面H的不同側(cè). T??f(x),ifαxβ,≤?

?f(x)=?1基于問題對稱性并不失一般性, 僅考慮αTx1>β , T??f2(x),ifαx≥β,??αTx2>β 發(fā)生的情況. 此時由(27)式可知: (27) ?T????f1(x),ifαx≤β, ?f(x1)=?f1(x1),?f(x2)=?f2(x2), (33) ??f(x)=?T

????f2(x),ifαx≥β,?

β?αTx1

令 θ=T2,x0=x1+θ(x2?x1), (34) T1根據(jù)光滑函數(shù)成為凸函數(shù)的充分必要條件, ?f1

αx?αx

n[20]1 2n

則有 和?f2均為R中的單調(diào)映射, 即對任意x,x∈R有下式成立:

?

????

??f1(x1)??f1(x2)?(x1?x2)≥0,????f2(x)??f2(x)?(x?x)≥0,??

n

T

0<θ<1,αTx0=β. (35)

?

????

T

再根據(jù)f1和f2的凸性可知:

(28)

10?(x1?x0)≥0,?fxfx???()()??11

12

T

12

為證f是凸函數(shù), 只需證明?f是R中的單調(diào)映射, 即對任意x1,x2∈Rn,

46

T

???f2(x)??f2(x)??(x?x)≥0.

02

T

02

(36)

由(34)式可得:

x1?x0=θ(x1?x2),x0?x2=(1?θ)(x1?x2),

1212?將上式代入(36)式并注意到0<θ<1則可以得到: ??f(x)??f(x)??(x?x)≥0, (29)