Title :
A method for real-time scheduling problems
Author :
Shi, Leyuan ; Hwang, Phillip Q.
Author_Institution :
Dept. of Ind. Eng., Wisconsin Univ., Madison, WI, USA
Abstract :
Many real-time scheduling problems have been proven to be NP-hard. Recently (1996), we proposed a randomized optimization framework for efficiently solving such NP-hard problems. The proposed method, called the nested partitions (NP) method, is proved to converge to global optimal solutions and it is also highly matched to emerging massively parallel processing capabilities. In particular, we apply the NP method to solve the scheduling of real-time tasks with minimum jitter
Keywords :
computational complexity; convergence; distributed algorithms; jitter; optimisation; parallel processing; processor scheduling; real-time systems; NP-hard problems; convergence; global optimal solutions; massively parallel processing; minimum jitter; nested partitions method; randomized optimization framework; real-time scheduling problems; Communication systems; Image converters; Industrial engineering; Jitter; Job shop scheduling; NP-hard problem; Partitioning algorithms; Polynomials; Processor scheduling; Real time systems;
Conference_Titel :
Object-Oriented Real-Time Dependable Systems, 1997. Proceedings., Third International Workshop on
Conference_Location :
Newport Beach, CA
Print_ISBN :
0-8186-8046-6
DOI :
10.1109/WORDS.1997.609950
