A Message-Passing Approach to Decentralized Parallel Machine Scheduling

作者：Vinyals Meritxell^*; Macarthur Kathryn S; Farinelli Alessandro; Ramchurn Sarvapali D; Jennings Nicholas R

来源：Computer Journal, 2014, 57(6): 856-874.

DOI：10.1093/comjnl/bxt140

• parallel machine scheduling
• task-allocation
• min-max
• decentralized coordination
• bounded approximation
• GDL
• junction tree

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 parallel to C-max). Given this equivalence observation, we present the spanning tree decentralized task distribution algorithm (ST-DTDA), the first decentralized solution to R parallel to C-max. 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 parallel to C-max 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 make span of its solution (optimal in the approximated R parallel to C-max problem) is not more than a factor rho times the make span 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.

• 出版日期2014-6