■

Chains and Trees: ‘Strong’–‘Weak’ Order in Job
Scheduling
by MOSHE DROR

A partial order will be denoted by P D .J;P /,where J is the finite ground set of elements and P (or just  if no confusion is possible) is the (precedence) order relation, i.e. an irreflexive and transitive relation whose pairs .a; b/ 2P are written as a P b.a;b 2 J/ with the interpretation in scheduling that a has to be completed before b can begin. Two elements a; b 2 J are comparable in P (denoted by a  b)if a  b or b  a. Otherwise they are said to be incomparable (denoted by akPb). A set of pairwise comparable elements is called a chain, and a set of incomparable elements is called an antichain.The height h.P/ of P is the largest size of a chain of P minus 1. The width w.P/ of P is the largest size of an antichain of P (the notation here is adopted from Mohring, 1989). Given j 2 J ,Pred.j / VD fb 2 J jb P jg denotes the set of all successors of j, while Suc.k/ VD fa 2 J jk P ag denotes the set of all predecessors of k with respect to P D .J;P /.If u  v and there is no w 2 J with u  w  v then v is an immediate successor (cover) of u (or u is an immediate predecessor of v).
ImSuc.u/ and ImPred.u/ denote the set of immediate successors and immediate predecessors of u. We restrict the discussion here in the context of scheduling to ImSuc.u/ and ImPred.u/ sets for each u 2 J to represent the partial order P.

Graphs (both directed and undirected) are denoted by G D .J;E/,where J is the set of vertices or points and E is the set of edges. If P D .J;/ is a partial order, then G.P/ D .J;E/ with E Df.u; v/ju  vg denotes the comparability graph of P. Two vertices are connected by an edge in G.P/ iff they are comparable in P. Every partial order associated with G corresponds to a transitive orientation of the vertex set of G and vice versa.

A dag is a directed acyclic graph. It is transitively closed if .u; v/; .v;w/ 2 E implies that .u;w/ 2 E,and transitively reduced if .u;w/ 2 E implies that there is no v 2 J with .u; v/ 2 E and .v;w/ 2 E. Edges .u;w/ violating this condition are called transitive or redundant. We will restrict our discussion to transitively
reduced representations of partial orders. A linear order is a partial order without incomparable elements. A linear extension of a partial order P D .J;P / is a linear order L D .J;L/ on the same ground set J that extends P. Linear extensions can be used to represent a partial order in the following sense. To every partial order P D .J;/,thereexist linear extensions Li D .J;Li /, i D 1;:::;k,of P whose intersection is P, a  b iff a Li b for i D 1;:::;k. The smallest number k of linear extensions in such representation is called the dimension of P and is denoted by dim.P/. P is called k-dimensional if dim.P/  k. For instance, the dimension of a partial order represented by a tree graph (a connected graph without cycles, and number of edges D n 1 – in-tree or out-tree) is the number of leaf nodes in that tree.
In scheduling theory, linear extensions of P can be viewed as 1-machine schedules that schedule the “jobs” from J , subject to the precedence constraints represented by P