Algorithms for Scheduling Imprecise Computations with Timing Constraints

DOI10.1137/0220035zbMath0732.68023OpenAlexW1985907895MaRDI QIDQ3358218

Wei-Kuan Shih, Jen-Yao Chung, Jane W. S. Liu

Publication date: 1991

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0220035

zbMATH Keywords

deterministic schedulingreal-time systemscheduling to meet deadlines

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Related Items (17)

Minimizing the weighted number of tardy task units ⋮ Scheduling imprecise computation tasks on uniform processors ⋮ Approximation algorithms for scheduling real-time jobs with multiple feasible intervals ⋮ Scheduling imprecise computation tasks with \(0/1\)-constraint ⋮ Pre-emptive scheduling problems with controllable processing times ⋮ Open shop scheduling problems with late work criteria. ⋮ Machine Speed Scaling by Adapting Methods for Convex Optimization with Submodular Constraints ⋮ Fast Divide-and-Conquer Algorithms for Preemptive Scheduling Problems with Controllable Processing Times – A Polymatroid Optimization Approach ⋮ Preemptive scheduling on uniform parallel machines with controllable job processing times ⋮ Preemptive models of scheduling with controllable processing times and of scheduling with imprecise computation: a review of solution approaches ⋮ A DUAL CRITERIA PREEMPTIVE SCHEDULING PROBLEM FOR MINIMAX ERROR OF IMPRECISE COMPUTATION TASKS ⋮ IMPROVED COMPETITIVE ALGORITHMS FOR TWO-PROCESSOR REAL-TIME SYSTEMS ⋮ Scheduling two agents with controllable processing times ⋮ The two-machine flow-shop problem with weighted late work criterion and common due date ⋮ Application of Submodular Optimization to Single Machine Scheduling with Controllable Processing Times Subject to Release Dates and Deadlines ⋮ Real-time scheduling algorithm for minimizing maximum weighted error with \(O(N \log N+cN)\) complexity ⋮ Real-time task scheduling with fuzzy deadlines and processing times

This page was built for publication: Algorithms for Scheduling Imprecise Computations with Timing Constraints