Minimizing worst-case and average-case makespan over scenarios
Minimizing worst-case and average-case makespan over scenarios
复制标题
DOI：
10.1007/s10951-016-0484-y
复制
发表时间：
2016-06
影响因子：
2
通讯作者：
E. Feuerstein;A. Marchetti-Spaccamela;Frans Schalekamp;René Sitters;S. Ster;L. Stougie;A. V. Zuylen
中科院分区：
文献类型：
--
作者：
E. Feuerstein;A. Marchetti-Spaccamela;Frans Schalekamp;René Sitters;S. Ster;L. Stougie;A. V. Zuylen
我们认为调度问题的目标是找到一个单一的分配的工作，以及在所有的情况下，在一个明确给定的集的机器。每个场景都是必须在该场景中执行的作业的子集。我们考虑的两个目标是最小化所有场景的最大完工时间和最小化所有场景的完工时间之和。对于这两个版本，我们给出了几种逼近算法及其逼近性的下界。我们还考虑了一些（更简单的）特殊情况。一般情况下的组合优化问题，特别是在场景下的调度问题，到目前为止只看到有限的研究关注。通过本文，我们在这个有趣的研究方向上迈出了一步。
We consider scheduling problems over scenarios where the goal is to find a single assignment of the jobs to the machines which performs well over all scenarios in an explicitly given set. Each scenario is a subset of jobs that must be executed in that scenario. The two objectives that we consider are minimizing the maximum makespan over all scenarios and minimizing the sum of the makespans of all scenarios. For both versions, we give several approximation algorithms and lower bounds on their approximability. We also consider some (easier) special cases. Combinatorial optimization problems under scenarios in general, and scheduling problems under scenarios in particular, have seen only limited research attention so far. With this paper, we make a step in this interesting research direction.