实时系统在工程领域具有非常多的应用,例如过程控制系统、工业自动化系统、监控与数据采集系统、测试和测量仪器、自动设备等^[1].与非实时系统相比,实时系统的计算正确性不仅取决于计算的逻辑结果,也取决于结果产生的时间^{[2, 3]}.1973年,Liu和Layland提出了一种适用于可抢占的硬实时周期性任务调度的静态优先级调度算法——单调速率(rate monotonic,简称RM)调度算法^[4],并证明了该算法是最优的,即:对于在任何其他静态优先级算法下可调度的任务集,在RM算法下也是可调度的.

给定一组周期性任务集$\tau $={$\tau $₁,$\tau $₂,...,$\tau $_n},其中,每个任务由三元组$\tau $_i=(C_i,D_i,T_i)表示.其中,T_i是任务周期,每隔时间T_i会生成一个任务$\tau $_i;C_i是运行时间;D_i是截止期限.$\tau $_i必须在截止期限内完成.

根据任务周期和截止期限的关系,可分为3种任务模型^[5]:(1) 隐式期限(implicit-deadline)模型,每个任务$\tau $_i都满足D_i=T_i;(2) 限制期限(constrained-deadline)模型,此时,对每个任务$\tau $_i都有D_i≤T_i;(3) 任意期限(arbitrary- deadline)模型,每个任务$\tau $_i的截止期限D_i与周期T_i无关.目前最常用的模型为隐式期限^[6],本文也针对这类实时系统进行研究.

在单调速率调度算法中,最根本的问题是可调度的判定问题,这需要寻找一种高效的算法验证任务集是否可调度.目前已有大量关于RM算法可调度性判定的文献,判定方法可分为非确切性和确切性两大类.非确切性方法包括CPU利用率最小上界判定法^{[4, 2]}、双曲线上界判定法^[7]、调和链(harmonic chains)方法^{[8, 9]}、构造性方法^{[10, 11, 12, 13]}、线性规划方法^{[14, 15]}等;确切性方法包括有限时间点测试法^{[16, 17, 18, 19]}和最坏响应时间法等^{[20, 21]}.关于单调速率可调度判定算法的综述及比较请见文献^{[3, 19, 22, 23]}.

刘军祥等人在文献^[24]中对RM可调度性判定问题进行扩展,提出了实时系统RM优化设计问题.给定周期性任务集$\tau $及任务周期T₁,T₂,...,T_n,任务运行时间C_i在区间[C^min,C^max]内,需要在RM可调度的约束条件下寻找一组C_i,使得系统某一性能指标(如CPU利用率)最优.该问题主要回答以前可调度性判断存在的两个问题:(1) 如果给定任务集$\tau $不可调度,那么该如何调整参数C_i使得任务可调度;(2) 若任务集$\tau $可调度,能否在一定的区间内(例如所有C_i都不小于原始的运行时间)调整任务参数C_i,使得某个系统的性能指标(如CPU利用率)得到提升.

相比于RM可调度性判定问题,实时系统RM优化设计问题更具有一般性.虽然目前有很多高效的RM可调度性判定算法,但由于C_i都是固定的,因此只能针对某一个实例进行判断.优化设计问题可以看作是其所有实例的集合,即,所有C_i组合(离散或连续)的集合.我们可以通过求解这样的优化问题来对具有大量实例集合的可调度性进行判定.特别是当C_i集合是一个连续的区间时,现有的单实例判定算法已经不起作用,这时只能通过建立优化问题来求解.

实时系统RM优化设计问题也具有重要的应用价值.在Liu和Layland理想任务模型的基础之上,根据具体的应用和需求,提出了非精度计算(imprecise computation)^{[25, 26]}、IRIS(increased reward with increased service)^[27]、QoS资源分配^[28]等模型.在这些模型中,每个任务被分成了两个子任务:强制性任务和可选择性任务.其中:强制性任务必须在截止时间之前产生正确的结果,以保证最低的可接受的质量;而可选择性任务在强制性任务运行结束之后、截止时间之前运行,并能在任意时刻停止.任务运行的时间越多,计算的结果就越精确.这些模型具有广泛的应用^{[29, 30, 31, 32, 33]}:一方面,可以根据一定的最优指标设计任务的最佳运行时间,例如,在图像处理中需要设定提取模糊图像帧的时间,或者在雷达跟踪中,需要给定估计目标位置的时间,既要保证各个任务可调度也要保证有足够的时间使得输出的结果更为精确;另一方面,当系统过载导致任务不可调度时,能够通过调整任务的运行时间来进行过载处理,并同时达到某个最优指标(如CPU利用率).

目前有两种方法^{[34, 24]}求解实时系统RM优化设计问题,这两种方法都是利用RM可调度的充分必要条件作为约束条件,将原问题转化为广义约束优化问题^[35],然后再求解广义约束优化问题.Min-Allah等人^[34]提出了基于非线性约束优化算法的求解方法,先利用文献^[35]中的公式将约束条件等价变换为只含有逻辑“与”的约束条件,进而将问题转换为非线性约束优化问题,然后再利用序贯二次规划法(sequential quadratic programming)^[36]或内点法(interior-point method)^[37]求解.刘军祥等人^[24]则提出了基于混合布尔整数规划的求解方法,通过引入0-1整数变量,将具有逻辑“或”的约束条件转换为混合整数约束条件,得到混合布尔型整数规划问题,然后采用经典的分支定界算法^[38]求解.但这两种方法的求解速度较慢,任务数较多时将不再适用.

本文提出一种新的求解实时系统RM优化设计的方法——基于树状的线性规划搜索(linear programming search,简称LPS)算法:首先,将RM算法可调度的充分必要条件转换成具有逻辑“与”和“或”的线性约束不等式,建立优化模型;然后,将模型分拆成若干个线性规划子问题,再构造线性规划问题的搜索树,利用深度优先搜索及其剪枝算法,选择部分线性规划问题进行求解;最终找到线性规划子问题中最大的最优值,从而得到使得CPU利用率最大的任务运行时间.实验结果表明:LPS方法相比于已有的方法能节省20%~70%的求解时间,任务数越多,节省时间越多.

本文第1节介绍理论基础,包括实时系统RM可调度性判定条件和约束优化问题.第2节介绍实时系统RM优化设计问题及已有的两种求解方法.第3节介绍基于树状的线性规划搜索算法.第4节分析算法的时间复杂度.第5节给出实验设计及结果.第6节对全文进行总结.

1. 研究基础 1.1 实时系统RM可调度性判定条件

设实时系统的任务集$\tau $={$\tau $₁,$\tau $₂,...,t_n},每个任务$\tau $_i=(T_i,C_i),其中,T_i为任务周期,C_i为运行时间.

不妨设T₁≤T₂≤…≤T_n,那么根据Liu和Layland的单调速率调度算法,各任务的优先级由高到低为$\tau $₁,$\tau $₂,...,$\tau $_n.Liu和Layland证明了单调速率调度算法是最优的,也即:如果其他任何静态优先级算法是可调度的,那么RM算法也是可以调度的.

目前已有大量关于RM可调度性判定的文献,见文献^{[3, 22, 23, 19]}.在此,只介绍Bini等人于2002年提出的RM可调度性的充要条件^[17],它是本文工作的基础.

定理1(Bini et al.). 任务集$\tau $是RM可调度的当且仅当下式为真:

$\mathop \wedge \limits_{i = 1,2,...,n} \mathop \vee \limits_{t \in {P_{i - 1}}({T_i})} \left( {\sum\limits_{j = 1}^i {\left\lceil {t/{T_j}} \right\rceil } {C_j} \le t} \right)$

(1)

其中,

