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 al...

Full description

Saved in:
Bibliographic Details
Published in:Journal of computer & systems sciences international 2014-09, Vol.53 (5), p.702-712
Main Authors: Gruzlikov, A. M., Kolesov, N. V., Skorodumov, Yu. M., Tolmacheva, M. V.
Format: Article
Language:English
Subjects:
Algorithms
Analysis
Assignment problem
Channels
Communication channels
Computer Methods
Control
Distributed processing
Dynamic programming
Dynamical systems
Efficiency
Employment
Engineering
Graph algorithms
Graph theory
Graphs
Heuristic
Information communication
Mechatronics
Optimization
Packing problem
Principles
Processors
Real time
Robotics
Studies
Tasks
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:1064-2307
1555-6530
DOI:10.1134/S106423071404008X