An Almost-Linear Algorithm for Two-Processor Scheduling

DOI10.1145/322326.322335MaRDI QIDQ3945581zbMATH OpenOpenAlexFDO

Authors Harold N. Gabow

Publication date 1982

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/322326.322335

zbMATH Keywords

critical path schedulingdirected acyclic graphsgraph algorithms, precedence constraintshighest-level-first scheduling

Mathematics Subject Classification ID

Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Graph theory (including graph drawing) in computer science (68R10)

Cited in

(24)

• A linear-time algorithm for a special case of disjoint set union
• Applications of scheduling theory to formal language theory
• An inherently iterative computation of Ackermann's function
• Computing the bump number is easy
• Computing the bump number with techniques from two-processor scheduling
• A state-space search approach for parallel processor scheduling problems with arbitrary precedence relations
• Planar stage graphs: Characterizations and applications
• Minimizing the number of stations and station activation costs for a production line
• Scheduling unit-length jobs with precedence constraints of small height
• Normal-form preemption sequences for an open problem in scheduling theory
• Scheduling chains on uniform processors with communication delays
• An efficient deterministic parallel algorithm for two processors precedence constraint scheduling
• Non-preemptive profile scheduling and quasi-interval orders
• A note on scheduling multiprocessor tasks with precedence constraints on parallel processors
• Static scheduling of directed acyclic data flow graphs onto multiprocessors using particle swarm optimization
• Optimal scheduling of unit-time tasks on two uniform processors under tree-like precedence constraints
• Profile Scheduling of Opposing Forests and Level Orders
• Optimal shooting: Characterizations and applications
• Scheduling Opposing Forests
• ON OPTIMAL LOOP UNROLLING IN TWO-PROCESSOR SCHEDULING
• Parallel maximum matching algorithms in interval graphs
• An efficient parallel algorithm for scheduling interval ordered tasks
• An efficient algorithm for finding ideal schedules
• A state-of-the-art review of parallel-machine scheduling research

This page was built for publication: An Almost-Linear Algorithm for Two-Processor Scheduling

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