A method for real-time scheduling problems

Author

Shi, Leyuan ; Hwang, Phillip Q.

Author_Institution

Dept. of Ind. Eng., Wisconsin Univ., Madison, WI, USA

fYear

1997

fDate

5-7 Feb 1997

Firstpage

172

Lastpage

176

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;

fLanguage

English

Publisher

ieee

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

Type

conf

DOI

10.1109/WORDS.1997.609950

Filename

609950

Link To Document

https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=2593524