We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
A Message-Passing Approach to Decentralized Parallel Machine Scheduling.
- Authors
Vinyals, Meritxell; Macarthur, Kathryn S.; Farinelli, Alessandro; Ramchurn, Sarvapali D.; Jennings, Nicholas R.
- Abstract
This paper tackles the problem of parallelizing heterogeneous computational tasks across a number of computational nodes (aka agents) where each agent may not be able to perform all the tasks and may have different computational speeds. An equivalent problem can be found in operations research, and it is known as scheduling tasks on unrelated parallel machines (also known as R∥Cmax). Given this equivalence observation, we present the spanning tree decentralized task distribution algorithm (ST-DTDA), the first decentralized solution to R∥Cmax. ST-DTDA achieves decomposition by means of the min–max algorithm, a member of the generalized distributive law family, that performs inference by message-passing along the edges of a graphical model (known as a junction tree). Specifically, ST-DTDA uses min–max to optimally solve an approximation of the original R∥Cmax problem that results from eliminating possible agent-task allocations until it is mapped into an acyclic structure. To eliminate those allocations that are least likely to have an impact on the solution quality, ST-DTDA uses a heuristic approach. Moreover, ST-DTDA provides a per-instance approximation ratio that guarantees that the makespan of its solution (optimal in the approximated R∥Cmax problem) is not more than a factor ρ times the makespan of the optimal of the original problem. In our empirical evaluation of ST-DTDA, we show that ST-DTDA, with a min-regret heuristic, converges to solutions that are between 78 and 95% optimal whilst providing approximation ratios lower than 3.
- Subjects
HETEROGENEOUS computing; DECENTRALIZED control systems; COMPUTATIONAL complexity; PARALLEL computers; HEURISTIC algorithms
- Publication
Computer Journal, 2014, Vol 57, Issue 6, p856
- ISSN
0010-4620
- Publication type
Article
- DOI
10.1093/comjnl/bxt140