Chains and Trees: 'Strong'-'Weak' Order in Job Scheduling

Moshe Dror

Research output: Contribution to journalArticlepeer-review

1 Scopus citations


We present a summary of recent NP-hardness and polynomial time solvability results for the distinction between 'strong' and 'weak' precedence for chains and trees in scheduling. We distinguish between chains and proper trees which are not chains, and demonstrate that the strong-weak precedence distinction for chains is not inclusive with regards to NP-hardness, and conjecture that the same holds for strong-weak tree precedence. The objective is to show that different 'interpretations' for chain and tree order relations in scheduling might have far reaching computational implications.

Original languageEnglish (US)
Pages (from-to)211-228
Number of pages18
Issue number3
StatePublished - 1997


  • Complexity
  • Partial order
  • Scheduling

ASJC Scopus subject areas

  • Algebra and Number Theory
  • Geometry and Topology
  • Computational Theory and Mathematics


Dive into the research topics of 'Chains and Trees: 'Strong'-'Weak' Order in Job Scheduling'. Together they form a unique fingerprint.

Cite this