The permutahedron of series-parallel posets

DOI10.1016/0166-218X(90)90089-UMaRDI QIDQ5895282zbMATH OpenOpenAlexFDO

Authors Annelie von Arnim, U. Faigle, Rainer Schrader

Publication date 1990

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0166-218x(90)90089-u

zbMATH Keywords

convex hullfinite partially ordered setincidence vectorsjob-schedulingpermutationssingle machine

Mathematics Subject Classification ID

Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Deterministic scheduling theory in operations research (90B35) Integer programming (90C10)

Review text

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.

Recommendations

• Facets of the generalized permutahedron of a poset
• The permutahedron of \(N\)-sparse posets
• The permutahedron of series-parallel posets
• On the facial structure of scheduling polyhedra
• Base polytopes of series-parallel posets: Linear description and optimization

Cites work

• Adjacent Vertices on a Permutohedron
• An Inequality
• Decomposition Algorithms for Single-Machine Sequencing with Precedence Relations and Deferral Costs
• scientific article; zbMATH DE number 3659595 (Why is no real title available?)
• Sequencing Jobs to Minimize Total Weighted Completion Time Subject to Precedence Constraints

Cited in

(13)

• N-free posets as generalizations of series-parallel posets
• Base polytopes of series-parallel posets: Linear description and optimization
• Oriented sets and even permutations: Asymmetry index series and \(q\)-series
• Series-parallel posets and relative Ockham lattices
• The setup polyhedron of series-parallel posets
• Enumeration of series-parallel posets according to heights
• A half-integral linear programming relaxation for scheduling precedence-constrained jobs on a single machine
• The permutahedron of \(N\)-sparse posets
• scientific article; zbMATH DE number 1015115 (Why is no real title available?)
• scientific article; zbMATH DE number 6928780 (Why is no real title available?)
• On the linear description of the Huffman trees polytope
• The permutahedron of series-parallel posets
• Facets of the generalized permutahedron of a poset

This page was built for publication: The permutahedron of series-parallel posets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5895282)