The permutahedron of series-parallel posets (Q5895282): Difference between revisions

For a finite partially ordered set the convex hull of the incidence vectors of some permutations of its elements is investigated. Only those permutations \(\pi\) are considered, which satisfy \(\pi (i)<\pi (j)\) for \(i<'j\). Here \(<\) is the standard ordering and \(<'\) is the actual partial ordering. Maximizing a linear functional on this convex hull is the solution of a job-scheduling problem: The finite set of jobs with individual processing times is partially ordered. A job can be processed only if all preceding jobs were done on the single machine. Minimize the completion time. The paper gives a characterization using linear inequalities of the convex hull, when the corresponding partially ordered set does not contain four elements a, b, c, d such that \(a>'c\), \(a>'d\), \(b>'d\), and the other pairs are incomparable. Without this assumption, such a characterization cannot be achieved.