Scheduling under Uncertainty: A Query-based Approach
Scheduling under Uncertainty: A Query-based Approach
复制标题
不确定性下的调度：基于查询的方法
DOI：
--
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Pierre Sens
中科院分区：
文献类型：
--
作者：
L. Arantes;E. Bampis;A. Kononov;Manthos Letsios;Giorgio Lucarelli;Pierre Sens
我们考虑一台机器、一组单位时间作业和一组单位时间错误。我们假设每个误差发生的时隙是事先未知的，但对于每个误差，存在一个误差将发生的不确定区域。为了发现错误是否发生在特定的时隙中，有必要向它发出查询。在这项工作中，我们研究了两个问题：(i)错误查询调度问题，其目的是用最少的查询数来揭示足够的无错误槽；（ii）字典顺序错误查询调度问题，我们寻求用最少的查询数最早的无错误槽。我们考虑了上述问题的离线和在线版本。在前者中，我们预先知道了整个实例及其特征，并给出了一个多项式时间算法来解决错误查询调度问题。在后一种情况下，对手有能力以在线方式决定每个错误出现的时间。然后，我们提出了下界和竞争比渐近匹配下界的算法。
We consider a single machine, a set of unit-time jobs, and a set of unit-time errors. We assume that the time-slot at which each error will occur is not known in advance but, for every error, there exists an uncertainty area during which the error will take place. In order to find if the error occurs in a specific time-slot, it is necessary to issue a query to it. In this work, we study two problems: (i) the error-query scheduling problem, whose aim is to reveal enough error-free slots with the minimum number of queries, and (ii) the lexicographic error-query scheduling problem where we seek the earliest error-free slots with the minimum number of queries. We consider both the off-line and the on-line versions of the above problems. In the former, the whole instance and its characteristics are known in advance and we give a polynomial-time algorithm for the error-query scheduling problem. In the latter, the adversary has the power to decide, in an on-line way, the time-slot of appearance for each error. We propose then both lower bounds and algorithms whose competitive ratios asymptotically match these lower bounds.
查询的鲁棒背包问题
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
算法百科全书
DOI：
10.1007/978-0-387-30162-4_347
发表时间：
2008
期刊：
--
影响因子：
--
作者：
Lyngsø R
通讯作者：
Lyngsø R