An optimal online algorithm for metrical task systems
An optimal online algorithm for metrical task systems
复制标题
DOI：
10.1145/28395.28435
复制
发表时间：
1987-01
期刊：
影响因子：
--
通讯作者：
A. Borodin;N. Linial;M. Saks
中科院分区：
文献类型：
--
作者：
A. Borodin;N. Linial;M. Saks
在实践中，几乎所有的动态系统都需要在线决策，而不完全了解它们对系统的未来影响。我们介绍了一个一般模型的任务序列的处理，并开发了一个通用的在线决策算法。我们表明，对于一类重要的特殊情况下，该算法是最优的所有在线算法。具体地说，用于处理任务序列的任务系统（S，d）由状态集合S和成本矩阵d组成，其中d（i，j）是从状态i改变到状态j的成本（我们假设d满足三角不等式并且所有对角元素都是O）。处理给定任务的成本取决于系统的状态。任务序列T1，T2. Tk的调度是状态序列s1，s2. sk，其中si是处理Ti的状态;调度的成本是所有任务处理成本和所产生的状态转换成本的总和。在线调度算法是仅知道T1 T2. Ti就选择si的算法。如果在任何输入任务序列上，其成本在w乘以最优离线调度成本的附加常数内，则这样的算法在浪费因子w内操作。在线浪费因子w（S，d）是针对（S，d）的任何在线调度算法的弱浪费因子。我们证明了w（S，d）= 2| S|- 对于每个任务系统，其中d是对称的，并且w（S，d）=&Ogr;（|S| 2）对于每个任务系统。
In practice, almost all dynamic systems require decisions to be made online, without full knowledge of their future impact on the system. We introduce a general model for the processing of sequences of tasks and develop a general online decision algorithm. We show that, for an important class of special cases, this algorithm is optimal among all online algorithms. Specifically, a task system (S, d) for processing sequences of tasks consists of a set S of states and a cost matrix d where d(i, j) is the cost of changing from state i to state j (we assume that d satisfies the triangle inequality and all diagonal entries are O.) The cost of processing a given task depends on the state of the system. A schedule for a sequence T1, T2 … Tk of tasks is a sequence s1, s2 … sk of states where si is the state in which Ti is processed; the cost of a schedule is the sum of all task processing costs and state transition costs incurred. An online scheduling algorithm is one that chooses si only knowing T1 T2 … Ti. Such an algorithm operates within waste factor w if, on any input task sequence, its costs is within an additive constant of w times the optimal offline schedule cost. The online waste factor w(S, d) is the infirm waste factor of any online scheduling algorithm for (S, d). We show that w(S, d) = 2|S| - 1 for every task system in which d symmetric, and w(S, d) = &Ogr;(|S|2) for every task system.