|
|||||
|
|
The permutahedron ofN-sparse posets |
|
| Authors: | Annelie von Arnim Rainer Schrader Yaoguang Wang |
| Affiliation: | 1. Institut für Informatik, University of Cologne, D-50969, K?ln, Germany 2. Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ont., Canada |
| Abstract: | The permutahedron of a poset is the convex hull of all incidence vectors of linear extensions. For the case ofN-sparse posets in which any five elements induce at most oneN we give a characterization of the permutahedron in terms of linear inequalities. This yields an LP-solution for minimizing the weighted mean completion time for jobs with unit processing times andN-sparse precedence constraints. We close with an extension of our approach to arbitrary processing times. |
| Keywords: | Combinatorial optimization Polyhedra Weighted completion time scheduling Precedence constraints |
| 本文献已被 SpringerLink 等数据库收录！ | |