A New Algorithm for Preemptive Scheduling of Trees

DOI10.1145/322186.322194zbMath0446.68026OpenAlexW2001447488MaRDI QIDQ3891759

Donald B. Johnson, Teofilo F. Gonzalez

Publication date: 1980

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

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

zbMATH Keywords

preemptive scheduling of trees

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Related Items

A survey on how the structure of precedence constraints may change the complexity class of scheduling problems, A state-space search approach for parallel processor scheduling problems with arbitrary precedence relations, Towards Tight Lower Bounds for Scheduling Problems, Nearly on line scheduling of preemptive independent tasks, Scheduling parallel jobs to minimize the makespan, Open shop problems with unit time operations, Identical parallel machines vs. unit-time shops and preemptions vs. chains in scheduling complexity, Scheduling chained multiprocessor tasks onto large multiprocessor system, A state-of-the-art review of parallel-machine scheduling research, Optimal preemptive scheduling on a fixed number of identical parallel machines, b9000A 1/4 approximate algorithm for P2/tree/Cmax, Makespan minimization with OR-precedence constraints, A note on on-line scheduling with precedence constraints on identical machines