Facets of the generalized permutahedron of a poset Original Research Article

Given a poset P as a precedence relation on a set of jobs with processing time vector p, the generalized permutahedron perm(P, p) of P is defined as the convex hull of all job completion time vectors corresponding to a linear extension of P. Thus, the generalized permutahedron allows 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 of the poset P, prove a dimension formula for perm(P, p), and characterize the facet inducing inequalities under the known classes of valid inequalities.