Benchmark-problem instances for static scheduling of task graphs with communication delays on homogeneous multiprocessor systems

DOI10.1016/J.COR.2005.01.005MaRDI QIDQ2489280zbMATH OpenOpenAlexFDO

Authors Tatjana Davidović, Teodor Gabriel Crainic

Publication date 16 May 2006

Published in Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.cor.2005.01.005

zbMATH Keywords

Task schedulingCommunication delaysBenchmark-problem instancesMultiprocessor systems

Mathematics Subject Classification ID

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

Recommendations

• A heuristic for scheduling task graphs with communication delays onto multiprocessors
• Lower bounds and efficient algorithms for multiprocessor scheduling of directed acyclic graphs with communication delays
• An approximation algorithm for scheduling dependent tasks on \(m\) processors with small communication delays
• Scheduling tasks with communication delays on parallel processors
• Optimal preemptive scheduling in multiprocessor systems with incomplete communication graph
• Task scheduling with and without communication delays: A unified approach
• Benchmarking and comparison of the task graph scheduling algorithms
• On the minimum number of processors for scheduling problems with communication delays

Cites work

• scientific article; zbMATH DE number 5345854 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 2047314 (Why is no real title available?)
• scientific article; zbMATH DE number 1458813 (Why is no real title available?)
• scientific article; zbMATH DE number 1512197 (Why is no real title available?)
• scientific article; zbMATH DE number 2099401 (Why is no real title available?)
• A note on LPT scheduling
• A standard task graph set for fair evaluation of multiprocessor scheduling algorithms
• Assigning dependency graphs onto processor networks
• Benchmarking and comparison of the task graph scheduling algorithms
• Generating Experimental Data for Computational Testing with Machine Scheduling Applications
• NP-complete scheduling problems
• Optimal scheduling for two-processor systems
• Task scheduling with and without communication delays: A unified approach

Cited in

(14)

• scientific article; zbMATH DE number 2099400 (Why is no real title available?)
• Parallelization strategies for bee colony optimization based on message passing communication protocol
• A comparison of random task graph generation methods for scheduling problems
• Benchmarking the clustering algorithms for multiprocessor environments using dynamic priority of modules
• A novel intelligent method for task scheduling in multiprocessor systems using genetic algorithm
• Improved mixed-integer programming models for the multiprocessor scheduling problem with communication delays
• Lower bounds and efficient algorithms for multiprocessor scheduling of directed acyclic graphs with communication delays
• Satisfiability modulo theory (SMT) formulation for optimal scheduling of task graphs with communication delay
• PERMUTATION-BASED GENETIC, TABU, AND VARIABLE NEIGHBORHOOD SEARCH HEURISTICS FOR MULTIPROCESSOR SCHEDULING WITH COMMUNICATION DELAYS
• MPI parallelization of variable neighborhood search
• Bee colony optimization for scheduling independent tasks to identical processors
• New MIP model for multiprocessor scheduling problem with communication delays
• A standard task graph set for fair evaluation of multiprocessor scheduling algorithms
• ECP: a novel clustering-based technique to schedule precedence constrained tasks on multiprocessor computing systems

This page was built for publication: Benchmark-problem instances for static scheduling of task graphs with communication delays on homogeneous multiprocessor systems

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