Preemptive scheduling on a small number of hierarchical machines
Preemptive scheduling on a small number of hierarchical machines
复制标题
DOI：
10.1016/j.ic.2007.11.004
复制
发表时间：
2008-05
期刊：
影响因子：
--
通讯作者：
G. Dósa;L. Epstein
中科院分区：
文献类型：
--
作者：
G. Dósa;L. Epstein
在分层模型中，我们考虑在相同机器和统一相关机器上的抢占式离线和在线调度，目标是最小化完工时间。在该模型中，每个作业可以分配到机器的一个子集，该子集是机器集的前缀。我们设计了两个均匀相关机器的最优离线和在线算法，无论是更高层次的机器更快还是更慢，以及三个相同机器的情况。具体来说，对于这三种情况，我们分别给出了计算最优调度的最大跨度的简单公式，给出了计算最优调度的线性时间离线算法，并设计了一个最优竞争比的在线算法。
We consider preemptive offline and online scheduling on identical machines and uniformly related machines in the hierarchical model, with the goal of minimizing the makespan. In this model, each job can be assigned to a subset of the machines which is a prefix of the machine set. We design optimal offline and online algorithms for two uniformly related machines, both when the machine of higher hierarchy is faster and when it is slower, as well as for the case of three identical machines. Specifically, for each one of the three variants, we give a simple formula to compute the makespan of an optimal schedule, provide a linear time offline algorithm which computes an optimal schedule and design an online algorithm of the best possible competitive ratio.