The triangle scheduling problem

DOI10.1007/S10951-017-0533-1MaRDI QIDQ1617282zbMATH OpenOpenAlexFDO

Authors Christoph Dürr, Zdeněk Hanzálek, Christian Konrad, Yasmina Seddik, Gerhard J. Woeginger, René A. Sitters, Oscar C. Vásquez

Publication date 7 November 2018

Published in Journal of Scheduling (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1602.04365, https://research.vu.nl/ws/files/120343362/D_rr2018_TheTriangleSchedulingProblem.pdf

zbMATH Keywords

mixed-criticalityschedulingpacking

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Abstract: 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 (QPTAS). The approximation ratio of Greedy on general instances is shown to be between 1.5 and 1.05.

Recommendations

• Approximation algorithms for time constrained scheduling
• scientific article; zbMATH DE number 1182771
• Scheduling partially ordered jobs faster than \(2^{n }\)
• The geometry of scheduling
• A greedy approximation algorithm for minimum-gap scheduling

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A robust approach for the single machine scheduling problem
• An analysis of the non-preemptive mixed-criticality match-up scheduling problem
• Scheduling Real-Time Mixed-Criticality Jobs

Cited in

(1)

• Triangle width problem: at the intersection of graph theory, scheduling, and matrix visualization

This page was built for publication: The triangle scheduling problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1617282)