|Title||Uniprocessor Scheduling Policy for Non-Preemptive Task Sets with Precedence and Temporal Constraints|
|Publication Type||Conference Proceedings|
|Year of Conference||2012|
|Authors||Gombolay, M. C., and J. A. Shah|
|Conference Name||AIAA Infotech@Aerospace (I@A) [Best Intelligent Systems Paper]|
We present an idling, dynamic priority scheduling policy for non-preemptive task sets with precedence, wait constraints, and deadline constraints. The policy operates on a well-formed task model where tasks are related through a hierarchical temporal constraint structure found in many real-world applications. In general, the problem of sequencing according to both upperbound and lowerbound temporal constraints requires an idling scheduling policy and is known to be NP-complete. However, we show through empirical evaluation that, for a given task set, our polynomial-time scheduling policy is able to sequence the tasks such that the overall duration required to execute the task set, the makespan, is within a few percent of the theoretical, lowerbound makespan.