OPTIMAL SCHEDULING OF COOPERATIVE TASKS IN A DISTRIBUTED SYSTEM USINGAN ENUMERATIVE METHOD

This paper considers preemptive (resume) scheduling of cooperative tas ks that have been preassigned to a set of processing nodes in a distri buted system, where each task is assumed to consist of several modules . During the course of their execution, these tasks communicate with e ach other to collectively accomplish a common goal. Such intertask com munications lead to precedence constraints between the modules of diff erent tasks. Our scheduling objective is to minimize the maximum norma lized task response time, called the system hazard. Real-time tasks an d the precedence constraints among them are expressed in a PERT/CPM fo rm with activity on arc (AOA), called the task graph (TG), in which do minance relationship between simultaneously schedulable modules is der ived and used to reduce the size of the set of active schedules to be searched for an optimal schedule. Lower-bound costs are estimated, whi ch are then used to bound the search. Finally, a demonstrative example and some computational experiences are presented.