Automated competitive analysis of real-time scheduling with graph games

DOI10.1007/s11241-017-9293-4zbMath1425.68044OpenAlexW2766431763MaRDI QIDQ1698779

Alexander Kößler, Krishnendu Chatterjee, Ulrich Schmid, Andreas Pavlogiannis

Publication date: 16 February 2018

Published in: Real-Time Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s11241-017-9293-4

zbMATH Keywords

competitive analysisreal-time schedulingfirm-deadline tasksquantitative graph games

Mathematics Subject Classification ID

Games involving graphs (91A43) Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Uses Software

• lp_solve
• lpSolve

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Polynomial-time algorithms for energy games with special weight structures
• Faster algorithms for mean-payoff games
• Feasibility analysis of sporadic real-time multiprocessor task systems
• Scheduler modeling based on the controller synthesis paradigm
• Resource reservation in dynamic real-time systems
• Competitive analysis of online real-time scheduling algorithms under hard energy constraint
• A new algorithm for scheduling periodic, real-time tasks
• Positional strategies for mean payoff games
• On the competitiveness of on-line real-time task scheduling
• Borel determinacy
• A characterization of the minimum cycle mean in a digraph
• Online real-time preemptive scheduling of jobs with deadlines on multiple machines
• The complexity of mean payoff games on graphs
• Faster algorithms for quantitative verification in constant treewidth graphs
• The complexity of multi-mean-payoff and multi-energy games
• Automated analysis of real-time scheduling using graph games
• Scheduling without Payments
• A calculus for network delay. I. Network elements in isolation
• Succinct representations of graphs
• $\text{D}^{\textit{over}}$: An Optimal On-Line Scheduling Algorithm for Overloaded Uniprocessor Real-Time Systems
• A New Approach to Online Scheduling
• Reducibility among Combinatorial Problems
• Algorithmic Game Theory
• Depth-First Search and Linear Graph Algorithms
• Stochastic Games