5.4.2 DPS算法思路
更新于 2026年11月21日
版权声明
5.4.2 DPS算法思路
本书先以实例阐明DPS 算法思路,再给出主要步骤。设有一任务集
如表5-1 所示。
表5-1 任务集实例

由于ξ4是截止时间最早的关键元组,因此ξ4必须在ξ4[T]=τ+δ-ξ4[C]=108 时刻被调度,那么接下来的问题就是在
中寻找最优节能调度。ξ6由于ρ6值低于关键元组ξ4的ρ4,排除在调度之外,因此根据功耗因子ρ值进行高低排序得到进入时间段[102,108]调度的序列为 (ξ5,ξ1,ξ3,ξ2)。下面我们基于这个序列分步考虑。
初始化:S0={ { ∅},FP0(0)=0}
第一步,对ξ5进行决策:舍ξ5,FP1(0)=0;取ξ5,FP1(ξ5[C])=FP1(4)=20,合并得到解集:
S1={ {{ ∅},FP1(0)=0)},{{ ξ5},FP1(4)=20}}
第二步,对ξ1进行决策:舍ξ1,FP2(0)=0,FP2(4)=20;取ξ1,FP2(3)=12,FP2(7)=32,合并得到解集:

第三步,对ξ3进行决策:舍ξ3,解集就是S2;取ξ3,得到解集
:
(https://www.daowen.com)
其中 {{ξ1,ξ5,ξ3},FP3(10)=41} 解集超出问题的定义域0 ≤Ω≤7,舍去。合并S2,
′ 得到解集:

第四步,对ξ2进行决策:舍ξ2,解集就是S3;取ξ2,并排除已经超出定义域的解并得到解集
′:

合并S3,
得到解集S4:

从S4可以容易得到FP4(7)=32 为最优解,最优节能解集为 {ξ1,ξ5}。
算法5.1 DPS步骤

续表
