A survey on how the structure of precedence constraints may change the complexity class of scheduling problems <s> 7 <s> Given a partially ordered setP=(X, ≤), a collection of linear extensions {L1,L2,...,Lr} is arealizer if, for every incomparable pair of elementsx andy, we havex<y in someLi (andy<x in someLj). For a positive integerk, we call a multiset {L1,L2,...,Lt} ak-fold realizer if for every incomparable pairx andy we havex<y in at leastk of theLi's. Lett(k) be the size of a smallestk-fold realizer ofP; we define thefractional dimension ofP, denoted fdim(P), to be the limit oft(k)/k ask→∞. We prove various results about the fractional dimension of a poset. <s> BIB001 </s> A survey on how the structure of precedence constraints may change the complexity class of scheduling problems <s> 7 <s> The general non preemptive multiprocessor scheduling problem (NPMS) is NP-Complete, while in many specific cases, the same problem is Time-polynomial. A first connection between PMS and linear programming was established by Yannanakis, Sauer and Stone, who associated to any PMS instance some specific linear program. The main result inside this paper consists in a characterization of the partially ordered structures which allow the optimal values of any associated PMS instance to be equal to the optimal values of the corresponding linear programs. <s> BIB002
Definition 5 (Antichain) Given a partial order set P = (X, P ), an antichain is a subset S of X such that any two elements of S are incomparable. Definition 6 (Width) Given a poset P = (X, P ), the width of a poset is the size of a maximum antichain. By extension, for a given directed acyclic graph G = (X, A) we define the width of the graph to be the width of the corresponding poset, denoted by w(G). The Am−order (first introduced in BIB002 ) contains the over-interval order for any integer m ≥ 2 and is defined in the following way: We call Am−order graph a directed acyclic graph for which the set of arcs corresponds to an Am−order. Definition 8 (Linear extension) Given a partial order P over a set X, a linear extension of P over X is a total order respecting P . Definition 9 (Dimension) The dimension of a poset P = (X, P ) is the mimimum number t of linear extensions 1 , . . . , t such that x P y ⇐⇒ ∀l ∈ 1..t, x l y. In other words, if x||y (x and y are incomparable in P ), then there are at least two linear extensions, one with x y and another one with An interesting point is that series-parallel graphs are strictly included in directed acyclic graphs of dimension 2. The fractional dimension of a poset is extending the notion of dimension (see BIB001 and k with y x. The fractional dimension is the limit {t(k)/k} as k tends to +∞. The diagram in Figure 10 provides a better overview of the existing inclusion between the different classes.