relation in form of an intree (outdegrees are at most 1). outtree: Given general precedence relation in form of an outtree (indegrees are at most 1). opposing forest: Given general precedence relation in form of a collection of intrees and outtrees. sp-graph: Given precedence relation in form of a series parallel graph. bounded height: Given precedence relation where the longest directed path is bounded by a constant. level order: Given precedence relation where each vertex of a given level ℓ (i.e. the length of the longest directed path starting from this vertex is ℓ) is a predecessor of all the vertices of level . interval order: Given precedence relation for which one can associate to each vertex an interval in the real line, and there is a precedence between and if and only if the half-open intervals and are such that is smaller than or equal to . quasi-interval order: Quasi-interval orders are a superclass of interval orders defined in Moukrim: "Optimal scheduling on parallel machines for a new order class", Operations Research Letters, 24(1):91–95, 1999. over-interval order: Over-interval orders are a superclass of quasi-interval orders defined in Chardon and Moukrim: The Coffman–Graham algorithm optimally solves UET task systems with overinterval orders, SIAM Journal on Discrete Mathematics, 19(1):109–121, 2005. Am-order: Am orders are a superclass of over-interval orders defined in Moukrim and Quilliot: "A relation between multiprocessor scheduling and linear programming." Order, 14(3):269–278, 1997. DC-graph: A divide-and-conquer graph is a subclass of series-parallel graphs defined in Kubiak et al.: Optimality of HLF for scheduling divide-and-conquer UET task graphs on identical parallel processors. Discrete Optimization, 6:79–91, 2009. 2-dim partial order: A 2-dimensional partial order is a k-dimensional partial order for k = 2. k-dim partial order: A poset is a k-dimensional partial order iff it can be embedded into the k-dimensional Euclidean space in such a way that each node is represented by a k-dimensional point and there is a precedence between two nodes i and j iff for any dimension the coordinate of i is smaller than or equal to the one of j. In the presence of a precedence relation one might in addition assume time lags. Let denote the start time of a job and its completion time. Then the precedence relation implies the constraint . If no time lag is specified then it is assumed to be zero. Time lags can be positive or negative numbers. ℓ: