基于连续效用子集的资源分配算法

作者：王皓轮; 倪宏; 郭志川

来源：中国科学技术大学学报, 2013, (04): 287-294.

• 效用
• 资源分配
• 启发式算法
• 实时系统 utility
• resource allocation
• heuristic
• real-time system

基于离散资源配置选项的实时(或软实时)系统资源分配问题,当以系统整体效用最大化为目标时,属于多维多选择背包问题,直接求解最优值的时间复杂度较高.现有的研究中主要通过使用启发式算法,将其时间复杂度降低为多项式级.这些启发式算法不考虑离散资源配置选项之间的联系,因此在求解中存在一些不必要的计算,而且分配结束后的残留资源不能得到利用.为此通过定义连续效用子集,分析了同一个任务的不同资源配置选项之间的联系.对已有的启发式算法HEU加以改进,提出启发式算法(T-HEU),能够用较低的时间复杂度获得与HEU算法相同的结果.根据同一个连续效用子集中的资源消耗函数的连续性,将残留资源分配问题近似归结为线性规划...

• 出版日期2013
• 单位中国科学院声学研究所; 中国科学技术大学