Whether it is possible to have an optimal online algorithm for unidirectional ring, out-tree, in-tree, bidirectional tree, and bidirectional ring networks is discussed. The problem is considered under various restrictions of four parameters-origin node, destination node, release time and deadline. For unidirectional ring, it is shown that no such algorithm can exist unless one of the four parameters is fixed. For out-tree, it is shown that no such algorithm can exist unless one of three parameters-origin node, destination node and release time-is fixed. For in-tree, it is shown that no such algorithm can exist unless one of three parameters-origin node, destination node and deadline-is fixed. For bidirectional tree, it is shown that no such algorithm can exist unless the origin node or the destination node is fixed. For bidirectional ring, it is shown that no such algorithm can exist unless the origin node and either the destination node or the release time are fixed.>

In a new model of task systems studied by J.W.S. Liu et al. (1987) each task is logically decomposed into two subtasks, mandatory and optional. The authors discuss preemptively scheduling this kind of task system on p>or=1 identical processors so as to minimize the mean flow time. Given a task system and an error threshold K, the goal is to find a preemptive schedule such that each task is executed in the interval of its release time and deadline, the average error is no more than K, and the mean flow time of the schedule is minimized. Such a schedule is called an optimal schedule. It is shown that the problem of finding an optimal schedule is NP-hard for each p>or=1, even if all tasks have the same ready time and deadline. For a single processor, a pseudo-polynomial time algorithm and polynomial time algorithms for various special cases of the problem are given.>