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] |
Date Published | 06/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. |
URL | https://interactive.mit.edu/sites/default/files/documents/infotechPaperGombolayShah.pdf |