A polynomial algorithm for some preemptive multiprocessor task scheduling problems

DOI10.1016/J.EJOR.2005.07.022MaRDI QIDQ2432888zbMATH OpenOpenAlexWikidataFDO

Authors Łukasz Kuszner, Michal Malafiejski

Publication date 25 October 2006

Published in European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ejor.2005.07.022

zbMATH Keywords

complexity theorydedicated processorsmultiprocessor tasksscheduling

Mathematics Subject Classification ID

Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Deterministic scheduling theory in operations research (90B35)

Recommendations

• Polynomial algorithms for resource-constrained and multiprocessor task scheduling problems
• Scheduling independent multiprocessor tasks
• Algorithms for preemptive scheduling of different classes of processors to do jobs with fixed times
• Preemptive multiprocessor task scheduling with release times and time windows
• scientific article; zbMATH DE number 2080263

Cites work

• Complexity of scheduling multiprocessor tasks with prespecified processors allocations
• Graph Classes: A Survey
• scientific article; zbMATH DE number 1929966 (Why is no real title available?)
• scientific article; zbMATH DE number 830382 (Why is no real title available?)
• Minimizing total completion time in two-processor task systems with prespecified processor allocations
• Optimal Linear Ordering
• Scheduling multiprocessor tasks for mean flow time criterion

Cited in

(11)

• A polynomial feasibility test for preemptive periodic scheduling of unrelated processors
• Polynomial algorithms for resource-constrained and multiprocessor task scheduling problems
• A fully polynomial approximation scheme for a scheduling problem with intree-type precedence delays
• Algorithms for preemptive scheduling of different classes of processors to do jobs with fixed times
• A polynomial algorithm for \(P | p_j = 1,r_j, outtree\,| \sum C_j\)
• Optimal preemptive scheduling in multiprocessor systems with incomplete communication graph
• A polynomial time approximation scheme for general multiprocessor job scheduling
• scientific article; zbMATH DE number 2080224 (Why is no real title available?)
• Logic versus Approximation
• Preemptive scheduling of interval orders is polynomial
• A projective algorithm for preemptive open shop scheduling with two multiprocessor groups

This page was built for publication: A polynomial algorithm for some preemptive multiprocessor task scheduling problems

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