Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1016/j.dam.2010.06.015 | Discrete Applied Mathematics |
Keywords | Field | DocType |
strong precedence,series-parallel order,weak precedence,job precedence relation,computational complexity implication,consistent definition,series-parallel posets,scheduling,strong and weak precedence,new computational complexity result,strong precedence constraint,posets,past complexity result,scheduling problem,series parallel,modular decomposition,computational complexity,partially ordered set | Discrete mathematics,Modular decomposition,Combinatorics,Scheduling (computing),Series and parallel circuits,Partially ordered set,Mathematics,Computational complexity theory | Journal |
Volume | Issue | ISSN |
158 | 16 | Discrete Applied Mathematics |
Citations | PageRank | References |
1 | 0.36 | 12 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Moshe Dror | 1 | 574 | 64.77 |
| George Steiner | 2 | 425 | 27.83 |