${P_i}(t) = \left\{ {\begin{array}{*{20}{l}} {\{ t\} ,{\rm{ }}i = 0}\\ {{P_{i - 1}}(\left\lfloor {t/{T_i}} \right\rfloor {T_i}) \cup {P_{i - 1}}(t),{\rm{ }}i \ge 1} \end{array}} \right.$

(2)

这是一种利用有限个时间点进行测试的判定方法.文献^[18]给出了一种计算P_i(t)的二叉树剪枝方法,它能够在计算P_i(t)过程中避免产生相同元素,减少了不必要的开销.

1.2 标准约束优化和广义约束优化问题

标准约束问题(standard constrained optimization problem,简称SCOP)研究在一系列等式和不等式的约束下寻找一个最优点,使得目标函数值达到最大或最小.SCOP在工程领域有很多应用,如控制理论、计算机视觉、计算机辅助设计、结构优化设计、机器人路径规划、实时系统等^{[24, 35]}.SCOP的具体形式可描述为

$\begin{array}{l} \max \;\,f(x)\,\\ {\rm{s}}{\rm{.t}}{\rm{.}} {g_i}(x) = 0,i = 1,2,...,{m_1},\\ \quad \quad {g_i}(x) \le 0,i = {m_1} + 1,{m_1} + 2,...,{m_2}. \end{array}$

其中,变量x=(x₁,x₂,…,x_n)是n维向量,f(x)是目标函数,g_i(x)=0(i=1,2,...,m₁)和g_i(x)≤0(i=m₁+1,m₁+2,...,m₂)是约束条件.

目前有大量的求解SCOP的成熟算法,包括序贯二次规划法^[36]和内点法^[37].

文献^[35]在SCOP的基础上提出了更一般的广义约束优化问题GCOP(generalized constrained optimization problem),在GCOP的约束条件中,不仅有逻辑“与”的关系,也有逻辑“或”的关系.GCOP可描述为

$\left. \begin{array}{l} \max \;f(x)\\ {\rm{s}}{\rm{.t}}{\rm{.}}\quad ({h_{11}}(x) \le 0 \vee {h_{12}}(x) \le 0 \vee ... \vee {h_{1{k_1}}}(x) \le 0) \wedge \\ {\rm{ }}({h_{21}}(x) \le 0 \vee {h_{22}}(x) \le 0 \vee ... \vee {h_{2{k_2}}}(x) \le 0) \wedge ... \wedge \\ \quad \quad ({h_{s1}}(x) \le 0 \vee {h_{s2}}(x) \le 0 \vee ... \vee {h_{s{k_s}}}(x) \le 0) \end{array} \right\}$

(3)

文献^[35]给出了一种求解GCOP的方法,先将带有逻辑“或”的不等式等价变换成一个不等式(见定理2),从而就把GCOP转化为了SCOP,然后再利用求解SCOP的算法进行求解即可.

定理2(Wang and Lane). 已知函数g₁(x),g₂(x),…,g_n(x),那么:

$\begin{array}{l} {g_1}(x) \le 0 \vee {g_2}(x) \le 0 \vee ... \vee {g_n}(x) \le 0 \Leftrightarrow \\ {\rm{\Delta }}v - \sum\limits_{i = 1}^n {(\sqrt {{g_i}{{(x)}^2}} - {g_i}(x))} \le 0 \end{array}$

(4)

其中,Δv为任意小的正数.

2. 实时系统RM优化设计问题及已有的两种求解方法

刘军祥等人^[24]将RM可调度判定问题进行扩展,提出了实时系统RM优化设计问题.在该问题中,不再将RM判定问题中的任务运行时间C_i看作一个固定值,而是一个在区间$[C_i^{\min },C_i^{\max }]$内可选择的变动值.刘军祥等人将实时系统RM优化设计问题表述为^[24]:给定实时系统的任务集$\tau $={$\tau $₁,$\tau $₂,...,$\tau $_n},每个任务$\tau $_i的周期为T_i,运行时间C_i在区间$[C_i^{\min },C_i^{\max }]$内可选择,如何设计各任务的运行时间,使得该系统的某个性能指标达到最优.本文将CPU利用率$U = \sum\limits_{i = 1}^n {{C_i}/{T_i}} $作为系统性能指标.该问题可以解决如下两类问题^{[24, 34]}:

· 若给定的任务集$\tau $不可调度,那么该如何调整或减少任务的运行时间C_i,使得系统可调度;

· 若给定的任务集$\tau $可调度,如何增加任务的运行时间,使得系统性能指标(如CPU利用率)得到提升甚至达到最优.

文献^[24]将实时系统RM优化设计问题建模成一个广义约束优化问题.目标函数为CPU利用率:

$f = \sum\limits_{i = 1}^n {{C_i}/{T_i}} .$

约束条件由两部分组成:

(1) 每个任务的运行时间C_i都在限定的区间内;

(2) 满足所有任务RM可调度.

· 对于约束条件(1),我们只需保证对所有的i都有$C_i^{\min } \le {C_i} \le C_i^{\max }$即可;

· 对于约束条件(2),我们利用Bini等人^[17]提出的RM可调度充要条件(定理1).

从而,实时系统RM优化设计问题可以建模成如下广义约束优化问题:

$\left. \begin{align} & \max \quad f=\sum\limits_{i=1}^{n}{{{C}_{i}}/{{T}_{i}}} \\ & \text{s}\text{.t}\text{.}\quad \underset{t\in {{P}_{i-1}}({{T}_{i}})}{\mathop \vee }\,\left( \sum\limits_{j=1}^{i}{\left\lceil t/{{T}_{j}} \right\rceil }{{C}_{j}}-t\le 0 \right) \\ & C_{i}^{\min }\le {{C}_{i}}\le C_{i}^{\max }~ \\ & \quad \quad \quad i=1,2,...,n \\ \end{align} \right\}$

(5)

我们称上述模型为求解实时系统RM优化设计问题的基本模型.

目前有两种方法求解模型公式(5)^{[24, 34]}:

· 文献^[24]提出了基于混合布尔整数规划的求解方法:通过引入整数变量和布尔变量,将公式(5)等价转换为混合型整数规划(MBP)问题;然后,再利用MBP的经典算法——分支定界法^[38]来求解转换后的优化问题,进而得到原问题的最优解.这种方法需要引入大量新的变量,增大了一定的求解难度;

· 文献^[34]则提出了基于非线性约束优化算法的求解方法:将模型中每一组含有逻辑“或”的约束条件转换为一个非线性的约束不等式,得到一个标准的约束优化问题(SCOP)中的非线性规划(NLP)问题;然后,再利用NLP中的成熟算法——序贯二次规划^[36]或内点法^[37]求解SCOP.这种方法将线性的不等式变成了非线性的不等式,这增加了求解模型的难度.并且,转化后的SCOP的可行域并不是凸的,在求解时容易掉入局部解.

文献^{[24, 34]}分别将目标问题等价建模成MBP和NLP问题,因此,我们将文献^[24]的方法称为基于MBP的方法,而将文献^[34]中的方法称为基于NLP的方法.

3. 线性规划搜索(LPS)方法 3.1 模型建立

在基本公式(5)中,约束条件$\underset{t\in {{P}_{i-1}}({{T}_{i}})}{\mathop \vee }\,\left( \sum\limits_{j=1}^{i}{\left\lceil t/{{T}_{j}} \right\rceil }{{C}_{j}}-t\le 0 \right),i=1,2,...,n$之间的关系是“与”,因此也可以写成:

$\underset{i=1,...,n}{\mathop \wedge }\,\underset{t\in {{P}_{i-1}}({{T}_{i}})}{\mathop \vee }\,\left( \sum\limits_{j=1}^{i}{\left\lceil t/{{T}_{j}} \right\rceil }{{C}_{j}}-t\le 0 \right).$

这是一个合取范式(conjunction normal form),注意到,任何逻辑公式均可以通过一定的方法等价转换为析取范式(disjunctive normal form),因此,我们也可以将上述的合取范式转换为析取范式.由于不同的逻辑公式转换成析取范式所用的技巧不尽相同,下面我们通过一个例子来说明从合取范式转换为析取范式的方法.

例:设p₁,p₂,p₃,p₄,p₅为命题,将合取范式(p₁$\vee $p₂)$\wedge $(p₃$\vee $p₄$\vee $p₅)转换为析取范式.

解:首先将第1个括号展开,利用分配律可得到(p₁$\wedge $(p₃$\vee $p₄$\vee $p₅))$\vee $(p₂$\wedge $(p₃$\vee $p₄$\vee $p₅));然后,再将由“或”连接的两个逻辑公式里各自的括号展开,再 利用分配律可得到:

(p1$\wedge $p3)$\vee $(p1$\wedge $p4)$\vee $(p1$\wedge $p5)$\vee $(p2$\wedge $p3)$\vee $(p2$\wedge $p4)$\vee $(p2$\wedge $p5).

这样就得到了析取范式.关于合取范式和析取范式的概念以及将任意逻辑公式转换为析取范式的方法见文献^[39].利用该方法,我们可以将上述合取范式转换为下面的析取范式:

$\underset{i=1,...,n}{\mathop \wedge }\,\underset{t\in {{P}_{i-1}}({{T}_{i}})}{\mathop \vee }\,\left( \sum\limits_{j=1}^{i}{\left\lceil t/{{T}_{j}} \right\rceil }{{C}_{j}}-t\le 0 \right)\Leftrightarrow \underset{\begin{matrix} {{t}_{1}}\in {{P}_{0}}({{T}_{1}}) \\ {{t}_{2}}\in {{P}_{1}}({{T}_{2}}) \\ ... \\ {{t}_{n}}\in {{P}_{n-1}}({{T}_{n}}) \\ \end{matrix}}{\mathop \vee }\,\underset{i=1,...,n}{\mathop \wedge }\,\left( \sum\limits_{j=1}^{i}{\left\lceil {{t}_{i}}/{{T}_{j}} \right\rceil }{{C}_{j}}-{{t}_{i}}\le 0 \right).$

