Polynomial time algorithms for the message routing problem

The problem of determining whether a set of messages can be routed in an unidirectional ring was studied by Leung, et al. They presented complexity results under various restrictions of four parameters : origin node, destination node, release time and deadline. For nonpreemptive transmission they showed that the problem is solvable in polynomial time when any of the four parameter is allowed to be arbitrary, and that it becomes NP-complete when any two of them are fixed. In this paper, we continue to study the problem to minimize the mean flow time of messages with respect to the nonpreemptive transmission. We show that the problem is solvable in polynomial time when destination node or deadline is allowed to be arbitrary.