Optimal time-critical scheduling via resource augmentation
From MaRDI portal
Publication:5957573
DOI10.1007/s00453-001-0068-9zbMath0990.68022OpenAlexW204261080MaRDI QIDQ5957573
Cynthia A. Phillips, Joel M. Wein, Clifford Stein, Eric Torng
Publication date: 7 March 2002
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://digital.library.unt.edu/ark:/67531/metadc686106/
Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)
Related Items
The feasibility of general task systems with precedence constraints on multiprocessor platforms, Online machine minimization with lookahead, Serve or skip: the power of rejection in online bottleneck matching, An $\mathcal{O}(\log {m})$-Competitive Algorithm for Online Machine Minimization, A competitive algorithm for throughput maximization on identical machines, (\(1+\varepsilon \))-competitive algorithm for online OVSF code assignment with resource augmentation, The distributed wireless gathering problem, Online bin packing with resource augmentation, A constant-approximate feasibility test for multiprocessor real-time scheduling, A best possible online algorithm for minimizing the total completion time and the total soft penalty cost, Optimizing the stretch of independent tasks on a cluster: from sequential tasks to moldable tasks, Improved multi-processor scheduling for flow time and energy, {\textsc{DP-Fair}}: a unifying theory for optimal hard real-time multiprocessor scheduling, Online bottleneck matching, The online knapsack problem: advice and randomization, Single machine scheduling with job-dependent convex cost and arbitrary precedence constraints, A Constant-Approximate Feasibility Test for Multiprocessor Real-Time Scheduling, On the Complexity of Minimizing the Total Calibration Cost, Partition oriented frame based fair scheduler, On packet scheduling with adversarial jamming and speedup, Greedy multiprocessor server scheduling, Meeting Deadlines: How Much Speed Suffices?, Minimizing maximum (weighted) flow-time on related and unrelated machines, Bincoloring, Laxity dynamics and LLF schedulability analysis on multiprocessor platforms, On the competitiveness of AIMD-TCP within a general network, Schedulability analysis of global EDF, Non-migratory feasibility and migratory schedulability analysis of multiprocessor real-time systems, Resource augmented semi-online bounded space bin packing, Minimizing the maximum starting time on-line, Optimal on-line flow time with resource augmentation, Optimal online multiprocessor scheduling of sporadic real-time tasks is impossible, Unnamed Item, Handling Critical Jobs Online: Deadline Scheduling and Convex-Body Chasing, Improved multiprocessor global schedulability analysis, Competitive analysis of online real-time scheduling algorithms under hard energy constraint, Approximating \(k\)-forest with resource augmentation: a primal-dual approach, A modified modeling approach and a heuristic procedure for the multi-mode resource constrained project scheduling problem with activity splitting, Narrowing the speedup factor gap of partitioned EDF, Reallocation problems in scheduling, From Preemptive to Non-preemptive Scheduling Using Rejections, Approximate and robust bounded job start scheduling for Royal Mail delivery offices, Calibrations scheduling with arbitrary lengths and activation length, Non-clairvoyantly scheduling to minimize convex functions, Unnamed Item
Uses Software