论文标题
耦合任务计划的近似算法最小化完成时间的总和
Approximation algorithms for coupled task scheduling minimizing the sum of completion times
论文作者
论文摘要
在本文中，我们将单台计算机上的耦合任务调度问题与精确的延迟时间考虑，目的是最大程度地减少工作的总完成时间。我们为该问题的几种变体提供了恒定的因子近似算法，这些算法已知是NP-硬化的，同时也证明了以前不明复杂性的两个变体的NP硬度。使用这些结果，以及文献中的MakePAN物镜的恒定因子近似值，我们还在耦合任务设置中引入了关于双向目标近似的第一个结果。
In this paper we consider the coupled task scheduling problem with exact delay times on a single machine with the objective of minimizing the total completion time of the jobs. We provide constant-factor approximation algorithms for several variants of this problem that are known to be NP-hard, while also proving NP-hardness for two variants whose complexity was unknown before. Using these results, together with constant-factor approximations for the makespan objective from the literature, we also introduce the first results on bi-objective approximation in the coupled task setting.
