EXTREMAL SCHEDULING OF PARALLEL-PROCESSING WITH AND WITHOUT REAL-TIME CONSTRAINTS

Parallel execution of an arrival stream of jobs with and without real-time constraints on a (possibly heterogeneous) multiprocessor system is considered. A job consists of a set of tasks and a partial order specifying the precedence constraints between the tasks. The real-time constraints are specified by due times, also called soft real time deadlines. It is assumed that there is a predefined mapping from the set of tasks onto the set of machines that is identical for all jobs. Associated with each task is a service time that may depend on the machine that it is allocated to. The problem of scheduling tasks into execution at each machine is the subject of this paper. Dynamic nonpreemptive scheduling policies that do not use service-time information is examined and a class of Local Order Preserving (LOP) policies that contains the class of nonidling First Come First Serve (FCFS) policies is defined. It is shown that policies from this last class, along with the classes of LOP Shortest Due Time First (SDTF), LOP Largest Due Time First (LDTF), and LOP Last Come First Serve (LCFS) policies stochastically minimize the number of jobs in the system and maximize the job throughput. The class of FCFS policies is further shown to minimize the vector of transient response times in the increasing Schur convex sense. Last, we consider the job lateness, the difference between the due time and the completion time of the job, and prove that within the class of LOP policies, the SDTF and LDTF policies bound, respectively, from below and from above the transient vector of the job latenesses, in the Schur convex sense. The paper concludes with extensions to the steady state performance metrics, to the class of preemptive-resume policies, and to jobs having random task graphs. All of the results, except those concerned with preemptive policies, assume that task service times form mutually independent sequences of independent and identically distributed random variables. In the latter case, service times are further assumed to be exponential random variables.