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 QW91a} as well as von Arnim
and Schrader AS} 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.
