论文标题
在线安排时间关键任务，以最大程度地减少校准数量
Online Scheduling of Time-Critical Tasks to Minimize the Number of Calibrations
论文作者
论文摘要
我们研究在线调度问题，在处理任何工作之前，需要对机器进行校准。要校准机器，将需要$λ$的时间步骤作为激活时间，然后机器将保持$ t $时间步长的校准状态。该作业只能由处于校准状态的机器处理。鉴于一组在线到达的工作，每个作业的特征是发布时间，处理时间和截止日期。我们假设有无限数量的用于使用的机器。目的是最大程度地减少校准总数，同时安排所有工作。 对于所有作业都有单元处理时间的情况，我们提出了$ \ Mathcal {o}（λ）$ - 竞争性算法，该算法在渐近上是最佳的。当$λ= 0 $时，问题会降低以最小化，在此，我们的算法达到了$ 3E+7（\ 15.16）$的竞争比率，从而改善了此类问题的结果。
We study the online scheduling problem where the machines need to be calibrated before processing any jobs. To calibrate a machine, it will take $λ$ time steps as the activation time, and then the machine will remain calibrated status for $T$ time steps. The job can only be processed by the machine that is in calibrated status. Given a set of jobs arriving online, each of the jobs is characterized by a release time, a processing time, and a deadline. We assume that there is an infinite number of machines for usage. The objective is to minimize the total number of calibrations while feasibly scheduling all jobs. For the case that all jobs have unit processing times, we propose an $\mathcal{O}(λ)$-competitive algorithm, which is asymptotically optimal. When $λ=0$, the problem is degraded to rent minimization, where our algorithm achieves a competitive ratio of $3e+7(\approx 15.16)$ which improves upon the previous results for such problems.
