论文标题
与非均匀测试时间计划的调度不确定性
Explorable Uncertainty in Scheduling with Non-Uniform Testing Times
论文作者
论文摘要
在可探索的不确定性模型环境的框架中进行测试的调度问题，其中某些初步动作会影响任务的持续时间。在模型中，每个作业都有一个未知的处理时间，可以通过运行测试来揭示。或者，在给定上限的持续时间内，可能未测试作业。最近，Dürr等。 [5]研究了所有测试时间均为单位尺寸的设置，并给出了最小化完成时间之和的目标和上限和上限。在本文中，我们将问题扩展到非均匀的测试时间，并介绍第一个竞争算法。例如，通过在线用户调查进行市场预测或查询分布式计算中的集中数据库的动机。引入一般测试时间为问题带来了新的口味，并且需要使用新技术进行更新的方法。我们提出了持续的竞争比率，以最大程度地减少确定性案例的完成时间之和的目标，无论是在非抢先和先前的环境中。对于先发制人的设置，我们还提供了第一个下限。我们还提出了一种随机算法，具有提高的竞争比。此外，在确定性和随机设置中，我们为最大程度地减少Makepan的目的而给出了紧密的竞争比率。
The problem of scheduling with testing in the framework of explorable uncertainty models environments where some preliminary action can influence the duration of a task. In the model, each job has an unknown processing time that can be revealed by running a test. Alternatively, jobs may be run untested for the duration of a given upper limit. Recently, Dürr et al. [5] have studied the setting where all testing times are of unit size and have given lower and upper bounds for the objectives of minimizing the sum of completion times and the makespan on a single machine. In this paper, we extend the problem to non-uniform testing times and present the first competitive algorithms. The general setting is motivated for example by online user surveys for market prediction or querying centralized databases in distributed computing. Introducing general testing times gives the problem a new flavor and requires updated methods with new techniques in the analysis. We present constant competitive ratios for the objective of minimizing the sum of completion times in the deterministic case, both in the non-preemptive and preemptive setting. For the preemptive setting, we additionally give a first lower bound. We also present a randomized algorithm with improved competitive ratio. Furthermore, we give tight competitive ratios for the objective of minimizing the makespan, both in the deterministic and the randomized setting.
