A Task Scheduling Algorithm In PAC System Based On Heuristic Shortest Path

In recent years, Programmable Automation Controller (PAC) is widely researched and used since the proposal of its concept as an general-type automation platform in conventional industrial control. PAC system is a typical real-time system with hybrid tasks including a variety of functional modules such as Human-Machine Interface, PLC and Motion Controller. PAC system needs specific requirement of task schedulnig mechanism.In this paper, task scheduling theory on real-time system is researched and for the important issue of scheduling algorithm in task scheduling theory, terms of algorithm classification, scheduling strategy, performance evaluation indicator are discussed in detail. The status of reseach and proposed algorithms are also concluded and the problems of practical application in real-time system of task scheduling theory are analyzed.To describe the characteristics of PAC real-time system, which is consisting of hybrid tasks with precedence orders and resource constraints, a new model of hybrid-task system is introduced. A shortest-path algorithm (SPA) based on heuristic search is presented to schedule the task sets. By searching state nodes in the state-space tree and minimizing the value of heuristic evaluation function, SPA works out the problem with an optimal solution. The provement of the structural condition of the heuristic evaluation function in SPA is given and the applicability of the algorithm is discussed.Based on the specific characteristics and application requirements of PAC real-time system, task partition of PAC system and task time constraints are established, and a heuristic evaluation function is also structured. The design, flow charts, pseudo-code and data structures of SPA are descripted in detail. SPA is implemented in the real-time kernel of PAC system, and performance of SPA is tested through case analysis and algorithm testing, results show that the actural operating performance consists with expected results by theoretical analysis, proving the high value industrial application of SPA proposed in this paper.