This paper describes a new and different paradigm for real-time command and control that we show can provide a static, polynomial-time scheduling algorithm. Current efforts in real -time scheduling have been unable to predict system performance, and use a unpredictable "dynamic" scheduling algorithm. The Nation’s Air Traffic Control (ATC) System has been unable to satisfy performance requirements, and is extremely expensive. An editorial in "USA Today" (419-1999) cites expenditures in ATC at $41 billion. But, current multiprocessor technology cannot do the job. The FAA wisely required a “proof of concept” study before the (AAS) contract. But that study, after expending a billion dollars, was abandoned, and production moved forward. AAS was canceled in 1995 exactly in line with real-time scheduling theory predictions. Garey, Graham, and Johnson state: "For these scheduling problems, no efficient optimization algorithm has yet been found, and indeed, none is expected.”[9]. Stankovic et. al. state: "…complexity results show most real-time multiprocessing scheduling is NP -hard.” [6]. We offer a completely different approach, that has been shown to overcome the severe limitations of multiprocessi ng. Additionally, we show that real-time parallel-processing techniques can be statically scheduled to solve the set of tasks making up the ATC problem for a worst-case environment.

Original document

The different versions of the original document can be found in:

Back to Top

Document information

Published on 01/01/2005

Volume 2005, 2005
DOI: 10.1109/ipdps.2001.925204
Licence: CC BY-NC-SA license

Document Score


Views 0
Recommendations 0

Share this document


claim authorship

Are you one of the authors of this document?