A decomposition approach to real-time scheduling on a single resource
Xiaoping Yuan · 1992
Consider the problem of scheduling a set of n tasks on a single resource such that a feasible schedule that satisfies each task's time constraints is generated. It is recognized that an exhaustive search may be required to generate such a feasible schedule, or to assure that there does not exist one. In that case the number of schedules to be examined in the search is $O$(n!). We propose a new approach called the decomposition scheduling which is able to cut the scheduling cost substantially. In this approach, a schedule is generated in two phases. In the first phase we decompose the set of tasks into a sequence of m subsets by analyzing their relationships with regard to the ready times, deadlines and computation times. An ordering of these subsets is specified such that in a feasible schedule all tasks in an earlier subset in the ordering appear before tasks in a later subset. In the second phase, tasks in each subset are scheduled in the sequence order with minimum schedule length. We propose an algorithm which can always find a feasible solution for each subset in the sequence, if one exists. Instead of enumerating all the possible schedules in a subset to determine the feasible solution, the algorithm searches over a super-sequence where only a small number of all possible task positions in schedules are considered. The searching strategy assures that our approach can find any feasible schedule, if one exists. Further, due to properties of the decomposition, the backtracking in the subset scheduling is restricted within each subset. Thus, the decomposition scheduling is also very efficient, depending on subset size. Simulation experiments were conducted to analyze the performance of decomposition scheduling approach. The experimental results show that in many cases the decomposition scheduling is a much better approach than others, namely the earliest-deadline-first and two variations of an algorithm introduced in (Zhao87b), in both percentage of finding feasible schedules over randomly-generated task sets, and scheduling cost. We further extend the decomposition scheduling results to specific cases: incremental scheduling, and scheduling with precedence relations.