Scheduling with Testing on Multiple Identical Parallel Machines
Scheduling with Testing on Multiple Identical Parallel Machines
复制标题
在多个相同的并行机器上进行测试调度
DOI：
--
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Alexander Eckl
中科院分区：
文献类型：
--
作者：
S. Albers;Alexander Eckl
测试调度是一个最近的在线问题的框架内的可探索的不确定性的激励环境中，一些初步的行动可以影响任务的持续时间。作业具有未知的处理时间，可以通过运行测试来探索。或者，作业可以在给定上限的持续时间内执行。我们认为这个问题的设置内的多个相同的并行机和竞争力的确定性算法和下界的目标，最大限度地减少了时间表的完工时间。在非抢占式环境中，我们提出了SBS算法，当机器数量变大时，其竞争比接近3.1016 $。我们比较这个结果与一个简单的贪婪策略和一个接近2美元的下限。在测试次数相同的情况下，我们可以改进SBS算法，使其具有3 $-竞争力。对于抢先的情况下，我们提供了一个2 $竞争算法和一个紧的下界，接近相同的值。
Scheduling with testing is a recent online problem within the framework of explorable uncertainty motivated by environments where some preliminary action can influence the duration of a task. Jobs have an unknown processing time that can be explored by running a test. Alternatively, jobs can be executed for the duration of a given upper limit. We consider this problem within the setting of multiple identical parallel machines and present competitive deterministic algorithms and lower bounds for the objective of minimizing the makespan of the schedule. In the non-preemptive setting, we present the SBS algorithm whose competitive ratio approaches $3.1016$ if the number of machines becomes large. We compare this result with a simple greedy strategy and a lower bound which approaches $2$. In the case of uniform testing times, we can improve the SBS algorithm to be $3$-competitive. For the preemptive case we provide a $2$-competitive algorithm and a tight lower bound which approaches the same value.
影响因子：
1.1
作者：
C. Durr;T. Erlebach;Nicole Megow;Julie Meißner
通讯作者：
C. Durr;T. Erlebach;Nicole Megow;Julie Meißner
查询的鲁棒背包问题
DOI：
10.1016/j.cor.2014.09.010
发表时间：
2015
期刊：
Comput. Oper. Res.
影响因子：
--
作者：
Goerigk;Schöbel
通讯作者：
Schöbel
DOI：
10.1007/978-3-662-48350-3_73
发表时间：
2017-01
期刊：
--
影响因子：
--
作者：
Nicole Megow;Julie Meißner;M. Skutella
通讯作者：
Nicole Megow;Julie Meißner;M. Skutella