Maximal throughput for stability of a class of parallel processing systems

Abstract

Considered are a parallel processing system consisting of a finite number of identical processors that can work concurrently, and a random stream of arriving jobs, each requiring for its execution a random number of processors to be engaged concurrently for some random processing time. Arriving jobs are placed in an infinite capacity buffer and are allocated to the processors to be executed nonpreemptively. The arrival times, the number of concurrently required processors, and the processing times of the jobs form a stationary and ergodic sequence. The queueing theoretic stability aspects of this system raised because of the infinite capacity buffer are discussed. It is concluded that if the arrival date lambda * of jobs to the system is greater than some threshold value lambda *, the system is unstable under any possible processing scheme (allocation policy of jobs to processors) used to operate it. However, for any arrival rate lambda less than lambda *, a processing scheme is constructed which keeps the system stable.