Scheduling Monotone Moldable Jobs in Linear Time
Scheduling Monotone Moldable Jobs in Linear Time
复制标题
在线性时间内调度单调可塑作业
DOI：
10.1109/ipdps.2018.00027
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Felix Land
中科院分区：
文献类型：
--
作者：
K. Jansen;Felix Land
可塑作业是可以在任意数量的处理器上执行的作业，其处理时间取决于分配给它的处理器数量。如果一个可塑作业的工作量没有随着分配的处理器数量的增加而减少，那么它就是单调的。研究了以最大完工时间为目标的单调可塑作业调度问题。我们认为，对于某些紧凑的输入编码，多项式算法具有n和log(m)的运行时间多项式，其中n是作业的数量，m是机器的数量。我们描述了如何使用作业的单调性来抵消由紧凑编码引起的问题复杂性的增加，并给出了紧凑编码问题的近似性的严格界限：它是np困难的最优解，但承认PTAS。这项工作的主要焦点是有效的近似算法。我们描述了利用作业的单调性来提高运行时间的不同技术，并给出了一个（3/2+?）-近似算法，其运行时间为log(m)的多项式和1/？，并且工作的数量是线性的。
A moldable job is a job that can be executed on an arbitrary number of processors, and whose processing time depends on the number of processors allotted to it. A moldable job is monotone if its work doesn't decrease for an increasing number of allotted processors. We consider the problem of scheduling monotone moldable jobs to minimize the makespan. We argue that for certain compact input encodings a polynomial algorithm has a running time polynomial in n and log(m), where n is the number of jobs and m is the number of machines. We describe how monotony of jobs can be used to counteract the increased problem complexity that arises from compact encodings, and give tight bounds on the approximability of the problem with compact encoding: it is NP-hard to solve optimally, but admits a PTAS. The main focus of this work are efficient approximation algorithms. We describe different techniques to exploit the monotony of the jobs for better running times, and present a (3/2+?)-approximate algorithm whose running time is polynomial in log(m) and 1/?, and only linear in the number n of jobs.
影响因子：
0.8
作者：
Jansen, K.;Land, F.;Land, K.
通讯作者：
Land, K.