Uniprocessor Scheduling Policy for Non-Preemptive Task Sets with Precedence and Temporal Constraints

TitleUniprocessor Scheduling Policy for Non-Preemptive Task Sets with Precedence and Temporal Constraints
Publication TypeConference Proceedings
Year of Conference2012
AuthorsGombolay, M. C., and J. A. Shah
Conference NameAIAA Infotech@Aerospace (I@A) [Best Intelligent Systems Paper]
Date Published06/2012
Abstract

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.

URLhttps://interactive.mit.edu/sites/default/files/documents/infotechPaperGombolayShah.pdf