Scheduling parallelizable jobs on multiprocessors

Abstract

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.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>