路程昭, 龚建兴, 朱 雷, 刘 权

(国防科技大学智能科学学院, 湖南 长沙 410073)

0 引 言

资源约束条件下的任务调度问题(resource-constrained task scheduling problem, RCTSP)是一个涉及众多领域的关键问题,比如并行计算、软件开发和工程建造等。特别在应急管理领域(如地震救援和突发公共卫生事件),该问题是影响应急处置效果的核心问题。RCTSP通常存在任务之间关系复杂、资源紧缺或补充不及时的特点,被证明是NP完全问题[1],复杂度高,实现高效任务调度和资源分配难度大。

针对RCTSP,国内外学者已经进行了大量的研究,涉及云计算[2-5]、分布式系统[6-7]、流水线生产[8]等多个领域。研究内容还包括问题的分析、建模、求解、应用等多个方向,例如,Orr[9]基于分配排序模型,提出了一种状态空间模型,用于解决存在重复任务的最优调度问题,任务重复调度可以缩短时间表总长度,并且可以给出最佳的任务重复计划;Krishnakumar[10]提出了一种基于模仿学习的方法,用于在处理无线通讯和雷达系统应用程序的多核心平台进行任务调度,通过提供一个分层学习框架,从已开发的任务调度策略学习,最大程度减少应用程序执行时间;田启华[11]采用多目标理想法构造评价函数,选择最优任务调度方法;Wang[12]建立了一种新型的分布式成像卫星紧急任务多目标动态调度模型,提出了一种综合考虑任务合并、后移、复原的动态调度算法;Yuan[13]根据早期树对所有任务进行分组,对于关键活动和非关键活动采用不同的优化算法;Lin[14]针对多技能资源受限……