FACETS OF THE GENERALIZED PERMUTAHEDRON OF A POSET

Given a poset P as a precedence relation on a set of jobs with process ing time vector p, the generalized permutahedron perm(P, p) of P is de fined as the convex hull of all job completion time vectors correspond ing to a linear extension of P. Thus, the generalized permutahedron al lows for the single machine weighted flowtime scheduling problem to be formulated as a linear programming problem over perm(P, p). Queyranne and Wang [8] as well as von Arnim and Schrader [2] gave a collection of valid inequalities for this polytope. Here we present a description of its geometric structure that depends on the series decomposition o f the poset P, prove a dimension formula for perm(P, p), and character ize the facet inducing inequalities under the known classes of valid i nequalities.