Algorithms and complexity for periodic real-time scheduling

DOI10.1145/2390176.2390182MaRDI QIDQ2933634zbMATH OpenOpenAlexWikidataFDO

Authors Vincenzo Bonifaci, Ho-Leung Chan, Nicole Megow, Alberto Marchetti-Spaccamela

Publication date 5 December 2014

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL http://hdl.handle.net/11590/381331

zbMATH Keywords

approximation algorithmscomputational complexityerliest deadline firstfeasibility testinapproximabilityperiodic task systemreal-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) Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25) Deterministic scheduling theory in operations research (90B35)

Recommendations

• Algorithms and complexity for periodic real-time scheduling
• scientific article; zbMATH DE number 4215346
• Nonpreemptive scheduling of periodic tasks in uni- and multiprocessor systems
• A new algorithm for scheduling periodic, real-time tasks
• A constant-approximate feasibility test for multiprocessor real-time scheduling

Cited in

(25)

• Alternating real-time computations
• A new algorithm for scheduling periodic, real-time tasks
• The complexity of multidimensional periodic scheduling
• Efficient algorithms for periodic scheduling
• Nonpreemptive scheduling of periodic tasks in uni- and multiprocessor systems
• Multiprocessor schedulability of arbitrary-deadline sporadic tasks: complexity and antichain algorithm
• A constant-approximate feasibility test for multiprocessor real-time scheduling
• Assigning sporadic tasks to unrelated parallel machines
• Periodicity of real-time schedules for dependent periodic tasks on identical multiprocessor platforms
• Federated scheduling admits no constant speedup factors for constrained-deadline DAG task systems
• Algorithms for Scheduling Imprecise Computations with Timing Constraints
• scientific article; zbMATH DE number 4215346 (Why is no real title available?)
• A PTAS for Static Priority Real-Time Scheduling with Resource Augmentation
• A Constant-Approximate Feasibility Test for Multiprocessor Real-Time Scheduling
• Scheduling periodic tasks in a hard real-time environment
• scientific article; zbMATH DE number 749829 (Why is no real title available?)
• scientific article; zbMATH DE number 1830720 (Why is no real title available?)
• Packing sporadic real-time tasks on identical multiprocessor systems
• EDF-schedulability of synchronous periodic task systems is coNP-hard
• Algorithms and complexity for periodic real-time scheduling
• Combinatorial optimization in real-time scheduling: Theory and algorithms
• Utilization bound for periodic task set with composite deadline
• Feasibility problems for recurring tasks on one processor
• Optimal harmonic period assignment: complexity results and approximation algorithms
• Feasibility analysis of real-time periodic tasks with offsets

This page was built for publication: Algorithms and complexity for periodic real-time scheduling

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