具有优先链约束的网格作业多资源调度问题

摘要

网格计算是网络并行计算的发展新趋势,网格系统中的分布式资源管理和调度一直是研究的热点和难点.对于网格应用作业的多资源调度问题,一个网格作业往往要分成多步骤进行,每个步骤都需要占用多个资源.首先将该问题抽象为典型的多处理机任务调度模型Pm|fix,p=1,chain|Cmax,即在m个处理机系统中调度n个多处理机任务,每个任务指派到所需一组处理机上不可剥夺地执行,而且每个任务都需要一个单位的处理时间,并根据优先关系形成链约束.该问题被证明为NP难问题.利用宽度优先技术和首次满足方法,构建了几个多项式时间近似算法,并通过模拟实验分析算法性能,实验结果显示算法是实用的.