论文标题
使用块类冲突图的作业调度算法近似算法
Approximation algorithms for job scheduling with block-type conflict graphs
论文作者
论文摘要
在本文中考虑了在MakePAN最佳标准下以模型为块图的不兼容关系，在平行机上安排作业（相同，统一或无关）的问题。该关系中的关系中没有两个作业（在同一块中等效）可以在同一机器上安排在此模型中。 提出的模型源于建立的研究线，将调度理论与与图形着色相关的方法结合在一起。最近，群集图及其扩展（例如块图）受到了额外的关注。我们通过提供近似算法来补充其他研究人员为块图提供的硬度结果。特别是，我们为$ p | g = block \ graph | c_ {max} $提供了$ 2 $ - APPROXIMATION算法，而当作业为单位时间的情况下。对于统一机器，我们分析了两种情况。第一个是当块的数量界限时，即$ q | g = k-block \ graph | c_ {max} $。对于这种情况，我们提供了一个PTA，并改善了D. Page和R. Solis-Oba提出的结果。改进是两个方面：我们允许更丰富的图形结构，并且允许机器速度的数量成为输入的一部分。由于$ q | g = 2-clique \ graph | c_ {max} $的强np- hard度，结果建立了$ q | g = k-block \ grack \ graph | c_ c_ {max} $的近似状态。 PTA可能具有独立的兴趣，因为该问题与目标总和问题的数值k维匹配密切相关。我们分析的第二种情况是块数量是任意的，但是切割媒体的数量是有限的，作业是单位时间的。在这种情况下，我们提出了一种精确的算法。此外，我们还提出了具有有界树宽和有限数量的无关机器的图形的FPTA。
The problem of scheduling jobs on parallel machines (identical, uniform, or unrelated), under incompatibility relation modeled as a block graph, under the makespan optimality criterion, is considered in this paper. No two jobs that are in the relation (equivalently in the same block) may be scheduled on the same machine in this model. The presented model stems from a well-established line of research combining scheduling theory with methods relevant to graph coloring. Recently, cluster graphs and their extensions like block graphs were given additional attention. We complement hardness results provided by other researchers for block graphs by providing approximation algorithms. In particular, we provide a $2$-approximation algorithm for $P|G = block\ graph|C_{max}$ and a PTAS for the case when the jobs are unit time in addition. In the case of uniform machines, we analyze two cases. The first one is when the number of blocks is bounded, i.e. $Q|G = k-block\ graph|C_{max}$. For this case, we provide a PTAS, improving upon results presented by D. Page and R. Solis-Oba. The improvement is two-fold: we allow richer graph structure, and we allow the number of machine speeds to be part of the input. Due to strong NP-hardness of $Q|G = 2-clique\ graph|C_{max}$, the result establishes the approximation status of $Q|G = k-block\ graph|C_{max}$. The PTAS might be of independent interest because the problem is tightly related to the NUMERICAL k-DIMENSIONAL MATCHING WITH TARGET SUMS problem. The second case that we analyze is when the number of blocks is arbitrary, but the number of cut-vertices is bounded and jobs are of unit time. In this case, we present an exact algorithm. In addition, we present an FPTAS for graphs with bounded treewidth and a bounded number of unrelated machines.
