Graph Approach to Job Assignment in Distributed Real-Time Systems

摘要

Two heuristic algorithms for assigning jobs to processors of a distributed real-time system are proposed and studied. Each job is described by a directed graph of sufficiently general form. The first algorithm is based on the principle of assigning adjacent tasks to the processor while the second algorithm is based on the principle of assigning tasks with most intensive communication. Efficiency of these algorithms is studied as compared to optimal one and using the random generation of examples. For each algorithm, the domain of efficient application is found and given by the value of the ratio of processor/communication channel costs.