从而,约束优化公式(5)就等价于如下问题:

$\left. \begin{align} & \max \quad \quad f=\sum\limits_{i=1}^{n}{\frac{{{C}_{i}}}{{{T}_{i}}}} \\ & \text{s}\text{.t}\text{.}\quad \quad \underset{\begin{matrix} {{t}_{1}}\in {{P}_{0}}({{T}_{1}}) \\ {{t}_{2}}\in {{P}_{1}}({{T}_{2}}) \\ ... \\ {{t}_{n}}\in {{P}_{n-1}}({{T}_{n}}) \\ \end{matrix}}{\mathop \vee }\,\underset{i=1,...,n}{\mathop \wedge }\,\left( \sum\limits_{j=1}^{i}{\left\lceil {{t}_{i}}/{{T}_{j}} \right\rceil }{{C}_{j}}-{{t}_{i}}\le 0 \right) \\ & \quad \quad \quad C_{i}^{\min }\le {{C}_{i}}\le C_{i}^{\max } \\ & \quad \quad \quad i=1,2,...,n \\ \end{align} \right\}$

(6)

只要(C₁,C₂,…,C_n)满足上述析取范式约束条件中的任意一项,即可满足整个析取范式.设集合P_i-1(T_i)的元素个数为|P_i-1(T_i)|,易知,|P_i-1(T_i)|是一个有限的整数(i=1,2,…,n).因此,约束优化问题(3.1)可以被分拆成如下K=|P₀(T₁)||P₁(T₂)|…|P_n-1(T_n)|个有限的线性规划子问题:

$\left. \begin{align} & \max \quad {{f}_{{{l}_{1}}{{l}_{2}}...{{l}_{n}}}}=\sum\limits_{i=1}^{n}{\frac{{{C}_{i}}}{{{T}_{i}}}} \\ & \text{s}\text{.t}\text{.}\quad \quad \sum\limits_{j=1}^{i}{\left\lceil {{p}_{i{{l}_{i}}}}/{{T}_{j}} \right\rceil }{{C}_{j}}-{{p}_{i{{l}_{i}}}}\le 0 \\ & \quad \quad \quad C_{i}^{\min }\le {{C}_{i}}\le C_{i}^{\max } \\ & \quad \quad \quad i=1,2,...,n \\ \end{align} \right\}$

(7)

其中,${{p}_{i{{l}_{i}}}}$表示集合P_i-1(T_i)中的第l_i个元素,l_i=1,2,…,|P_i-1(T_i)|.所有这些线性规划子问题的最优值(如果存在可行解的话)中的最大值就是约束优化问题(3.1)的最优值,即是基本模型的最优值.

当实时系统的任务数量n较小时,总的线性规划子问题数量K也较小;但是随着n的增大,K将呈指数级地增长.因此,试图去求解所有的线性规划子问题是不合实际的,我们只能通过一些搜索的办法,去掉最优值不可能成为全局最优解的线性规划子问题,使用剩下的线性规划子问题进行求解,进而得到问题(3.1)的最优解.我们称这种方法为线性规划搜索(linear programming search,简称LPS)方法.LPS方法的主要步骤如下所示:

1. 去掉集合P_i-1(T_i)中的部分元素,使得由剩下元素所组合而成的线性规划不等式都可以找到最优解,从而减少了线性规划子问题的数量;

2. 随机选取一些线性规划子问题,找出它们所得最优值中的最大值,并用概率统计中的非参数估计方法证明找到的这个最优值确实很接近模型(3.1)的全局最优值;

3. 构造由一些线性规划问题所组成的搜索树,将之前得到的最优值作为搜索剪枝的判定条件,利用深度优先搜索及两个剪枝策略去求解线性规划问题,最终得到模型(3.1)的最优值.

第3.2节主要介绍如何去掉集合P_i-1(T_i)中的部分元素,使得剩下集合的元素所组成的不等式都有最优解;在第3.3节中,我们构造了线性规划问题的搜索树,并假设先给定了一个线性规划问题的最优值f₀及其对应的最优点x₀,将(f₀,x₀)作为初始值进行深度优先搜索,最终得到模型(3.1)的最优解;在第3.4节中,主要讨论了如何用概率统计的方法寻找到一个较好的搜索初始值(f₀,x₀),从而可以更好地减少搜索空间;第3.5节给出了LPS方法的完整算法.

为了更方便地叙述LPS方法,我们定义:

$\begin{align} & C=({{C}_{1}},{{C}_{2}},...,{{C}_{n}}), \\ & {{C}^{\max }}=(C_{1}^{\max },C_{2}^{\max },...,C_{n}^{\max }), \\ & {{C}^{\min }}=(C_{1}^{\min },C_{2}^{\min },...,C_{n}^{\min }), \\ & CR=\{({{C}_{1}},{{C}_{2}},...,{{C}_{n}})|{{C}_{i}}\in [C_{i}^{\min },C_{i}^{\max }]\}. \\ \end{align}$

用${{p}_{i{{l}_{i}}}}$表示集合P_i-1(T_i)中的第l_i个元素,定义$Q(k,{{l}_{k}},C)=\sum\limits_{j=1}^{k}{\left\lceil {{p}_{k{{l}_{k}}}}/{{T}_{j}} \right\rceil }{{C}_{j}}-{{p}_{k{{l}_{k}}}}$,其中,k$ \in ${1,2,...,n},${{p}_{k{{l}_{k}}}}$表示集合P_k-1(T_k)中的第l_k个元素l_k=1,2,…,|P_k-1(T_k)|.

用记号$LP\left( \begin{matrix} {{k}_{1}} & {{k}_{2}} & ... & {{k}_{m}} \\ {{l}_{{{k}_{1}}}} & {{l}_{{{k}_{2}}}} & ... & {{l}_{{{k}_{m}}}} \\ \end{matrix} \right)$表示线性规划问题:

$\left. \begin{align} & \max \quad \sum\limits_{i=1}^{n}{\frac{{{C}_{i}}}{{{T}_{i}}}} \\ & \text{s}\text{.t}\text{.}\quad \quad Q({{k}_{i}},{{l}_{{{k}_{i}}}},C)=\sum\limits_{j=1}^{{{k}_{i}}}{\left\lceil {{p}_{{{k}_{i}}{{l}_{{{k}_{i}}}}}}/{{T}_{j}} \right\rceil }{{C}_{j}}-{{p}_{{{k}_{i}}{{l}_{{{k}_{i}}}}}}\le 0,i=1,2...,m \\ & \quad \quad \quad C_{r}^{\min }\le {{C}_{r}}\le C_{r}^{\max },r=1,2,...,n \\ \end{align} \right\}$

(8)

其中,m≤n,{k₁,k₂,…,k_m}$\subset ${1,2,…,n},且满足k₁<k₂<...<k_m,${{p}_{{{k}_{i}}{{l}_{{{k}_{i}}}}}}$表示集合${{P}_{{{k}_{i}}-1}}({{T}_{{{k}_{i}}}})$中的第${{l}_{{{k}_{i}}}}$个元素.该线性规划问题的最优值用$OPT\left( \begin{matrix} {{k}_{1}} & {{k}_{2}} & ... & {{k}_{m}} \\ {{l}_{{{k}_{1}}}} & {{l}_{{{k}_{2}}}} & ... & {{l}_{{{k}_{m}}}} \\ \end{matrix} \right)$或OPT(LP)表示.再定义线性规划问题集:

$L=\left\{ \left. LP\left( \begin{matrix} 1 & 2 & ... & n \\ {{l}_{1}} & {{l}_{2}} & ... & {{l}_{n}} \\ \end{matrix} \right) \right|{{l}_{i}}=1,2,...,|{{P}_{i-1}}({{T}_{i}})|;i=1,2,...,n \right\}$

(9)

以及线性规划最优值的集合:

$O(L)=\left\{ \left. OPT\left( \begin{matrix} 1 & 2 & ... & n \\ {{l}_{1}} & {{l}_{2}} & ... & {{l}_{n}} \\ \end{matrix} \right) \right|{{l}_{i}}=1,2,...,|{{P}_{i-1}}({{T}_{i}})|;i=1,2,...,n \right\}$

(10)

那么,要想求解模型公式(6),只需要找到线性规划问题集合L中最大的最优值max O(L)及其对应的最优点C即可.

3.2 减少线性规划子问题数量的算法

考虑模型公式(6)所分解出的任意一个线性规划子问题$LP\left( \begin{matrix} 1 & 2 & ... & n \\ {{l}_{1}} & {{l}_{2}} & ... & {{l}_{n}} \\ \end{matrix} \right)\in L$,当C=C^min时,若存在某个k$ \in ${1,2,...,n},使得Q(k,l_k,C^min)>0,那么对任意的C$ \in $CR:

