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 th at this distinction in precedence relation for trees (as demonstrated in ea rlier 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-har d 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 distin ction between strong and weak tree precedence was not clearly recognized in the past, this work establishes the existence of new problem categories in scheduling. (C) 1999 Elsevier Science B.V. All rights reserved.