基于逆序层优先的柔性综合调度算法

针对以往柔性综合调度算法均考虑正向调度,导致需要考虑目标工序的多紧前工序约束条件,难以合理安排相关工序进而影响产品完工时间的问题,该文提出一种基于逆序层优先的柔性综合调度算法。首先,提出逆序层优先策略,将各工序分配至逆序层待调度工序集;其次,提出动态拟长路径策略,确定各逆序层待调度工序集中工序的调度顺序;然后,分别提出设备选择策略和设备抢占策略以确定目标工序的加工设备以及加工时间;最后,提出基于完工时间翻转的调度方案转换策略,将逆序调度方案转换为正序调度方案。实例表明,和已有主流算法相比,该算法在不提高算法复杂度的前提下能够缩短产品完工时间。

面向异构分布式计算环境的并行任务调度优化方法

分布式计算环境中并行作业的任务调度策略直接影响应用程序的执行时间,寻找一种使任务执行时间最短的调度方案已被证明是NP(non-deterministic polynomial)完全问题。首先给出了异构分布式计算系统的形式化描述,建立了静态任务调度问题的理论体系,通过分析总结最长动态关键路径(longest dynamic critical path,LDCP)算法的核心思想及存在的不足,提出一种运用结点信息流量减少CPU空闲时间碎片的并行任务调度优化算法,其时间复杂度为O(M×N^3)。实验表明改进后的算法在调度长度、加速比及计算效率3个指标上均优于LDCP算法和分层结点排序算法(sorted nodes in leveled directed acyclic graph division,SNLDD),其中,与LDCP、SNLDD相比,调度长度平均缩短19.03%、8.02%,加速比平均提升18.42%、7.96%,计算效率平均提高10.17%、3.72%,进一步提高了并行系统的资源利用率。