On the competitiveness of on-line real-time task scheduling

DOI10.1007/BF00365406zbMath0766.68011OpenAlexW3163474831MaRDI QIDQ1206445

S. Singh

Publication date: 1 April 1993

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

Full work available at URL: https://doi.org/10.1007/bf00365406

zbMATH Keywords

on-line schedulingclairvoyancycompetitive factorreal-time environments

Mathematics Subject Classification ID

Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Related Items (33)

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 ⋮ Online real-time preemptive scheduling of jobs with deadlines on multiple machines ⋮ A competitive algorithm for throughput maximization on identical machines ⋮ A 2.79 competitive on-line algorithm for two processor real-time systems with uniform value density ⋮ 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 ⋮ Scheduling multipacket frames with frame deadlines ⋮ Improved bounds for randomized preemptive online matching ⋮ Unnamed Item ⋮ On the Competitiveness of Online Real-Time Scheduling with Rate of Progress Guarantees ⋮ Optimally Handling Commitment Issues in Online Throughput Maximization ⋮ Random trees in queueing systems with deadlines ⋮ Online C-benevolent job scheduling on multiple machines ⋮ ON THE LOWER BOUND OF THE COMPETITIVE RATIO FOR THE WEIGHTED ONLINE ROOMMATES PROBLEM ⋮ Improved randomized online scheduling of intervals and jobs ⋮ Lower bounds on online deadline scheduling with preemption penalties ⋮ 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 ⋮ Variable sized online interval coloring with bandwidth ⋮ Randomized online interval scheduling ⋮ Online interval scheduling: Randomized and multiprocessor cases ⋮ Scheduling parallel tasks with individual deadlines ⋮ Approximating scheduling for multimedia applications under overload conditions ⋮ Competitive on-line scheduling of continuous-media streams ⋮ Online scheduling of jobs with fixed start times on related machines

Cites Work

• Convergence of discrete ordinates iteration scheme
• $\text{D}^{\textit{over}}$: An Optimal On-Line Scheduling Algorithm for Overloaded Uniprocessor Real-Time Systems
• Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment

This page was built for publication: On the competitiveness of on-line real-time task scheduling