View article

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 T¹, T²,…, T^k of tasks is a sequence s₁, s₂,…,s_k of states where s_i is the state in which Tⁱ is processed; the cost of a schedule is the sum of all task processing costs and the state transition costs …