Optimal scheduling of parallel processing systems with real-time constraints

We consider parallel execution of structured jobs with real time constraints in (possibly heterogeneous) multiprocessor systems. A job is composed of a set of tasks and a partial order specifying the precedence constraints between the tasks. The task processing times are random variables with known probability distribution functions. The interarrival times of the jobs are also random variables with arbitrary distributions. The real time constraints are specified by reference times, also called soft real-time deadlines. In the discussion we assume first that all the jobs have the same task graph, i.e. the same task set and the same partial order. We assume that there is a predefined mapping from the set of tasks onto the set of machines, identical for all jobs, that allocates tasks to machines. We focus on dynamic scheduling policies which do not use information on the processing times of the tasks to be scheduled. The policies can be non-preemptive or preemptive-resume. For non-preemptive policies, we assume that task processing times are independently and identically distributed, whereas for the preemptive ones, we assume that they are independently and identically distributed and come from some specific distributions. Some of the results that are obtained generalize to the case where jobs have a random structure. This more difficult case is treated at the end of the paper. We are interested in such performance criteria as the number of jobs in the system, the throughput in term of jobs and the job lag times, which correspond to the differences between the reference times and the completion times of tasks or jobs. We show that FCFS policies, applied at task level (which imply FIFO for jobs), stochastically minimize the number of jobs and maximize the system throughput. We establish that FCFS policies minimize the vector of the transient response times in the sense of Schur convex ordering, and minimize the stationary response times in the convex ordering sense. Awe c real time applications, we prove that within the class of local order preserving policies that is defined in the paper, the SRF (shortest reference first) and LRF (longest reference first) policies bound respectively from below and from above the lag times vector of the n first jobs, in the Schur convex sense. This in turn yields an analogous convex ordering among the stationary job lag times