Optimal algorithms for scheduling under time-of-use tariffs
Optimal algorithms for scheduling under time-of-use tariffs
复制标题
DOI：
10.1007/s10479-021-04059-3
复制
发表时间：
2018-11
影响因子：
4.8
通讯作者：
Lin Chen;Nicole Megow;R. Rischke;L. Stougie;José Verschae
中科院分区：
文献类型：
--
作者：
Lin Chen;Nicole Megow;R. Rischke;L. Stougie;José Verschae
我们考虑将经典调度问题自然推广到这样一种设置，其中使用时间单位来处理作业会导致一些与时间相关的成本，即使用时间费率，除了标准调度成本之外还必须支付该成本。我们关注抢占式单机调度和两个经典的调度成本函数，即（加权）完成时间和最大完成时间之和，即完工时间。虽然这些问题在经典调度设置中很容易解决，但当必须考虑使用分时费率时，它们要复杂得多。我们贡献最佳多项式时间算法和最佳近似算法。对于最小化单台机器上总（加权）完成时间的问题，我们提出了一种多项式时间算法，该算法为任何给定的作业序列计算最佳调度，即根据给定序列用于抢占式调度作业的最佳时隙集。该结果基于动态规划，使用对最优解的结构和潜在函数参数的精细分析。通过该算法，我们可以在多项式时间内最优地解决未加权问题。对于更普遍的问题，其中作业可能具有单独的权重，我们开发了一种基于双调度方法的多项式时间近似方案（PTAS），该方法用于在不同速度的机器上进行调度。由于加权问题是强 NP 难问题，因此我们的 PTAS 是我们所希望的最佳近似值。对于抢占式调度以最小化完工时间，我们证明存在一种相对简单的具有多项式运行时间的最优算法。即使在具有不相关机器的某个广义模型中也是如此。
We consider a natural generalization of classical scheduling problems to a setting in which using a time unit for processing a job causes some time-dependent cost, the time-of-use tariff, which must be paid in addition to the standard scheduling cost. We focus on preemptive single-machine scheduling and two classical scheduling cost functions, the sum of (weighted) completion times and the maximum completion time, that is, the makespan. While these problems are easy to solve in the classical scheduling setting, they are considerably more complex when time-of-use tariffs must be considered. We contribute optimal polynomial-time algorithms and best possible approximation algorithms. For the problem of minimizing the total (weighted) completion time on a single machine, we present a polynomial-time algorithm that computes for any given sequence of jobs an optimal schedule, i.e., the optimal set of time slots to be used for preemptively scheduling jobs according to the given sequence. This result is based on dynamic programming using a subtle analysis of the structure of optimal solutions and a potential function argument. With this algorithm, we solve the unweighted problem optimally in polynomial time. For the more general problem, in which jobs may have individual weights, we develop a polynomial-time approximation scheme (PTAS) based on a dual scheduling approach introduced for scheduling on a machine of varying speed. As the weighted problem is strongly NP-hard, our PTAS is the best possible approximation we can hope for. For preemptive scheduling to minimize the makespan, we show that there is a comparably simple optimal algorithm with polynomial running time. This is true even in a certain generalized model with unrelated machines.