王晓丽，王宇平，孟 坤

（西安电子科技大学计算机学院，陕西西安 710071）

考虑处理机释放时间的可分任务调度优化模型

王晓丽，王宇平，孟 坤

（西安电子科技大学计算机学院，陕西西安 710071）

可分任务调度是近年来信息技术领域研究的热点课题.已有的可分任务调度模型大多假设所有处理机在任务分配之初全部处于空闲状态，而实际上，当新的任务到来时很多处理机可能尚处于忙碌状态.每台处理机从忙碌状态转到空闲状态的时间不同，即处理机可能具有不同的释放时间.在充分考虑处理机释放时间不同的基础上，建立了一种新的混合时序约束的可分任务调度模型，并设计了高效的全局优化遗传算法求解该模型.实验结果表明了模型的合理性和算法的有效性.

可分任务调度；释放时间；混合时序约束；遗传算法

在并行与分布式系统中，大规模计算任务的处理逐渐成为了极具挑战性的课题.为系统建立合理且贴近实际的任务调度模型成了该领域最大的难点，其中可分任务调度模型［1-3］就是典型的代表之一.可分任务是指任务可以被切分为任意大小的若干子任务且子任务间不具有优先关系.在并行与分布式系统下，可分任务调度的主要目标是寻求合理的任务调度策略，使得任务的完成时间最短.

针对现实生活中常见的线性网路、总线型网络和树形网络，已经有很多文献研究可分任务调度方案的最优解.例如，文献……