选, 某些系统可能不需要.

由(1)~(8)式描述的具有实际背景的生产制造系Ci(pi(k)) 设备i在第k时段生产量为pi(k)时的生

统优化调度问题十分复杂, 既包括了离散时间约束, 产成本, 假定成本仅与生产量有关;

也包括了连续时间积分关系, 难以直接应用现有的D(k) 第k时段的总需求或合同供货量.

非线性规划或最优控制理论求解, 本文通过深入研

本文考虑的生产调度可描述为以下优化问题.

究约束(4)~(7)及目标函数(1)的结构特征, 找到了将

目标: 生产成本最小

此类调度问题转化为光滑凸规划问题的系统方法.

IK

minJ=∑∑Ci(pi(k)). (1) 受篇幅限制, 模型(1)~(8)中未引入描述设备开

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

i=1k=1关机状态的离散决策变量和约束. 作者已结合本文

约束条件: 的理论结果和前期研究成果[9], 在上述模型中考虑了

(a) 即时产需平衡: 离散决策变量和约束, 将在以后报告.

43

管晓宏等: 一类含积分约束的生产制造系统优化调度

3 问题转化为光滑凸规划的理论基础

(14)式中的两式相减可得:

gi,k?gi,k?1=∫

kτ(k?1)τ

本节给出将问题(1)~(8)转化为光滑凸规划的理论基础. 为使表述简洁, 引入下述符号:

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

ui(ξ)dξ, (15)

再根据(6)式, 结合(15)式即可得(10)式, 结论(i)因此成立.

(ii) 当t∈[(k?1)τ,kτ]时, 对比约束(5)和(6)式, 可得如下结论:

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

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

表示设备i在kτ时刻的瞬时生产率.

首先, 可以证明单台生产设备在各时段的产量上下限可表示为该设备在相应时段初、末时刻生产率的二元函数.

定理 1. 设 pi(k), gi(t), ui(t)满足约束(4)~(7), 则有下述结论成立:

(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)式中的产量上下限二元函数i(?,?)和i(?,?)解析表达式如下:

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)

因此结合(7)式可知, 当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时段初、末时刻生产率为gi,k?1和gi,k的前提下, 在第k时段设备i的最低可达生产率曲线. 根据产量-生产率积分关系约束(4)式, 从而得到: pi(k)=∫

k?τ(k?1)?τ

k?τ(k?1)?τ

gi(t)dt≥∫

gimin,k(t)dt

(iii) (11)式给出的pi(k)的上下界是可以达到的, 即分别存在适当的生产率函数gi(t)和生产率变化率函数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)式的结果基于(18)式, 通过图2中最左边一列的两幅图(最小可达生产率曲线)能够更好说明. 图2中

的Case 1和Case 2分别对应于(19)式中的第一种情况(k?1)τ?

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

(14) ?

kτ基于完全类似的推理分析, 可以得到当t∈

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

44

中国科学: 技术科学 2010年 第40卷 第1期

图2 设备i在时段k的最低/最高可达生产率曲线及其对应的生产爬升率

gi(t)≤gimax,k(t)

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

将变为等号. 本文仅指出对应于图2中与gimin,k(t)对应

上式右端给出的gimax,k(t)实际上是在给定第k时段初、末时刻设备生产率为gi,k?1和gi,k的前提下, 在第k时段设备i的最高可达生产率曲线. 根据产量-生产率积分关系式(4), 得到:

pi(k)=∫

k?τ(k?1)?τ

的Case 1情况下, ui(t)与gi(t)的对应关系, 其余情况完全类似.

在所考虑的情况下有下式成立:

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中的中间一列两

幅图(最高可达生产率曲线)能够更好说明. 图2中的Case 1和Case 2分别对应于(21)式中的第一种情况和第二种情况. 结论(ii)因此成立.

(iii) 显然, 在(ii)的证明中, 如果当t∈[(k?1)τ,kτ]

不难验证(22)式满足时, (24)中给出的两个时刻tk,1, tk,2均位于第k时段. 与gimin,k(t)对应的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)式中的不等号将变为等号; 同理, 如果取gi(t)=gimax,k(t), 则(21)式中的不等号

(23)~(25)式的结果可以用图2中第3列的两幅图

45

管晓宏等: 一类含积分约束的生产制造系统优化调度

来解释. 注意(25)式中给出的生产率变化率(控制量)曲线呈阶梯状. 定理1至此全部证完.

定理1是将具有积分约束的调度问题(1)~(8)转化为非线性规划问题的基础. 定理2进一步指出当(11)~(13)式中给出已知时段初、末时刻生产率时, 时段内产量上下界函数为凸或凹.

(29)式的证明可基于对x1, x2和超平面H间的所有可能位置关系进行分析来完成. 所有可能位置关系全部在表1中列出.

表1 x1, x2和超平面H间的所有可能位置关系

关系分类

αTx2<β

Case 1 Case 1 Case 2

αTx2=β

Case 1 Case 1 Case 1

αTx2>β

Case 2 Case 1 Case 1

定理2. 定理1中给出的二元函数i(?,?)是光

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

滑的(即连续可导)凸函数, i(?,?)是光滑的凹函数.

为证明定理2, 需要两个引理.

引理1. 假设f1:R→R, f2:R→R均为连

nn

续可导函数, H={x|αTx=β,x∈Rn}是Rn中的一个超平面, 其中α∈Rn, β∈R为给定向量和实数. 如果f1(x)=f2(x)且?f1(x)=?f2(x) 对所有x∈H成立, 即两个函数在超平面H上光滑衔接, 则下述函数在Rn上连续可导.

在表1中, 所有可能的位置关系被分为两大类, 第一类为:

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

在这种类型中, 两个点x1, x2位于超平面H的同一侧, 因此由(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)

证明: 根据导数和光滑函数的定义, 引理1的

结论是显然的.

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

中均为凸函数, 则(26)中给出的函数f(x)也是Rn中的凸函数.

证明: 首先, 根据已知条件可得下式成立:

再结合(28)式即可知(29)式成立.

第二类为: Case 2.

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

在这种类型中, 两个点x1, x2位于超平面H的不同侧. T??f(x),ifαxβ,≤?

?f(x)=?1基于问题对称性并不失一般性, 仅考虑αTx1>β , T??f2(x),ifαx≥β,??αTx2>β 发生的情况. 此时由(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根据光滑函数成为凸函数的充分必要条件, ?f1

αx?αx

n[20]1 2n

则有 和?f2均为R中的单调映射, 即对任意x,x∈R有下式成立:

?

????

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

n

T

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

?

????

T

再根据f1和f2的凸性可知:

(28)

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

12

T

12

为证f是凸函数, 只需证明?f是R中的单调映射, 即对任意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)