Worst Case Analysis of Two Scheduling Algorithms

DOI10.1137/0206037MaRDI QIDQ4152013zbMATH OpenOpenAlexDBLPWikidataFDO

Authors

Publication date 1977

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

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

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Deterministic scheduling theory in operations research (90B35) Algorithms in computer science (68W99)

Cited in

(19)

• Scheduling preemptive jobs with precedence constraints on parallel machines
• Precedence constrained scheduling in \((2-\frac{7}{3p+1})\) optimal
• Polynomial time approximation algorithms for machine scheduling: Ten open problems
• Approximation scheduling algorithms: a survey
• Scheduling loosely connected task graphs.
• Non-preemptive profile scheduling and quasi-interval orders
• An EPTAS for scheduling fork-join graphs with communication delay
• Online scheduling of equal-processing-time task systems
• Performance of Coffman-Graham schedules in the presence of unit communication delays
• A state-of-the-art review of parallel-machine scheduling research
• Coffman-Graham scheduling of UET task systems with 0-1 resources
• A (1+epsilon)-approximation for makespan scheduling with precedence constraints using LP hierarchies
• Quasi-PTAS for scheduling with precedences using LP hierarchies
• Optimal multiprocessor task scheduling using dominance and equivalence relations
• An iterative algorithm for scheduling UET tasks with due dates and release times.
• UET scheduling with unit interprocessor communication delays
• Multiprocessor scheduling with interprocessor communication delays
• PREEMPTIVE SCHEDULING ON PARALLEL PROCESSORS WITH DUE DATES
• Speeding-up parallel computation of large smooth-degree isogeny using precedence-constrained scheduling

This page was built for publication: Worst Case Analysis of Two Scheduling Algorithms

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