Scheduling parallelizable jobs on multiprocessors

Ching Chih Han*, Kwei Jay Lin

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

24 Scopus citations


The effect of parallel execution on the complexity of scheduling hard real-time jobs on multiprocessors is analyzed. Studied is the scheduling problem in which a job may be parallelized and executed on any number of processors concurrently. In hard real-time systems, each job must be completed before a deadline. Parallelization gives a scheduler the flexibility to allocate more processors to a job whose deadline is near. Unfortunately, with this flexibility some of the multiprocessor scheduling problems are very difficult. The NP-hardness of scheduling parallelizable jobs where each job has a fixed priority is proved. A heuristic algorithm is proposed for finding an approximate job partition on two processors. Simulation results show that the heuristic algorithm usually has a very good performance.

Original languageEnglish
Title of host publicationProceedings - Real-Time Systems Symposium
Editors Anon
PublisherPubl by IEEE
Number of pages9
ISBN (Print)0818620048
StatePublished - 1989
Externally publishedYes
EventProceedings - Real-Time Systems Symposium - Santa Monica, CA, USA
Duration: 05 12 198907 12 1989

Publication series

NameProceedings - Real-Time Systems Symposium


ConferenceProceedings - Real-Time Systems Symposium
CitySanta Monica, CA, USA


Dive into the research topics of 'Scheduling parallelizable jobs on multiprocessors'. Together they form a unique fingerprint.

Cite this