AN OPTIMAL ONLINE ALGORITHM FOR METRICAL TASK SYSTEM
AN OPTIMAL ONLINE ALGORITHM FOR METRICAL TASK SYSTEM
复制标题
DOI：
10.1145/146585.146588
复制
发表时间：
1992-10-01
影响因子：
2.5
通讯作者：
SAKS, ME
中科院分区：
文献类型：
--
作者：
BORODIN, A;LINIAL, N;SAKS, ME
在实践中，几乎所有动态系统都需要在线做出决策，而没有充分了解其未来对系统的影响。引入了处理任务序列的一般模型，并开发了一般的在线决策算法。结果表明，对于一系列特殊情况，该算法在所有在线算法中都是最佳的。特别是，用于处理任务序列的任务系统（S，d）由一组状态和成本矩阵组成d其中d（i，j）是从状态i到状态j变化的成本（我们假设d满足三角形不平等，所有对角线条目为0）。处理给定任务的成本取决于系统状态。任务的序列T1，T2，...，T（K）的时间表是SI是SI是处理T1的状态的序列S1，S2，...，S（K）；时间表的成本是所有任务处理成本和州过渡成本的总和。在线安排算法是选择S（i）仅知道T1T2 ... t（i）的算法。如果在任何输入任务序列上，这种算法是W竞争力的，其成本属于最佳离线时间表成本的w倍。竞争比W（s，d）是（s，d）具有W竞争性的在线调度算法的a型w。结果表明，对于对称D的每个任务系统，W（s，d）= 2 s -1的绝对值，而W（s，d）= o（S2的绝对值S2）对于每个任务系统。最后，引入了随机的在线调度算法。结果表明，对于统一任务系统（其中d（i，j）= 1对于所有i，j），预期的竞争比WBAR（s，d）O（s的log绝对值）。
In practice, almost all dynamic systems require decisions to be made on-line, without full knowledge of their future impact on the system. A general model for the processing of sequences of tasks is introduced, and a general on-line decision algorithm is developed. It is shown that, for an important class of special cases, this algorithm is optimal among all on-line 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 0). The cost of processing a given task depends on the state of the system. A schedule for a sequence T1, T2, ..., T(k) of tasks is a sequence s1, s2, ..., s(k) of states where si is the state in which T1 is processed; the cost of a schedule is the sum of all task processing costs and state transition costs incurred.An on-line scheduling algorithm is one that chooses s(i) only knowing T1T2 ... T(i). Such an algorithm is w-competitive if, on any input task sequence, its cost is within an additive constant of w times the optimal offline schedule cost. The competitive ratio w(S,d) is the infimum w for which there is a w-competitive on-line scheduling algorithm for (S, d). It is shown that w(S, d) = 2 Absolute value of S - 1 for every task system in which d is symmetric, and w(S, d) = O(Absolute value of S2) for every task system. Finally, randomized on-line scheduling algorithms are introduced. It is shown that for the uniform task system (in which d(i, j) = 1 for all i, j), the expected competitive ratio wBAR(S, d) O(log Absolute value of S).