基于启发式最短路径的PAC任务调度算法

Task Scheduling Algorithm in PAC System Based on Heuristic Shortest Path

针对PAC实时系统中多种类型任务共存、部分任务之间具有时序相关性的特点,建立了混合关联任务系统的数学模型,将系统中待调度的任务看作构成状态空间树的状态节点,使任务执行序列的选择问题转化为状态空间树中寻找状态节点之间最短路径的问题;基于启发式搜索最短路径算法实现了PAC系统的任务调度机制,该算法通过在线搜索问题的状态空间树,在约束条件下寻找使代价评估函数取得极值的状态节点,从根节点出发并不停地寻找下个节点作为首发任务的后续任务,当根节点通过某条路径可以连接所有节点时,便形成了一个最优且可行的任务执行队列;实例分析和算法性能测试表明,该算法能较好地应用于PAC实时系统的任务调度中。

To describe the characteristics of PAC （ Programmable Automation Controller ） real-time system, which is consisting of hybrid tasks with precedence orders and resource constraints, a new model of hybrid-task system was introduced. State space tree node was considered as the task to be scheduled, making the task execution serial choice problem into the shortest path problem in state space tree node.Based on heuristic search of shortest path algorithm to achieve the PAC system task scheduling mechanism, through online search problem of state space tree, under the constraint condition, local node making cost evaluation function acquire extremum was searched.Starting from the root node, the next node was seen as the subsequent task.When the root node can connect all the nodes through a certain path, an optimal and feasible task queue was formed.Case study and computation complexity analysis prove that the algorithm is able to obtain the optimized sequence of hybrid task sets in PAC system effectively.