Heuristic algorithms for task assignment in distributed systems
Virginia M. Lo · IEEE Transactions on Computers · 1988
Investigate the problem of static task assignment in distributed computing systems, i.e. given a set of k communicating tasks to be executed on a distributed system of n processors, to which processor should each task be assigned? The author proposes a family of heuristic algorithms for Stone's classic model of communicating tasks whose goal is the minimization of the total execution and communication costs incurred by an assignment. In addition, she augments this model to include interference costs which reflect the degree of incompatibility between two tasks. Whereas high communication costs serve as a force of attraction between tasks, causing them to be assigned to the same processor, interference costs serve as a force of repulsion between tasks, causing them to be distributed over many processors. The inclusion of interference costs in the model yields assignments with greater concurrency, thus overcoming the tendency of Stone's model to assign all tasks to one or a few processors. Simulation results show that the algorithms perform well and in particular, that the highly efficient Simple Greedy Algorithm performs almost as well as more complex heuristic algorithms.>
Cited by 440 works. doi:10.1109/12.8704
Authors
References
- The Contract Net Protocol: High-Level Communication and Control in a Distributed Problem Solver
- Multiprocessor Scheduling with the Aid of Network Flow Algorithms
- Task Allocation in Distributed Data Processing
- Models for Dynamic Load Balancing in a Heterogeneous Multiple Processor System
- Control of Distributed Processes
- Heuristic Models of Task Assignment Scheduling in Distributed Systems
- Dual Processor Scheduling with Dynamic Reassignment
- Critical Load Factors in Two-Processor Distributed Systems
- Heuristic algorithms for task assignment in distributed systems
- A Graph Matching Approach to Optimal Task Assignment in Distributed Computing Systems Using a Minimax Criterion