An Approximation Algorithm for Preemptive Scheduling on Parallel-Task Systems

DOI10.1137/S0895480191221829MaRDI QIDQ4863982zbMATHFDO

Authors Ramesh Krishnamurti, Bhagirath Narahari

Publication date 15 September 1996

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

parallel-task system

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Number-theoretic algorithms; complexity (11Y16)

Recommendations

• Approximation algorithms for general parallel task scheduling
• General Multiprocessor Task Scheduling: Approximate Solutions in Linear Time
• An approximation algorithm for nonpreemptive scheduling on hypercube parallel task systems
• scientific article; zbMATH DE number 2080263
• Scheduling independent multiprocessor tasks

Cited in

(16)

• Approximate Parallel Scheduling. Part I: The Basic Technique with Applications to Optimal Parallel List Ranking in Logarithmic Time
• Bounding the Power of Preemption in Randomized Scheduling
• scientific article; zbMATH DE number 2080870 (Why is no real title available?)
• scientific article; zbMATH DE number 3902030 (Why is no real title available?)
• Nearly on line scheduling of preemptive independent tasks
• scientific article; zbMATH DE number 2086932 (Why is no real title available?)
• Analysis of the list scheduling algorithm for precedence constrained parallel tasks
• An approximation algorithm for nonpreemptive scheduling on hypercube parallel task systems
• Preemptive Scheduling of a Multiprocessor System with Memories to Minimize Maximum Lateness
• Linear algorithms for preemptive scheduling of multiprocessor tasks subject to minimal lateness
• Computing optimal preemptive schedules for parallel tasks: linear programming approaches
• scientific article; zbMATH DE number 1759431 (Why is no real title available?)
• On the two-phase method for preemptive scheduling
• Preemptive scheduling on a small number of hierarchical machines
• On preemptive scheduling: A general setting for the two-phase method
• Improved approximation algorithms for non-preemptive multiprocessor scheduling with testing

This page was built for publication: An Approximation Algorithm for Preemptive Scheduling on Parallel-Task Systems

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