General Multiprocessor Task Scheduling: Approximate Solutions in Linear Time

DOI10.1137/S0097539799361737MaRDI QIDQ5470701zbMATH OpenOpenAlexFDO

Authors Lorant Porkolab, Klaus Jansen

Publication date 1 June 2006

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/s0097539799361737

zbMATH Keywords

approximation algorithmslinear programmingscheduling problem

Mathematics Subject Classification ID

Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25) Deterministic scheduling theory in operations research (90B35) Combinatorial optimization (90C27) Dynamic programming (90C39)

Recommendations

• scientific article; zbMATH DE number 2185607
• scientific article; zbMATH DE number 1979517
• Approximation algorithms for general parallel task scheduling
• A class of generalized multiprocessor scheduling problems
• A polynomial time approximation scheme for general multiprocessor job scheduling
• A parallel approximation scheme for the multiprocessor scheduling problem
• A polynomial time approximation scheme for general multiprocessor job scheduling (extended abstract)
• scientific article; zbMATH DE number 1305441
• Linear-Time approximation schemes for scheduling malleable parallel tasks
• Multiprocessor scheduling by generalized extremal optimization

Cited in

(30)

• A relation between multiprocessor scheduling and linear programming
• A two-pass scheduling algorithm for parallel programs
• Multiprocessor scheduling with machine allotment and parallelism constraints
• Real-time scheduling of linear speedup parallel tasks
• Scheduling multiple variant programs under hard real-time constraints
• Approximation algorithms for general parallel task scheduling
• Scheduling parallel tasks with sequential heads and tails
• Scheduling malleable parallel tasks: an asymptotic fully polynomial time approximation scheme
• Multiprocessor scheduling by reduction to uniprocessor: an original optimal approach
• A polynomial time approximation scheme for general multiprocessor job scheduling
• An approximation result for a duo-processor task scheduling problem
• scientific article; zbMATH DE number 2185607 (Why is no real title available?)
• Lower bound algorithms for multiprocessor task scheduling with ready times
• scientific article; zbMATH DE number 1271325 (Why is no real title available?)
• scientific article; zbMATH DE number 1979516 (Why is no real title available?)
• scientific article; zbMATH DE number 2080263 (Why is no real title available?)
• scientific article; zbMATH DE number 1759466 (Why is no real title available?)
• scientific article; zbMATH DE number 2174419 (Why is no real title available?)
• scientific article; zbMATH DE number 1929944 (Why is no real title available?)
• Polynomial time approximation schemes for general multiprocessor job shop scheduling
• scientific article; zbMATH DE number 2090587 (Why is no real title available?)
• scientific article; zbMATH DE number 2090589 (Why is no real title available?)
• An Approximation Algorithm for Preemptive Scheduling on Parallel-Task Systems
• Applying Cilk in Provably Efficient Task Scheduling
• Efficient construction of minimum makespan schedules for tasks with a fixed number of distinct execution times
• Scheduling independent multiprocessor tasks
• Linear algorithms for preemptive scheduling of multiprocessor tasks subject to minimal lateness
• Generalizing Horn's conditions for preemptive scheduling on identical parallel machines via network flow techniques
• Scheduling independent multiprocessor tasks
• A simple linear time approximation algorithm for multi-processor job scheduling on four processors

This page was built for publication: General Multiprocessor Task Scheduling: Approximate Solutions in Linear Time

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