基于拓扑排序资源约束下多项目调度优化算法

多项目调度存在着工期和资源的竞争,调度时要考虑时序关系和资源受限两方面约束,启发式串行调度算法在每调度一个任务时都必须搜索项目的任务空间,为此提出了一种基于拓扑排序的多项目串行调度优化算法。此算法利用拓扑排序序列的特点保证任务时序关系,缩小调度时搜索空间,结合项目权重、向后影响度以及关键路径等优先规则进行资源分配和任务调度。通过具体实例验证了此算法可以求得项目调度的最优解并且能够有效地缩短调度计划生成时间。

Resource-constrained Multi-project Scheduling Algorithm Based on Topology Sorting

Multi-project scheduling problem is constrained by precedence and resource constraints.Heuristic serial scheduling algorithm needs to search the whole task space.To solve multi-project scheduling problem,an optimized serial scheduling algorithm based on topology sorting is proposed.Topology sorting keeps the precedence constraints in the schedule,therefore,with the merit of topology sorting the algorithm combines several priority rules to optimize resource allocation and task scheduling.The performance and feasibility of the algorithm is verified by a concrete instance.