Multi-users scheduling in parallel systems
Multi-users scheduling in parallel systems
复制标题
DOI：
10.1109/ipdps.2009.5161037
复制
发表时间：
2009-05
期刊：
影响因子：
--
通讯作者：
Erik Saule;D. Trystram
中科院分区：
文献类型：
--
作者：
Erik Saule;D. Trystram
我们有兴趣在本文中研究调度问题的系统中，许多用户竞争，以执行各自的工作共享并行资源。每个用户都有特定的需求或愿望，用于计算他/她的工作，表示为一个函数，以优化（在最大完成时间，完成时间和加权完成时间之和）。这些问题主要是通过博弈论来研究的。在这项工作中，我们专注于解决问题，同时优化每个用户的目标函数独立使用经典的组合优化技术。一些结果已经提出了两个用户在一个单一的计算资源。然而，没有通用的组合方法是已知的许多目标。本文提出的分析涉及任意固定数量的用户，并不限于一个单一的资源。我们首先推导出不可逼近性界限;然后分析几种逼近比接近这些界限的贪婪启发式算法。然而，由于用户数量呈线性，因此它们仍然很高。我们提供了一个更深入的分析表明，稍微修改的版本的算法是一个常数近似的帕累托最优解。
We are interested in this paper to study scheduling problems in systems where many users compete to perform their respective jobs on shared parallel resources. Each user has specific needs or wishes for computing his/her jobs expressed as a function to optimize (among maximum completion time, sum of completion times and sum of weighted completion times). Such problems have been mainly studied through Game Theory. In this work, we focus on solving the problem by optimizing simultaneously each user's objective function independently using classical combinatorial optimization techniques. Some results have already been proposed for two users on a single computing resource. However, no generic combinatorial method is known for many objectives. The analysis proposed in this paper concerns an arbitrarily fixed number of users and is not restricted to a single resource. We first derive inapproximability bounds; then we analyze several greedy heuristics whose approximation ratios are close to these bounds. However, they remain high since they are linear in the number of users. We provide a deeper analysis which shows that a slightly modified version of the algorithm is a constant approximation of a Pareto-optimal solution.