An Almost-Linear Algorithm for Two-Processor Scheduling

DOI10.1145/322326.322335zbMath0485.68034OpenAlexW1996256520MaRDI QIDQ3945581

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)

Related Items (25)

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

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