'Strong''weak' precedence in scheduling: Extensions to seriesparallel orders

Moshe Dror, George Steiner

Research output: Contribution to journalArticlepeer-review

1 Scopus citations


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 seriesparallel 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 seriesparallel posets we establish new computational complexity results for strong precedence constraints for single- and multi-machine problems.

Original languageEnglish (US)
Pages (from-to)1767-1776
Number of pages10
JournalDiscrete Applied Mathematics
Issue number16
StatePublished - Aug 28 2010
Externally publishedYes


  • Posets
  • Scheduling
  • Strong and weak precedence

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics


Dive into the research topics of ''Strong''weak' precedence in scheduling: Extensions to seriesparallel orders'. Together they form a unique fingerprint.

Cite this