### Abstract

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\in C$, Carathéodory'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 \bigO{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 Grötschel, Lovász, and Schrijver applied to one of these subpolytopes.

Original language | Undefined |
---|---|

Title of host publication | Combinatorial Optimization, Third International Symposium, ISCO 2014 |

Publisher | Springer |

Pages | 280-291 |

Number of pages | 12 |

ISBN (Print) | 978-3-319-09173-0 |

DOIs | |

Publication status | Published - 5 Mar 2014 |

### Publication series

Name | Lecture Notes in Computer Science |
---|---|

Publisher | Springer International Publishing |

Volume | 8596 |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Keywords

- Polyhedral subdivision
- Polyhedral theory
- EWI-24927
- Decomposition
- METIS-305955
- Scheduling polytope
- Zonotopes
- IR-91477
- Algorithms
- Convex combination

## Cite this

Hoeksma, R. P., Manthey, B., & Uetz, M. J. (2014). Decomposition algorithm for the single machine scheduling polytope. In

*Combinatorial Optimization, Third International Symposium, ISCO 2014*(pp. 280-291). (Lecture Notes in Computer Science; Vol. 8596). Springer. https://doi.org/10.1007/978-3-319-09174-7_24