Automated competitive analysis of real-time scheduling with graph games

DOI10.1007/S11241-017-9293-4MaRDI QIDQ1698779zbMATH OpenOpenAlexFDO

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

Publication date 16 February 2018

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

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

competitive analysisfirm-deadline tasksquantitative graph gamesreal-time scheduling

Mathematics Subject Classification ID

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

Recommendations

• Automated analysis of real-time scheduling using graph games
• On the competitiveness of on-line real-time task scheduling
• Synthesising succinct strategies in safety games with an application to real-time scheduling
• A 2.79 competitive on-line algorithm for two processor real-time systems with uniform value density
• IMPROVED COMPETITIVE ALGORITHMS FOR TWO-PROCESSOR REAL-TIME SYSTEMS

Cites work

• $\text{D}^{\textit{over}}$: An Optimal On-Line Scheduling Algorithm for Overloaded Uniprocessor Real-Time Systems
• A calculus for network delay. I. Network elements in isolation
• A characterization of the minimum cycle mean in a digraph
• A new algorithm for scheduling periodic, real-time tasks
• A new approach to online scheduling: approximating the optimal competitive ratio
• Algorithmic Game Theory
• Automated analysis of real-time scheduling using graph games
• Borel determinacy
• Competitive analysis of online real-time scheduling algorithms under hard energy constraint
• Considering suppressed packets improves buffer management in QoS switches
• Depth-First Search and Linear Graph Algorithms
• Faster algorithms for mean-payoff games
• Faster algorithms for quantitative verification in constant treewidth graphs
• scientific article; zbMATH DE number 3644821 (Why is no real title available?)
• scientific article; zbMATH DE number 3888913 (Why is no real title available?)
• scientific article; zbMATH DE number 1232130 (Why is no real title available?)
• On the competitiveness of on-line real-time task scheduling
• Online real-time preemptive scheduling of jobs with deadlines on multiple machines
• Positional strategies for mean payoff games
• Reducibility among combinatorial problems
• Resource reservation in dynamic real-time systems
• Scheduler modeling based on the controller synthesis paradigm
• Scheduling without payments
• Stochastic Games
• Succinct representations of graphs
• The complexity of mean payoff games on graphs
• The complexity of multi-mean-payoff and multi-energy games

Cited in

(3)

• An integrative approach with sequential game to real-time gate assignment under CDM mechanism
• Synthesising succinct strategies in safety games with an application to real-time scheduling
• Automated analysis of real-time scheduling using graph games

Describes a project that uses

Uses Software

• lp_solve
• lpSolve

This page was built for publication: Automated competitive analysis of real-time scheduling with graph games

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