$Q(k,{{l}_{k}},C)=\sum\limits_{j=1}^{k}{\left\lceil {{p}_{k{{l}_{k}}}}/{{T}_{j}} \right\rceil }{{C}_{j}}-{{p}_{k{{l}_{k}}}}\ge \sum\limits_{j=1}^{k}{\left\lceil {{p}_{k{{l}_{k}}}}/{{T}_{j}} \right\rceil }C_{j}^{\min }-{{p}_{k{{l}_{k}}}}>0.$

从而导致$LP\left( \begin{matrix} 1 & 2 & ... & n \\ {{l}_{1}} & {{l}_{2}} & ... & {{l}_{n}} \\ \end{matrix} \right)$无可行解.因此,在求解模型公式(6)的线性规划子问题公式(7)之前,可去掉集合P_i-1(T_i)中所有使得Q(k,l_k,C^min)>0的元素${{p}_{k{{l}_{k}}}}$(i=1,2,...,n),从而减少线性规划子问题的数量.

另一方面,当C=C^max时,若存在某个k$ \in ${1,2,...,n}使得Q(k,l_k,C^min)≤0,那么对任意的C$ \in $CR:

$Q(k,{{l}_{k}},C)=\sum\limits_{j=1}^{k}{\left\lceil {{p}_{k{{l}_{k}}}}/{{T}_{j}} \right\rceil }{{C}_{j}}-{{p}_{k{{l}_{k}}}}\le \sum\limits_{j=1}^{k}{\left\lceil {{p}_{k{{l}_{k}}}}/{{T}_{j}} \right\rceil }C_{j}^{\max }-{{p}_{k{{l}_{k}}}}\le 0.$

也即${{C}_{i}}\le C_{i}^{\max }(i=1,2,...,n)$蕴含了不等式Q(k,l_k,C)≤0,因此:

$\begin{align} & OPT\left( \begin{matrix} 1 & 2 & ... & k & ... & n \\ {{l}_{1}} & {{l}_{2}} & ... & {{l}_{k}} & ... & {{l}_{n}} \\ \end{matrix} \right)= \\ & OPT\left( \begin{matrix} 1 & 2 & ... & k-1 & k+1 & ... & n \\ {{l}_{1}} & {{l}_{2}} & ... & {{l}_{k-1}} & {{l}_{k+1}} & ... & {{l}_{n}} \\ \end{matrix} \right). \\ \end{align}$

