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.
- Partial order
ASJC Scopus subject areas
- Algebra and Number Theory
- Geometry and Topology
- Computational Theory and Mathematics