A 3/2-Approximation Algorithm for the Graph Balancing Problem with Two Weights
A 3/2-Approximation Algorithm for the Graph Balancing Problem with Two Weights
复制标题
具有两个权值的图平衡问题的3/2近似算法
作者：
Daniel R. Page;Roberto Solis
在追求找到子类的最大完工时间最小化问题的不相关的并行机，具有近似比优于2的近似算法，图平衡问题一直是当前的兴趣。在图平衡问题中，每个作业都可以在最多两台机器中的一台机器上进行非抢占式调度，并且在这两台机器上的处理时间相同。最近，Ebenlendr、Krcal和Sgall（Micromica 2014，68，62-80.）提出了一种求解图平衡问题的7 / 4近似算法。设r，s ∈ Z + .本文研究了具有两个权值的图平衡问题，其中一个工件需要r个时间单位或s个时间单位。我们提出了一个3 / 2近似算法解决这个问题。这是一个改进，以前最知名的近似算法的问题，近似比1.652，它匹配最知名的不可逼近性界限。
In the pursuit of finding subclasses of the makespan minimization problem on unrelated parallel machines that have approximation algorithms with approximation ratio better than 2, the graph balancing problem has been of current interest. In the graph balancing problem each job can be non-preemptively scheduled on one of at most two machines with the same processing time on either machine. Recently, Ebenlendr, Krcal, and Sgall (Algorithmica 2014, 68, 62–80.) presented a 7 / 4 -approximation algorithm for the graph balancing problem. Let r , s ∈ Z + . In this paper we consider the graph balancing problem with two weights, where a job either takes r time units or s time units. We present a 3 / 2 -approximation algorithm for this problem. This is an improvement over the previously best-known approximation algorithm for the problem with approximation ratio 1.652 and it matches the best known inapproximability bound for it.