Approximation Algorithms for Precedence-Constrained Scheduling Problems on Parallel Machines that Run at Different Speeds

DOI10.1006/jagm.1998.0987zbMath0923.68012OpenAlexW2607875432MaRDI QIDQ4238532

Publication date: 17 October 1999

Published in: Journal of Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/jagm.1998.0987

zbMATH Keywords

precedence-constrained jobs

Mathematics Subject Classification ID

Parallel algorithms in computer science (68W10) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Related Items (19)

Scheduling algorithms for procrastinators ⋮ Towards Tight Lower Bounds for Scheduling Problems ⋮ Optimal restricted due date assignment in scheduling ⋮ Scheduling on unrelated machines under tree-like precedence constraints ⋮ Approximation algorithms for multiprocessor scheduling under uncertainty ⋮ An improved monotone algorithm for scheduling related machines with precedence constraints ⋮ Scheduling of uniform parallel machines with s-precedence constraints ⋮ Speed scaling of tasks with precedence constraints ⋮ A monotone approximation algorithm for scheduling with precedence constraints ⋮ A study of scheduling problems with preemptions on multi-core computers with GPU accelerators ⋮ Approximation algorithms for scheduling problems with a modified total weighted tardiness objective ⋮ APPROXIMATION SCHEMES FOR SCHEDULING JOBS WITH CHAIN PRECEDENCE CONSTRAINTS ⋮ A General Scheme for Designing Monotone Algorithms for Scheduling Problems with Precedence Constraints ⋮ On the price of heterogeneity in parallel systems ⋮ Polynomial time approximation algorithms for machine scheduling: Ten open problems ⋮ An improved approximation algorithm for scheduling under arborescence precedence constraints ⋮ Non-Clairvoyant Precedence Constrained Scheduling. ⋮ Power-aware scheduling for makespan and flow ⋮ On-line scheduling with precedence constraints

This page was built for publication: Approximation Algorithms for Precedence-Constrained Scheduling Problems on Parallel Machines that Run at Different Speeds