‘Strong’-‘weak’ precedence in scheduling: Extensions to series-parallel orders

We examine computational complexity implications for scheduling problems with job precedence relations with respect to strong precedence versus weak precedence. We propose a consistent definition of strong precedence for chains, trees, and series-parallel orders. Using modular decomposition for partially ordered sets (posets), we restate and extend past complexity results for chains and trees as summarized in Dror (1997) 5]. Moreover, for series-parallel posets we establish new computational complexity results for strong precedence constraints for single- and multi-machine problems.