关键词: 调度问题, 周期任务, 非抢占式调度, 调度算法, 剪枝算法

Abstract: Many actual resource schedule problems for different tasks have timeliness, but few research has been focused on this kind of problem. This paper studies the problem, discusses the difference with some models that have been studied well, then proposes a new schedule model for non-preemptive periodic tasks, and proves the problem to be NP-Complete problem. After that, this paper gives two algorithms to solve the schedule problem, one for optimal solutions called pattern pruning algorithm, and the other for approximation solutions called fast solving algorithm. The experimental result shows that the algorithms can deal the schedule problem efficiently according to different situation.

Key words: schedule problem, periodic task, non-preemptive scheduling, schedule algorithm, pruning algorithm