A QPTAS for the General Scheduling Problem with Identical Release Dates
A QPTAS for the General Scheduling Problem with Identical Release Dates
复制标题
具有相同发布日期的一般调度问题的 QPTAS
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Andreas Wiese
中科院分区：
文献类型：
--
作者：
A. Antoniadis;R. Hoeksma;Julie Meißner;José Verschae;Andreas Wiese
一般调度问题（GSP）概括了具有加权流动时间和加权迟到等成本目标之和的调度问题。给定一组具有加工时间、发布日期和作业相关成本函数的工件，我们寻求在单机上找到一个最小成本的抢先调度。这个问题的最著名的算法，也为加权流时间/迟到是一个O（loglog P）-近似（其中P表示的范围内的作业处理时间），而最好的下限显示只有强NP-硬度。当发布日期相同时，也有一个间隙：问题仍然是强NP-难的，最著名的近似算法的比率为e+ ε（在准多项式时间内运行）。如果输入中的数字是准多项式有界的，我们通过给出QPTAS来减少后一个差距，排除了APX硬度证明的存在，除非NPsubseteq DTIME（2^polylog（n））。我们的技术是基于QPTAS已知的UFP覆盖问题，一个特殊的情况下，GSP，我们必须选择一个子集的区间（作业）的真实的线与相关的高度和成本。如果选择了区间，其高度将有助于满足区间内任何点的给定需求。我们减少我们的问题的UFP覆盖的推广，并使用一个复杂的分治程序与相互依赖的非对称子问题。
我们还提出了一个伪多项式时间近似计划的两个变种的UFP覆盖。对于可接受的间隔的情况下，我们给出了一个新的动态规划方法的基础上，这可能是有用的其他问题的这种类型的算法。第二个是资源增加设置，允许我们稍微放大每个间隔。
The General Scheduling Problem (GSP) generalizes scheduling problems with sum of cost objectives such as weighted flow time and weighted tardiness. Given a set of jobs with processing times, release dates, and job dependent cost functions, we seek to find a minimum cost preemptive schedule on a single machine. The best known algorithm for this problem and also for weighted flow time/tardiness is an O(loglog P)-approximation (where P denotes the range of the job processing times), while the best lower bound shows only strong NP-hardness. When release dates are identical there is also a gap: the problem remains strongly NP-hard and the best known approximation algorithm has a ratio of e+epsilon (running in quasi-polynomial time). We reduce the latter gap by giving a QPTAS if the numbers in the input are quasi-polynomially bounded, ruling out the existence of an APX-hardness proof unless NPsubseteq DTIME(2^polylog(n)). Our techniques are based on the QPTAS known for the UFP-Cover problem, a particular case of GSP where we must pick a subset of intervals (jobs) on the real line with associated heights and costs. If an interval is selected, its height will help cover a given demand on any point contained within the interval. We reduce our problem to a generalization of UFP-Cover and use a sophisticated divide-and-conquer procedure with interdependent non-symmetric subproblems.
We also present a pseudo-polynomial time approximation scheme for two variants of UFP-Cover. For the case of agreeable intervals we give an algorithm based on a new dynamic programming approach which might be useful for other problems of this type. The second one is a resource augmentation setting where we are allowed to slightly enlarge each interval.