The triangle scheduling problem

Christoph Dürr*, Zdeněk Hanzálek, Christian Konrad, Yasmina Seddik, R.A. Sitters, Óscar C. Vásquez, Gerhard Woeginger

*Corresponding author for this work

Research output: Contribution to JournalArticleAcademicpeer-review

117 Downloads (Pure)


This paper introduces a novel scheduling problem, where jobs occupy a triangular shape on the time line. This problem is motivated by scheduling jobs with different criticality levels. A measure is introduced, namely the binary tree ratio. It is shown that the Greedy algorithm solves the problem to optimality when the binary tree ratio of the input instance is at most 2. We also show that the problem is unary NP-hard for instances with binary tree ratio strictly larger than 2 and provide a quasi-polynomial time approximation scheme. The approximation ratio of Greedy on general instances is shown to be between 1.5 and 1.05.

Original languageEnglish
Pages (from-to)305–312
Number of pages8
JournalJournal of Scheduling
Issue number3
Early online date18 May 2017
Publication statusPublished - Jun 2018


  • Mixed-criticality
  • Packing
  • Scheduling


Dive into the research topics of 'The triangle scheduling problem'. Together they form a unique fingerprint.

Cite this