An Adversarial Model for Scheduling with Testing
An Adversarial Model for Scheduling with Testing
复制标题
DOI：
10.1007/s00453-020-00742-2
复制
发表时间：
2017-09
期刊：
影响因子：
1.1
通讯作者：
C. Durr;T. Erlebach;Nicole Megow;Julie Meißner
中科院分区：
文献类型：
--
作者：
C. Durr;T. Erlebach;Nicole Megow;Julie Meißner
针对具有可探测性不确定性的调度问题，提出了一种新的对抗性模型。在该模型中，可以通过测试作业来潜在地减少作业的处理时间(优先级和未知量)。测试作业需要一个单位的时间，并且可以将其处理时间从给定的上限(如果未测试则为执行作业所需的时间)减少到0到之间的任意值。该设置例如由其中代码优化器可以在执行作业之前在作业上运行的应用程序来激励。我们考虑在一台机器上最小化完成时间总和的目标。所有工作从一开始就是可用的，但测试导致的处理时间减少是未知的，这使得这是一个可以进行竞争性分析的在线问题。需要平衡花在测试上的时间和花在作业执行上的时间，这增加了问题的新鲜感。我们给出了确定性算法和随机化算法的竞争比的第一个且几乎紧凑的上下界。我们还证明了最小化完工时间是一个相当容易的问题，对于这个问题，我们给出了最优的确定性和随机化在线算法。
We introduce a novel adversarial model for scheduling with explorable uncertainty. In this model, the processing time of a job can potentially be reduced (by ana prioriunknown amount) by testing the job. Testing a jobjtakes one unit of time and may reduce its processing time from the given upper limit(which is the time taken to execute the job if it is not tested) to any value between 0 and. This setting is motivated e.g., by applications where a code optimizer can be run on a job before executing it. We consider the objective of minimizing the sum of completion times on a single machine. All jobs are available from the start, but the reduction in their processing times as a result of testing is unknown, making this an online problem that is amenable to competitive analysis. The need to balance the time spent on tests and the time spent on job executions adds a novel flavor to the problem. We give the first and nearly tight lower and upper bounds on the competitive ratio for deterministic and randomized algorithms. We also show that minimizing the makespan is a considerably easier problem for which we give optimal deterministic and randomized online algorithms.