$\text{D}^{\textit{over}}$: An Optimal On-Line Scheduling Algorithm for Overloaded Uniprocessor Real-Time Systems
From MaRDI portal
Publication:4834383
DOI10.1137/S0097539792236882zbMath0834.68037OpenAlexW1879402272MaRDI QIDQ4834383
Publication date: 18 March 1996
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/s0097539792236882
Analysis of algorithms and problem complexity (68Q25) Control/observation systems involving computers (process control, etc.) (93C83) Parallel algorithms in computer science (68W10) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Theory of operating systems (68N25)
Related Items (34)
MOCA: A multiprocessor on-line competitive algorithm for real-time system scheduling ⋮ Online scheduling with partial job values: does timesharing or randomization help? ⋮ Improved competitive algorithms for online scheduling with partial job values ⋮ Buffer Management for Packets with Processing Times ⋮ Online real-time preemptive scheduling of jobs with deadlines on multiple machines ⋮ Dynamic real-time scheduling of firm periodic tasks with hard and soft aperiodic tasks ⋮ A 2.79 competitive on-line algorithm for two processor real-time systems with uniform value density ⋮ Scheduling with deadlines and buffer management with processing requirements ⋮ Online time-constrained scheduling in linear and ring networks ⋮ Online scheduling with preemption or non-completion penalties ⋮ Online Throughput Maximization on Unrelated Machines: Commitment is No Burden ⋮ On-line scheduling with tight deadlines. ⋮ Preemptive scheduling in overloaded systems. ⋮ Automated competitive analysis of real-time scheduling with graph games ⋮ Breaking 1 - 1/e Barrier for Nonpreemptive Throughput Maximization ⋮ Preemptive scheduling of equal-length jobs to maximize weighted throughput. ⋮ On the Competitiveness of Online Real-Time Scheduling with Rate of Progress Guarantees ⋮ Optimally Handling Commitment Issues in Online Throughput Maximization ⋮ Improved randomized online scheduling of intervals and jobs ⋮ On the competitiveness of on-line real-time task scheduling ⋮ Energy efficient scheduling for real-time embedded systems with QoS guarantee ⋮ IMPROVED COMPETITIVE ALGORITHMS FOR TWO-PROCESSOR REAL-TIME SYSTEMS ⋮ Approximation algorithms for variable voltage processors: min energy, max throughput and online heuristics ⋮ Lower bounds on online deadline scheduling with preemption penalties ⋮ Dynamic scheduling for real‐time distributed systems using ant colony optimization ⋮ A tighter extra-resource analysis of online deadline scheduling ⋮ Improved Randomized Online Scheduling of Unit Length Intervals and Jobs ⋮ Competitive analysis of online real-time scheduling algorithms under hard energy constraint ⋮ ONLINE SCHEDULING OF UNIT JOBS WITH BOUNDED IMPORTANCE RATIO ⋮ A general framework for handling commitment in online throughput maximization ⋮ Online interval scheduling: Randomized and multiprocessor cases ⋮ Approximation Algorithms for Variable Voltage Processors: Min Energy, Max Throughput and Online Heuristics ⋮ A technique for adaptive scheduling of soft real-time tasks ⋮ Efficient job scheduling algorithms with multi-type contentions
This page was built for publication: $\text{D}^{\textit{over}}$: An Optimal On-Line Scheduling Algorithm for Overloaded Uniprocessor Real-Time Systems