易知,对任意的${{{l}'}_{k}}=1,2,...,|{{P}_{k-1}}({{T}_{k}})|$:

$\begin{align} & OPT\left( \begin{matrix} 1 & 2 & ... & k-1 & k+1 & ... & n \\ {{l}_{1}} & {{l}_{2}} & ... & {{l}_{k-1}} & {{l}_{k+1}} & ... & {{l}_{n}} \\ \end{matrix} \right)\ge \\ & OPT\left( \begin{matrix} 1 & 2 & ... & k & ... & n \\ {{l}_{1}} & {{l}_{2}} & ... & {{l}_{{{k}'}}} & ... & {{l}_{n}} \\ \end{matrix} \right). \\ \end{align}$

因此,

$\begin{align} & OPT\left( \begin{matrix} 1 & 2 & ... & k & ... & n \\ {{l}_{1}} & {{l}_{2}} & ... & {{l}_{k}} & ... & {{l}_{n}} \\ \end{matrix} \right)\ge \\ & OPT\left( \begin{matrix} 1 & 2 & ... & k & ... & n \\ {{l}_{1}} & {{l}_{2}} & ... & {{l}_{{{k}'}}} & ... & {{l}_{n}} \\ \end{matrix} \right). \\ \end{align}$

又因为Q(k,l_k,C^min)≤Q(k,l_k,C^max)≤0,从而集合P_i-1(T_i)只需保留一个元素${{p}_{k{{l}_{k}}}}$即可.

因此,我们可以按照上述方法去掉P_i-1(T_i)中的若干元素,这样可以减少线性规划子问题的数量.对集合P_i-1(T_i),定义它的子集:

${{W}_{i}}=\left\{ \begin{array}{*{35}{l}} \{{{p}_{ik}}\},\text{ } \exists k\in \{1,2,...,|{{W}_{i}}|\}\ \text{s}\text{.t}\text{.}\ Q(i,k,{{C}^{\max }})\le 0 \\ \{{{p}_{i{{l}_{i}}}}\in {{P}_{i-1}}({{T}_{i}})|Q(i,{{l}_{i}},{{C}^{\min }})\le 0\},\text{ otherwise} \\ \end{array} \right.,i=1,2,...,n.$

用记号$wLP\left( \begin{matrix} {{k}_{1}} & {{k}_{2}} & ... & {{k}_{m}} \\ {{h}_{{{k}_{1}}}} & {{h}_{{{k}_{2}}}} & ... & {{h}_{{{k}_{m}}}} \\ \end{matrix} \right)$表示如下线性规划问题:

$\left. \begin{align} & \max \quad \sum\limits_{i=1}^{n}{\frac{{{C}_{i}}}{{{T}_{i}}}} \\ & \text{s}\text{.t}\text{.}\quad \quad \sum\limits_{j=1}^{{{k}_{i}}}{\left\lceil {{w}_{{{k}_{i}}{{h}_{{{k}_{i}}}}}}/{{T}_{j}} \right\rceil }{{C}_{j}}-{{w}_{{{h}_{i}}{{l}_{{{k}_{i}}}}}}\le 0,i=1,2,...,m \\ & \quad \quad \quad C_{r}^{\min }\le {{C}_{r}}\le C_{r}^{\max },r=1,2,...,n \\ \end{align} \right\}$

(11)

其中,m≤n,{k₁,k₂,…,k_m}$\subset ${1,2,…,n},且满足k₁<k₂<...<k_m,${{w}_{{{k}_{i}}{{h}_{{{k}_{i}}}}}}$表示集合W_i中的第${{l}_{{{k}_{i}}}}$个元素.定义wOPT(wLP)为wLP的最优值,由W_i的构造方法易知:对任意的m,线性规划问题(3.6)均存在最优值.再定义线性规划问题的集合:

$W=\left\{ \left. wLP\left( \begin{matrix} 1 & 2 & ... & n \\ {{h}_{1}} & {{h}_{2}} & ... & {{h}_{n}} \\ \end{matrix} \right) \right|{{h}_{i}}=1,2,...,|{{W}_{i}}|;i=1,2,...,n \right\}$

(12)

以及线性规划最优值的集合:

$O(W)=\left\{ \left. wOPT\left( \begin{matrix} 1 & 2 & ... & n \\ {{h}_{1}} & {{h}_{2}} & ... & {{h}_{n}} \\ \end{matrix} \right) \right|{{h}_{i}}=1,2,...,|{{W}_{i}}|;i=1,2,...,n \right\}.$

定理3. 求解模型公式(6)等价于求解线性规划问题集$\Omega $中最大的最优值max O($\Omega $).

证明:只需证明max O($\Omega $)=max O(L).

显然,W_i⊂P_i-1(T_i),因此$\Omega $$\subset $L,故max O(L)≥max O($\Omega $).

再证max O(L)≤max O($\Omega $).

设max O(L)所对应的线性规划问题为$LP\left( \begin{matrix} 1 & 2 & ... & m \\ {{l}_{1}} & {{l}_{2}} & ... & {{l}_{n}} \\ \end{matrix} \right)$,最优点为C,从而对任意的i=1,2,...,n,有:

Q(i,li,Cmin)≤Q(i,li,C)≤0.

那么,${{p}_{i{{l}_{i}}}}\in {{W}_{i}}$;

若不然,不妨设${{p}_{{{k}_{j}}{{l}_{{{k}_{j}}}}}}\not{\in }{{W}_{{{k}_{j}}}}$(j=1,2,...,m,m≤n),那么由${{W}_{{{k}_{j}}}}$的定义知${{W}_{{{k}_{j}}}}=\{{{p}_{{{k}_{j}}l{{'}_{{{k}_{j}}}}}}\}({{{l}'}_{{{k}_{j}}}}\ne {{l}_{{{k}_{j}}}})$,定义:

${{w}_{i}}=\left\{ \begin{array}{*{35}{l}} {{p}_{i{{l}_{i}}}},\text{ }{{p}_{i{{l}_{i}}}}\in {{W}_{i}}\subset {{P}_{i-1}}({{T}_{i}}) \\ {{p}_{i{{l}_{{{i}'}}}}},\text{ }{{p}_{i{{l}_{i}}}}\not{\in }{{W}_{i}}=\{{{p}_{i{{l}_{{{i}'}}}}}\} \\ \end{array} \right.,$

则w_i$ \in $W_i.设w_i是集合W_i中的第h_i个元素,那么由前面的讨论知:

$\begin{align} & wOPT\left( \begin{matrix} 1 & 2 & ... & n \\ {{h}_{1}} & {{h}_{2}} & ... & {{h}_{n}} \\ \end{matrix} \right)\ge \\ & OPT\left( \begin{matrix} 1 & 2 & ... & m \\ {{l}_{1}} & {{l}_{2}} & ... & {{l}_{n}} \\ \end{matrix} \right)=\max O(L). \\ \end{align}$

又因为$wLP\left( \begin{matrix} 1 & 2 & ... & n \\ {{h}_{1}} & {{h}_{2}} & ... & {{h}_{n}} \\ \end{matrix} \right)\in L$,因此$\max O(L)\ge wOPT\left( \begin{matrix} 1 & 2 & ... & n \\ {{h}_{1}} & {{h}_{2}} & ... & {{h}_{n}} \\ \end{matrix} \right)$,

那么,$\max O(L)=wOPT\left( \begin{matrix} 1 & 2 & ... & n \\ {{h}_{1}} & {{h}_{2}} & ... & {{h}_{n}} \\ \end{matrix} \right)\le \max O(W).$

在得到了集合W₁,W₂,...,W_n后,我们可以通过构造线性规划子问题搜索树进行深度优先搜索以及适当地剪枝来求解部分线性规划子问题,进而可以求得模型(3.1)的最优值.

3.3 利用剪枝搜索算法寻找O($\Omega $)的最大值

设搜索树ST的根结点为Root,深度为0,作为深度优先搜索的起点.搜索树ST中深度为1的子结点(根结点 Root的所有子结点)为$wLP\left( \begin{matrix} n \\ {{h}_{n}} \\ \end{matrix} \right)({{h}_{n}}=1,2,...,|{{W}_{n}}|)$,对每一个固定的h_n,$wLP\left( \begin{matrix} n \\ {{h}_{n}} \\ \end{matrix} \right)$的子结点为$wLP\left( \begin{matrix} n-1 & n \\ {{h}_{n-1}} & {{h}_{n}} \\ \end{matrix} \right)$(h_n-1=1,2,...,|W_n-1|),搜索树ST中深度为k的线性规划问题均具有形式:

$wLP\left( \begin{matrix} n-k+1 & ... & n-1 & n \\ {{h}_{n-k+1}} & ... & {{h}_{n-1}} & {{h}_{n}} \\ \end{matrix} \right).$

对固定的h_n-k+1,…,h_n-1,h_n,结点$wLP\left( \begin{matrix} n-k+1 & ... & n-1 & n \\ {{h}_{n-k+1}} & ... & {{h}_{n-1}} & {{h}_{n}} \\ \end{matrix} \right)$的所有子结点为

$wLP\left( \begin{matrix} n-k & n-k+1 & ... & n-1 & n \\ j & {{h}_{n-k+1}} & ... & {{h}_{n-1}} & {{h}_{n}} \\ \end{matrix} \right),j=1,2,...,|{{W}_{n-k}}|.$

图1显示了一棵搜索树的结构.

在进行搜索之前,先随机选取若干个线性规划问题$wLP\left( \begin{matrix} 1 & 2 & ... & n \\ {{h}_{1}} & {{h}_{2}} & ... & {{h}_{n}} \\ \end{matrix} \right)$,取其最大的最优值f₀(关于如何选取及选取的数量,将在第3.4节中讨论),然后开始进行深度优先搜索.在深度优先搜索过程中,若某个结点$wNode=wLP\left( \begin{matrix} n-k+1 & ... & n-1 & n \\ {{h}_{n-k+1}} & ... & {{h}_{n-1}} & {{h}_{n}} \\ \end{matrix} \right)$的最优值不超过f₀,那么wNode的所有子树的线性规划问题的最优值均不会超过f₀(这是因为wNode的可行域包含它所有子树的线性规划的可行域),因此就可以把结点wNode的子树裁剪掉,并继续进行深度优先搜索;若结点wNode的最优值超过了f₀,并且wNode已经是叶子结点,那么就说明存在${{{h}'}_{1}},{{{h}'}_{2}},...,{{{h}'}_{n}}$,使得:

$wOPT\left( \begin{matrix} 1 & 2 & ... & n \\ {{h}_{{{1}'}}} & {{h}_{{{2}'}}} & ... & {{h}_{{{n}'}}} \\ \end{matrix} \right)>{{f}_{0}}.$

即找到了一个线性规划子问题,它的最优值比当前找到的最优值大,因此就把f₀更新为

$wOPT\left( \begin{matrix} 1 & 2 & ... & n \\ {{{{h}'}}_{1}} & {{{{h}'}}_{2}} & ... & {{{{h}'}}_{n}} \\ \end{matrix} \right).$

若wNode并不是叶子结点,那么就继续进行深度优先搜索,直到把整棵树都搜索完毕.

最终得到的f₀就是O($\Omega $)的最大值.

值得注意的是:按照上述方法进行搜索时,可能掉入局部搜索的陷阱中.

例如:当对某个k,满足$wOPT\left( \begin{matrix} n-k+1 & ... & n-1 & n \\ {{h}_{n-k+1}} & ... & {{h}_{n-1}} & {{h}_{n}} \\ \end{matrix} \right)>{{f}^{*}}$时,接下来就会对以$wLP\left( \begin{matrix} n-k+1 & ... & n-1 & n \\ {{h}_{n-k+1}} & ... & {{h}_{n-1}} & {{h}_{n}} \\ \end{matrix} \right)$为根结点的子树进行搜索,如果对某个r及任意的h_n-r+1,h_n-r+2,…,h_n-k,满足:

$wOPT\left( \begin{matrix} n-r+1 & ... & n-k+1 & ... & n-1 & n \\ {{h}_{n-r+1}} & ... & {{h}_{n-k+1}} & ... & {{h}_{n-1}} & {{h}_{n}} \\ \end{matrix} \right)>{{f}^{*}},$

且

$wOPT\left( \begin{matrix} n-r & n-r+1 & ... & n-k+1 & ... & n-1 & n \\ {{h}_{n-r}} & {{h}_{n-r+1}} & ... & {{h}_{n-k+1}} & ... & {{h}_{n-1}} & {{h}_{n}} \\ \end{matrix} \right)\le {{f}^{*}},$

那么该算法需要访问的结点数至少为v=|W_n-r+1||W_n-r+2|…|W_n-k|,当n和r-k较大时,v是一个相当大的数.如:当n=30,k=24,r=20时,v可以达到10¹⁰.因此,算法在进行局部搜索这个子树时会有相当大的时间开销.为了减少这样的时间开销,我们考虑当算法在某个子树里面访问的结点数达到一定数量并且还没有发现新的最优值f时,就应该使用一种辅助方法来判断是否在这棵子树里可以发现新的最优值.如果不能,就立即剪切掉这棵子树,从而达到节省时间的目的.

我们定义两个线性规划的并集:

$\begin{align} & wLP\left( \begin{matrix} {{\alpha }_{1}} & {{\alpha }_{2}} & ... & {{\alpha }_{m}} \\ {{h}_{{{\alpha }_{1}}}} & {{h}_{{{\alpha }_{2}}}} & ... & {{h}_{{{\alpha }_{m}}}} \\ \end{matrix} \right)\bigcup{wLP\left( \begin{matrix} {{\beta }_{1}} & {{\beta }_{2}} & ... & {{\beta }_{{{m}'}}} \\ {{h}_{{{\beta }_{1}}}} & {{h}_{{{\beta }_{2}}}} & ... & {{h}_{{{\beta }_{{{m}'}}}}} \\ \end{matrix} \right)}= \\ & wLP\left( \begin{matrix} {{k}_{1}} & {{k}_{2}} & ... & {{k}_{m+{m}'}} \\ {{h}_{{{k}_{1}}}} & {{h}_{{{k}_{2}}}} & ... & {{h}_{{{k}_{m+{m}'}}}} \\ \end{matrix} \right), \\ \end{align}$

以及它们并集的最优解:

$\begin{align} & wOPT\left( \begin{matrix} {{\alpha }_{1}} & {{\alpha }_{2}} & ... & {{\alpha }_{m}} \\ {{h}_{{{\alpha }_{1}}}} & {{h}_{{{\alpha }_{2}}}} & ... & {{h}_{{{\alpha }_{m}}}} \\ \end{matrix} \right)\bigcup{wOPT\left( \begin{matrix} {{\beta }_{1}} & {{\beta }_{2}} & ... & {{\beta }_{{{m}'}}} \\ {{h}_{{{\beta }_{1}}}} & {{h}_{{{\beta }_{2}}}} & ... & {{h}_{{{\beta }_{{{m}'}}}}} \\ \end{matrix} \right)} \\ & =wOPT\left( \begin{matrix} {{k}_{1}} & {{k}_{2}} & ... & {{k}_{m+{m}'}} \\ {{h}_{{{k}_{1}}}} & {{h}_{{{k}_{2}}}} & ... & {{h}_{{{k}_{m+{m}'}}}} \\ \end{matrix} \right). \\ \end{align}$

在深度优先搜索中考虑结点$wL{{P}_{k}}=wLP\left( \begin{matrix} n-k+1 & ... & n-1 & n \\ {{h}_{n-k+1}} & ... & {{h}_{n-1}} & {{h}_{n}} \\ \end{matrix} \right)$,设当前的最优值为f,如果要把它的子树剪切掉,那就必须保证对任意的${{\hat{h}}_{1}},{{\hat{h}}_{2}},...,{{\hat{h}}_{n-k}}$,满足:

$wOPT\left( \begin{matrix} n-k+1 & ... & n-1 & n \\ {{h}_{n-k+1}} & ... & {{h}_{n-1}} & {{h}_{n}} \\ \end{matrix} \right)\bigcup{wOPT\left( \begin{matrix} 1 & 2 & ... & n-k \\ {{{\hat{h}}}_{1}} & {{{\hat{h}}}_{2}} & ... & {{{\hat{h}}}_{n-k}} \\ \end{matrix} \right)}\le {{f}^{*}}.$

如果$wOPT\left( \begin{matrix} n-k+1 & ... & n-1 & n \\ {{h}_{n-k+1}} & ... & {{h}_{n-1}} & {{h}_{n}} \\ \end{matrix} \right)\le {{f}^{*}}$,可以直接进行剪枝;但如果$wOPT\left( \begin{matrix} n-k+1 & ... & n-1 & n \\ {{h}_{n-k+1}} & ... & {{h}_{n-1}} & {{h}_{n}} \\ \end{matrix} \right)>{{f}^{*}}$的话,我们给出一个新的剪枝判定条件:

引理1. 给定线性规划问题$wOPT\left( \begin{matrix} n-k+1 & ... & n-1 & n \\ {{h}_{n-k+1}} & ... & {{h}_{n-1}} & {{h}_{n}} \\ \end{matrix} \right)$,若存在某个整数r$ \in ${1,2,…,n-k},使得对任意的${{\hat{h}}_{r}}=1,2,...,|{{W}_{r}}|$都有$wOPT\left( \begin{matrix} n-k+1 & ... & n-1 & n \\ {{h}_{n-k+1}} & ... & {{h}_{n-1}} & {{h}_{n}} \\ \end{matrix} \right)\bigcup{wOPT\left( \begin{matrix} r \\ {{{\hat{h}}}_{r}} \\ \end{matrix} \right)}\le {{f}^{*}}$,那么对任意的${{\hat{h}}_{1}},{{\hat{h}}_{2}},...,{{\hat{h}}_{n-k}}$都有:

$wOPT\left( \begin{matrix} n-k+1 & ... & n-1 & n \\ {{h}_{n-k+1}} & ... & {{h}_{n-1}} & {{h}_{n}} \\ \end{matrix} \right)\bigcup{wOPT\left( \begin{matrix} 1 & 2 & ... & n-k \\ {{{\hat{h}}}_{1}} & {{{\hat{h}}}_{2}} & ... & {{{\hat{h}}}_{n-k}} \\ \end{matrix} \right)}\le {{f}^{*}}.$

证明:任取${{\hat{h}}_{1}},{{\hat{h}}_{2}},...,{{\hat{h}}_{n-k}}$,不失一般性,可设n-k=r,那么:

$\begin{align} & wOPT\left( \begin{matrix} n-k+1 & ... & n-1 & n \\ {{h}_{n-k+1}} & ... & {{h}_{n-1}} & {{h}_{n}} \\ \end{matrix} \right)\bigcup{wOPT\left( \begin{matrix} 1 & 2 & ... & n-k \\ {{{\hat{h}}}_{1}} & {{{\hat{h}}}_{2}} & ... & {{{\hat{h}}}_{n-k}} \\ \end{matrix} \right)}\le \\ & wOPT\left( \begin{matrix} n-k+1 & ... & n-1 & n \\ {{h}_{n-k+1}} & ... & {{h}_{n-1}} & {{h}_{n}} \\ \end{matrix} \right)\bigcup{wOPT\left( \begin{matrix} r \\ {{{\hat{h}}}_{r}} \\ \end{matrix} \right)}\le {{f}^{*}}. \\ \end{align}$

引理1给出了一种新的剪枝方法,它可以用来进行辅助剪枝.设按照深度优先搜索开始访问结点wNode,如果算法在接下来的T次访问子结点中都未找到新的最优值,这时就可以利用引理1来判断从根结点到结点wNode的路径上是否有结点可以被剪枝.

最终的剪枝搜索算法请见算法1,其中,函数NextNode表示按深度优先搜索顺序寻找下一个结点,函数TrimNode表示裁剪掉当前结点的子树并继续进行深度优先搜索,函数FindTrimNode为按照引理1进行剪枝并返回继续搜索的深度(见算法2).

算法1. 计算max O($\Omega $)最大值的算法.

Input:

1.   集合W₁,W₂,…,W_n以及初始最优值f₀和最优点x₀;

2.   T:连续T次均未找到新的最优值;

Output:f=max O($\Omega $)和对应的最优点x.

1.  function FindOptimal((f₀,x₀),T)

2.   (f,f)←(f₀,x₀)

3.   depth←1

4.   visit_count←0

5.   $wLP\leftarrow wLP\left( \begin{matrix} n \\ 1 \\ \end{matrix} \right)$

6.   while depth≠0 do

7.    解线性规划wLP并得到最优值wOPT和最优点x

8.    if wOPT>f then

9.     if depth=n then

10.      (x,f)←(wOPT,x)

11.      visit_count←0

12.     end if

13.     (wLP,depth)←NextNode(wLP,depth)

14.     else

15.     (wLP,depth)←TrimNode(wLP,depth)

16.    end if

17.    visit_count←visit_count+1

18.    if visit_count>T then

19.     trim_depth←FindTrimNode(wLP,depth,f)

20.     if trim_depth≠-1 then

21.      depth←trim_depth

22.      (wLP,depth)←TrimNode(wLP,depth)

23.     end if

24.     visit_count←0

25.    end if

26.   end while

27.   return (f,x)

28. end function

算法2. 寻找并判定可剪枝的结点.

Input:子问题结点$wLP=wLP\left( \begin{matrix} n-depth+1 & ... & n-1 & n \\ {{h}_{n-depth+1}} & ... & {{h}_{n-1}} & {{h}_{n}} \\ \end{matrix} \right)$及所在的深度depth以及当前最优值f;

Output:剪枝的深度trim_depth.

1.  function FindTrimNode(wLP,depth,f)

2.   for i←1 to depth-1 do

3.    trim_node←i

4.    for t←i+1 to n do

5.     for j←1 to |W_n-t+1| do

6.      $wOP{{T}_{j}}\leftarrow wOPT\left( \begin{matrix} n-i+1 & ... & n-1 & n \\ {{h}_{n-i+1}} & ... & {{h}_{n-1}} & {{h}_{n}} \\ \end{matrix} \right)\bigcup{wOPT\left( \begin{matrix} n-t+1 \\ j \\ \end{matrix} \right)}$

7.      if wOPT_j>f then

8.       break

9.      else if j=|W_n-t+1| then

10.       return trim_node

11.      end if

12.     end for

13.    end for

14.   end for

15.   return -1 //没有找到可以剪枝的结点

16. end function

我们证明算法1的正确性:

定理4. 利用算法1可以得到max O($\Omega $)及对应的解x.

证明:设算法得到的解为(f,x),对应的线性规划问题为$wLP=wLP\left( \begin{matrix} 1 & 2 & ... & n \\ {{h}_{1}} & {{h}_{2}} & ... & {{h}_{n}} \\ \end{matrix} \right)$,max O($\Omega $)对应的线性规划问题为$wL{P}'=wLP\left( \begin{matrix} 1 & 2 & ... & n \\ {{{{h}'}}_{1}} & {{{{h}'}}_{2}} & ... & {{{{h}'}}_{n}} \\ \end{matrix} \right)$.显然,${{w}_{i{{h}_{i}}}}\in {{W}_{i}}$(i=1,2,...,n),并且$wLP\left( \begin{matrix} 1 & 2 & ... & n \\ {{h}_{1}} & {{h}_{2}} & ... & {{h}_{n}} \\ \end{matrix} \right)\in W$,则f≤max O($\Omega $).

假设f<max O($\Omega $),那么在进行深度优先搜索的过程中,在根结点Root到叶结点wLP'的路径上,存在某个深度为k的结点$wL{{P}_{k}}=wLP\left( \begin{matrix} n-k+1 & ... & n-1 & n \\ {{h}_{n-k+1}} & ... & {{h}_{n-1}} & {{h}_{n}} \\ \end{matrix} \right)$,使得:

$OP{{T}_{k}}=OPT\left( \begin{matrix} n-k+1 & ... & n-1 & n \\ {{h}_{n-k+1}} & ... & {{h}_{n-1}} & {{h}_{n}} \\ \end{matrix} \right)\le {{f}^{*}},$

其中,f为算法当前的最优值(第7行).由于wLP'的可行域包含于wLP_k的可行域,因此OPT_k≥max O($\Omega $),故f≥OPT_k≥max O($\Omega $)>f≥f.矛盾,从而得到f=max O($\Omega $).

3.4 计算搜索初始值的算法

算法1的运行时间取决于算法初始的最大值(算法1第2行)f,f越大,需要搜索的结点数就越小,从而搜索的时间就越少.因此,找出一个尽可能大的搜索初始值f₀是很有必要的.

一个简单快速的方法是:随机选取(h₁,h₂,...,h_n),然后求解线性规划$wLP=wLP\left( \begin{matrix} 1 & 2 & ... & n \\ {{h}_{1}} & {{h}_{2}} & ... & {{h}_{n}} \\ \end{matrix} \right),$这样重复N 次,选出最大的最优值和其对应的最优解即可作为搜索的初始值.但是,如何判断这样选出来的最优值确实是尽可能大的?我们需要用一些统计的方法来判断.

将集合$\Omega $的所有线性规划子问题的最优值作为统计样本,可以得到最优值的分布函数F(x),再事先给定一个充分小的正数$\varepsilon $,如果:

Pr(X<f0)=F(f0)>1-$\varepsilon $

(13)

就说明任意一个最优值比f₀要小的概率是很大的,从而说明f₀确实是一个很大的数.然而,$\Omega $的元素个数是很大的,我们只能随机选取一小部分样本值来估计分布函数F(x),设选取的样本数量为N,那么搜索初始值即为这N个样本中的最大值.设根据这N个样本得到的密度估计函数为${{\hat{f}}_{N}}(x)$,那么分布估计函数为${{F}_{N}}(x)=\int_{-\infty }^{x}{{{p}_{N}}(t)dt}$.我们把分布估计函数当作O($\Omega $)的分布函数,利用式(13)来判断是否该选取f₀作为搜索初始值.

设O($\Omega $)服从分布F(x),选取的N个样本为x₁,x₂,...,x_N,F(x)的密度函数为f(x),我们使用核密度估计方法^[40]来估计f(x),设核密度估计函数为

${{\hat{f}}_{N}}(x)=\frac{1}{Nh}\sum\limits_{i=1}^{N}{K}\left( \frac{{{x}_{i}}-x}{h} \right),$

其中,h为窗宽(bandwidth),K(×)为核函数.对于核函数,我们选择最常用的高斯核(Gaussian kernel),关于核函数的详细介绍见文献^[40].在计算窗宽h时,先根据平均积分均方误差(mean integrated square error)确定出最小窗宽表达式,再采用plug-in方法^[41]计算窗宽的估计值.关于核密度估计的详细算法见文献^{[40, 41]}.

在实际情况中,所有的样本都不小于${{U}_{\min }}=\sum\limits_{i=1}^{n}{\frac{C_{i}^{\min }}{{{T}_{i}}}}$且都不大于1,因此在求密度估计函数时,可以规定当x<U_min或x>1时,${{\hat{f}}_{N}}(x)=0.$

已知密度估计函数${{\hat{f}}_{N}}(x)$,也就可以计算出分布估计函数F_N(x)了.当公式(14)满足时,我们就认为当前样本中的最大值f₀在所有线性规划最优值中确实是一个足够大的值:

Pr(X<f0)=FN(f0)>1-$\varepsilon $

(14)

因此,可以将f₀及其对应的最优点x₀作为算法1的搜索初始值(f₀,x₀).如果f₀并不满足公式(14)时,就再通过随机选取并求解线性规划子问题来添加样本.添加新样本后的最大值f₀可能发生变化,也可能不会变化,但无论怎样,我们找到的确实比f₀小的数量增加了,从而Pr(X<f₀)=F_N(f₀)也会增加,最终总会超过事先设定的1-$\varepsilon $.但是随着样本的增加,计算密度估计函数的时间也会增加,因此,采集的样本数量达到某个上限N时,就直接取出其中的最大值f₀及对应的x₀作为搜索初始值了.另外,还需考虑在采样过程中求解密度估计函数的时机,我们设定一个周期N_p,每采样N_p个样本后立即根据所有已知的样本求解密度估计函数${{\hat{f}}_{N}}(x)$.算法3给出了计算搜索初始值的方法.

算法3. 计算搜索初始值.

Input:集合W₁,W₂,…,W_n,正数$\varepsilon $$ \in $(0,1),样本最大值N,采样周期N_p;

Output:搜索初始值f₀,x₀.

1.  function FindInitial($\varepsilon $,N,N_p)

2.   count←0 //统计样本的个数

3.   Sample←∅

4.   (f₀,x₀)←(0,C^min)

5.   while count≤N do

6.    随机选取元素${{w}_{i{{h}_{i}}}}$$ \in $W_i(i=1,2,…,n)

7.    求解线性规划$wLP=wLP\left( \begin{matrix} 1 & 2 & ... & n \\ {{h}_{1}} & {{h}_{2}} & ... & {{h}_{n}} \\ \end{matrix} \right)$,得到最优值wOPT和最优点wx

8.    Sample←SampleÈ{wOPT} //不能去掉Sample中的相同元素

9.    if wOPT>f₀ then

10.     (f₀,x₀)←(wOPT,wx)

11.    end if

12.    if mod(count,N_p)=0 then

13.     根据样本Sample计算密度估计函数$\hat{f}(x)$

14.     计算分布估计函数$\hat{F}(x)$

15.     if $\hat{F}({{f}_{0}})>1-\varepsilon $then

16.      return (f₀,x₀)

17.     end if

18.    end if

19.   end while

20.   return (f₀,x₀)

21. end function

3.5 求解LPS模型的算法

通过第3.2~第3.4节的叙述,我们给出求解LPS模型的最终算法(见算法4),定理3和定理4保证了该算法的正确性.

算法4. LPS模型求解算法.

Input:

1.  实时系统的n个任务周期T₁,T₂,…,T_n;

2.  n个任务运行时间的范围$[C_{1}^{\min },C_{1}^{\max }],[C_{2}^{\min },C_{2}^{\max }],...,[C_{n}^{\min },C_{n}^{\max }]$;

3.  T:连续T次为找到新的最优值;

4.  正数$\varepsilon $$ \in $(0,1);

5.  样本采集最大数量N;

6.  样本采样周期N_p;

Output:实时系统调度的最大CPU利用率f以及对应的n个任务的执行时间$C=(C_{1}^{*},C_{2}^{*},...,C_{n}^{*}).$

1.  function LPSOptimization

2.   for i←1 to n do

3.    计算P_i-1(T_i)和W_i

4.   end for

5.   (f₀,x₀)←FindInitial($\varepsilon $,N,N_p)

6.   (f,C)←FindOptimal((f₀,x₀),T)

7.   return (f,C)

8.  end function

4. 算法的时间复杂度

下面分析算法4的时间复杂度.

计算P_i(T_i)的方法来自文献^[18]所提出的二叉树剪枝方法.由二叉树的性质可知,|P_i-1(T_i)|≤2^i-1;

又因为$|{{P}_{i-1}}({{T}_{i}})|\le |{{S}_{i}}|\le \sum\limits_{j=1}^{i}{\left\lfloor {{T}_{i}}/{{T}_{j}} \right\rfloor }\le i\left\lfloor {{T}_{i}}/{{T}_{1}} \right\rfloor $,因此计算单个P_i-1(T_i)的时间复杂度是线性的O(nT_i),那么计算所有的集合P₀(T₁),P₁(T₂),…,P_n-1(T_n)的时间复杂度为O(n²T_n).

根据W_i的定义,计算W_i时最坏情况下的循环次数为|P_i-1(T_i)|x2i≤O(nT_n)x2n=O(n²T_n),那么计算W₁,W₂,…,W_n的时间复杂度不超过O(n³T_n).

在计算搜索初始值时,设每采样N_p次计算一次密度函数,一共采样N次.那么最坏情况为采样了N次均未满足$\hat{F}({{f}_{0}})>1-\varepsilon $.计算密度函数的次数为⌊N/N_p⌋.文献^[42]指出:在所有使用核密度估计方法求解近似密度函数的算法时间复杂度为O(SV),其中,S为采样样本的个数,V为样本值的个数.在这里,S=N,V可以近似为S.因此,计算⌊N/N_p⌋次密度估计函数的时间复杂度为O(N³/N_p).我们使用商用优化软件MINOS进行快速求解线性规划问题,文献^[43]指出:用MINOS求解线性规划的平均时间复杂度为O(n+m),其中,n为变量数(也即任务数),m为不等式数.在本问题中,m≤3n,因此在LPS方法中,求解一次线性规划只需要花费线性的时间O(n).综上所述,计算搜索初始值的时间复杂度不会超过O(N⁴n/N_p).一般情况下,N/N_p不会取得太大,因此可以把N/N_p看做一个常数,实际时间复杂度为O(N³n).

考虑剪枝搜索算法的时间复杂度,$\Omega $中的线性规划问题的总数为

${K}'=|{{W}_{1}}||{{W}_{2}}|...|{{W}_{n}}|\le \prod\limits_{i=1}^{n}{i{{T}_{i}}/{{T}_{1}}}=\frac{n!{{T}_{1}}{{T}_{2}}...{{T}_{n}}}{T_{1}^{n}}.$

那么搜索树的叶子结点数量为K',所有的结点数为${K}''\le \prod\limits_{j=1}^{n}{{{k}_{j}}},$其中,${{k}_{j}}=\prod\limits_{i=1}^{j}{\frac{n!{{T}_{n-i+1}}...{{T}_{n-1}}{{T}_{n}}}{(n-i+1)!T_{1}^{n-i+1}}}.$虽然这是一个非常庞大的数,由于初始的搜索最优值的大小已经超过了大约(1-$\varepsilon $)|$\Omega $|线性规划最优值(在后面的实验中,我们将取$\varepsilon $=0.02),因此在实际的搜索中,大量的子树会被剪枝掉.此外,即使在搜索某棵子树时访问了过多的结点,一旦连续T次的结点访问中都没有找到新的最优值,我们就会额外花费t的时间来寻找可以剪枝的结点,这样又减少了大量搜索所消耗的时间.时间t的计算如下:设当前访问的结点wNode的深度为d,那么访问结点的总次数的最坏情况为

$\begin{align} & \sum\limits_{i=d}^{n}{\sum\limits_{j=1}^{i-1}{|{{W}_{j}}|}}\le (n-d+1)\sum\limits_{i=1}^{n-1}{|{{W}_{i}}|}\le \\ & (n-d+1)\sum\limits_{i=1}^{n-1}{i{{T}_{i}}/{{T}_{1}}}\le \frac{(n-d+1)n(n-1){{T}_{n}}}{{{T}_{1}}}. \\ \end{align}$

因此,t=O(n³T_n).这是一个伪多项式的时间.用MINOS计算线性规划的平均时间为O(n),因此算法1的时间复杂度为O(k_vn+n⁴T_nK_v/T),其中,K_v在实际情况中运行算法2的次数是一个较小的数,因此我们可以把K_v/T看做常数.因此,实际复杂度为O(k_vn+n⁴T_n).

综上,LPS算法的理论时间复杂度为O(n²T_n+n³T_n+N³n+k_vn+n⁴T_n)=O(N³n+k_vn+n⁴T_n).事实上,在实时系统中,T_n是一个有界的变量,因此可以把T_n看做一个常数.而对于采样次数N,我们不可能采集关于n的指数次样本,否则也就失去了采样的意义,因此,采样次数必须是一个关于n的多项式,设N=O(n^a),其中,$\alpha $>0.我们把$\alpha $称为采样因子.当$\alpha $≤1时,O(N³n+n⁴T_n)=O(n⁴);当$\alpha $>1时,O(N³n+n⁴T_n)=O(n^{3$\alpha $+1})≥O(n⁴).因此对任意$\alpha $>0,有O(N³n+n⁴T_n)= O(n^{3$\alpha $+1}).从而在实际情况中,LPS算法的时间复杂度为

O(n3$\alpha $+1+Kvn),$\alpha $>0

(15)

从公式(15)中可以看出:对LPS算法的时间开销起决定性作用的因素在于选取搜索初始最优值以及深度优先搜索,同时,前者的结果又影响后者的运行时间.$\alpha $越大,选取搜索初始最优值的时间开销就越大,但相对地访问的结点总数K_v就越少.

5. 实验结果与分析

本文利用Matlab优化工具包及Matlab的优化工具接口Tomlab^[44]进行实验,比较LPS、基于MBP与基于NLP的3种方法求解实时系统RM优化设计问题所得到的最优值(CPU最大利用率)和时间开销.其中:在LPS方法中,求解线性规划时使用Tomlab中的MINOS包;在基于MBP的方法中,求解混合整数线性规划时使用Tomlab中的CPLEX包.算法实验环境为Windows 7,Intel i7-3770,8GM RAM.

实验条件描述如下:算法的精度为10^-4,任务周期T_i从[50,5000]中均匀、随机地选取.这样选取有两个原因: (1) 区间跨度大,不等式的变量系数范围可以在1~100之间;(2) 各个系数的值会尽量保证不同.任务执行时间 C_i的区间为$\left[ \frac{1}{10n}{{T}_{1}},\lambda {{T}_{i}} \right],$其中,l在[0.4,0.6]之间随机选取.这是因为3种方法均为优化算法,必须保证每个问题均有可行解,变量下界T₁/10n能够保证每个问题都有可行解;变量上界的设定是为了保证当所有运行时间均达到上界时系统一定不可调度,从而才能够发挥各方法的作用.在基于NLP的方法中,为了在保证实验精度范围内使得运行时间较短,根据公式(4)我们设定Δv的值也为10^-4.在基于MBP的方法中,M值的数量级至少应是所有在算法中出现的常数值数量级的两倍,注意到,任务周期最大是5 000,从而将M定为10⁸.在LPS方法中,设置$\varepsilon $=0.02.T=max(1000,40n)为未更新最优值情况下的连续搜索结点最大数,n越大,T越大.为了在采样过程中不耗费大量时间,同时又能获得一个较大的结果,我们设定采样周期为N_p=ln|w|,采样最大数量N=10N_p.对相同的任务数n,随机生成10组任务集进行实验,将得到的10个结果的平均值作为实验结果.实验结果见表1.

从表1中可以看出:LPS方法与基于MBP的方法所得到的最优值相同;而基于NLP的方法得到的最优值就小于LPS与基于MBP的方法,这是因为使用基于NLP的方法很容易掉入局部最优值.当n较小时,基于MBP的方法运行时间最少;但随着n的增大,运行时间陡然增加;当n>30时,几乎不能算出结果来.而此时,LPS的优势逐渐显现出来.基于MBP的方法失效的原因主要有3点:(1) 问题搜索空间大,算法运行时间随规模呈指数增长; (2) 当中间迭代点出现多个非整数分量时,目前没有理论告诉我们最好的选择策略,只能是进行随机选择,不能够提升算法性能;(3) 该方法引入了相当于原问题1倍数量的变量,这也增大了该方法的运行时间.当n>50时,基于NLP的方法的运行时间大幅增加,而LPS仍然能在较短的时间内得到最优解(如图2所示).基于NLP的方法在这种情况下失效的原因有两点:一是该方法把原来的线性约束优化变成了一个非线性约束优化问题,而非线性约束优化算法相比于线性约束优化算法有本质的区别,其时间复杂度远高于线性约束优化算法;另一方面,除变量自身的区间约束条件外,该方法将其余每个线性不等式的长度被扩大了1倍,这也增加了运行处理的时间.因此:在n比较小时,选择基于MBP的方法;当n稍大时,可以选择LPS或基于NLP的方法;当n很大时,就应该选择LPS方法.

实验结果还表明,LPS方法所产生的线性规划搜索树的结点个数是随n增长而呈指数级增长的.但实际的搜索结点数与任务数并不是指数的关系,事实上,利用对线性规划搜索树进行剪枝,实际访问的结点数只占总结点数的很少一部分.

6. 结论及未来工作

本文提出了一种新的实时系统RM优化设计算法——基于树状的线性规划搜索(LPS)方法.首先将RM优化设计模型分拆成若干个线性规划子问题,再构造线性规划问题的搜索树,利用深度优先搜索及其剪枝算法,找到线性规划子问题中最大的最优值,从而得到了CPU利用率最大值.与已有的两种方法相比,LPS方法的运行速度更快;尤其当任务数量较大时,LPS仍然能在较短的时间内运行,但基于NLP和MBP的方法已经不能适用.

本文的工作可以与计算机可满足性模定理(satisfiability modulo theories,简称SMT)领域^[45]的多个研究热点问题联系起来.提出的LPS方法可以求解SMT中线性运算(linear arithmetic)部分的可满足性及优化问题^{[46, 47, 48]}.我们接下来将比较研究SMT求解器Z3^[49]、Yices^[50]以及基于SMT的优化求解器OPT-MathSAT^[47]、Symba^[48]的线性运算部分,进一步改进LPS方法,提高SMT中线性运算部分的可满足性和优化问题的求解效率.