Tree precedence in scheduling: The strong-weak distinction

In this paper we formally introduce the distinction between strong and weak precedence relation in scheduling for the case of trees. We demonstrate that this distinction in precedence relation for trees (as demonstrated in earlier work for chains) is a proper one in the sense that some problems are solvable in polynomial time if weak tree relation is assumed and are NP-hard in the case of strong tree relations. For some other problems, both weak tree and strong tree relations are NP-hard, and for yet other problems both weak and strong tree relations are polynomially solvable. Since the distinction between strong and weak tree precedence was not clearly recognized in the past, this work establishes the existence of new problem categories in scheduling.