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

directed acyclic graphshighest-level-first schedulingcritical path schedulinggraph algorithms, precedence constraints

Mathematics Subject Classification ID

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

Cited in

(24)

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

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)