Decomposition algorithm for the single machine scheduling polytope

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

1 Citation (Scopus)
62 Downloads (Pure)

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 languageUndefined
Title of host publicationCombinatorial Optimization, Third International Symposium, ISCO 2014
PublisherSpringer
Pages280-291
Number of pages12
ISBN (Print)978-3-319-09173-0
DOIs
Publication statusPublished - 5 Mar 2014

Publication series

NameLecture Notes in Computer Science
PublisherSpringer International Publishing
Volume8596
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