Makespan Minimization via Posted Prices
Makespan Minimization via Posted Prices
复制标题
通过公布价格最小化完工时间
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
A. Roytman
中科院分区：
文献类型：
--
作者：
M. Feldman;A. Fiat;A. Roytman
我们考虑作业调度设置，有多台机器，其中作业在线到达，并自私地选择一台机器，以最小化它们的成本。我们的目标是经典的makespan最小化目标，它对应于最后一个要完成的任务的完成时间。自私工作的激励可能会导致糟糕的表现。为了调和不同的目标，我们引入了贴出的机器价格。自私的作业寻求最小化其在机器上的完成时间和机器的张贴价格的总和。价格可能是静态的（即，在任何到来之前一次性设定）或动态的（即，随时间变化），但它们仅由过去决定，不考虑即将发生的事件。显然，这样的计划本质上是真实的。我们考虑竞争比：定价方案的最大完工时间与最优算法的最大完工时间之比。我们对相同的、受限的、相关的和不相关的机器设置的动态和静态定价方案的竞争比率给出了严格的界限。我们的主要结果是相关机器的动态定价方案，该方案给出了恒定的竞争比率，基本上与在线算法的竞争比率相匹配。相比之下，对于不相关的机器，动态定价的性能很差。这个下限也显示了定价与在线算法之间的差距。
We consider job scheduling settings, with multiple machines, where jobs arrive online and choose a machine selfishly so as to minimize their cost. Our objective is the classic makespan minimization objective, which corresponds to the completion time of the last job to complete. The incentives of the selfish jobs may lead to poor performance. To reconcile the differing objectives, we introduce posted machine prices. The selfish job seeks to minimize the sum of its completion time on the machine and the posted price for the machine. Prices may be static (i.e., set once and for all before any arrival) or dynamic (i.e., change over time), but they are determined only by the past, assuming nothing about upcoming events. Obviously, such schemes are inherently truthful. We consider the competitive ratio: the ratio between the makespan achievable by the pricing scheme and that of the optimal algorithm. We give tight bounds on the competitive ratio for both dynamic and static pricing schemes for identical, restricted, related, and unrelated machine settings. Our main result is a dynamic pricing scheme for related machines that gives a constant competitive ratio, essentially matching the competitive ratio of online algorithms for this setting. In contrast, dynamic pricing gives poor performance for unrelated machines. This lower bound also exhibits a gap between what can be achieved by pricing versus what can be achieved by online algorithms.
DOI：
10.1109/focs.2015.39
发表时间：
2014-11
期刊：
2015 IEEE 56th Annual Symposium on Foundations of Computer Science
影响因子：
--
作者：
Sungjin Im;Nathaniel Kell;Janardhan Kulkarni;Debmalya Panigrahi
通讯作者：
Sungjin Im;Nathaniel Kell;Janardhan Kulkarni;Debmalya Panigrahi