Given an n-vector p of processing times of jobs, the single machine scheduling polytope C arises as the convex hull of completion times of jobs when these are scheduled without idle time on a single machine. Given a point x ∈ C, Caratheodory's theorem implies that x can be written as convex combination of at most n vertices of C. We show that this convex combination can be computed from x and p in time O(n~2), which is linear in the naive encoding of the output. We obtain this result using essentially two ingredients. First, we build on the fact that the scheduling polytope is a zonotope. Therefore, all of its faces are centrally symmetric. Second, instead of C, we consider the polytope Q of half times and its barycentric subdivision. We show that the subpolytopes of this barycentric subdivison of Q have a simple, linear description. The final decomposition algorithm is in fact an implementation of an algorithm proposed by Grotschel, Lovasz, and Schrijver applied to one of these subpolytopes.
展开▼
