Decomposition algorithm for the single machine scheduling polytope

Research output: Book/ReportReportProfessional

71 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\'eodory'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{\"o}tschel, Lov{\'a}sz, and Schrijver applied to one of these subpolytopes.
Original languageUndefined
Place of PublicationEnschede
PublisherCentre for Telematics and Information Technology (CTIT)
Number of pages14
Publication statusPublished - 4 Dec 2013

Publication series

NameCTIT Technical Report Series
PublisherUniversity of Twente, Centre for Telematics and Information Technology
No.TR-CTIT-13-25
ISSN (Print)1381-3625

Keywords

  • METIS-300180
  • IR-88292
  • EWI-24630
  • Polyhedral subdivision
  • Algorithms
  • Zonotopes
  • Scheduling polytope
  • Convex combination
  • Decomposition
  • Polyhedral theory

Cite this

Hoeksma, R. P., Manthey, B., & Uetz, M. J. (2013). Decomposition algorithm for the single machine scheduling polytope. (CTIT Technical Report Series; No. TR-CTIT-13-25). Enschede: Centre for Telematics and Information Technology (CTIT).