We consider the problem of sequencing N jobs on a single machine when each job has a known processing time and a known deferral rate and a general precedence relationship exists among the jobs. The problem is to find the minimum cost sequence which is consistent with the precedence relationship. This problem has been solved in certain special cases obtained by restricting the form of the precedence graph. The results of this paper constitute a proper generalization of all previously solved special cases. These results are used to derive an alternate efficient approach to the case in which the precedence graph is a rooted tree, as well as an algorithm for attacking the general problem having an arbitrary acyclic precedence graph. The general algorithm has an $O(n^3)$ time bound and though it only gives partial solutions in some instances, the class of problems that it completely solves is a proper superset of the corresponding classes for all previous polynomial time algorithms.

This paper considers a special case of the standard transportation problem obtained by restricting the number of origins to two. Necessary and sufficient conditions are established which lead to a direct construction of the optimal solution. Using an extension of a recent selection algorithm, an algorithm is developed to solve this special case of the transportation problem in $O(n)$ time in the worst case. The algorithm applies to both capacitated as well as uncapacitated problems.