A comparison of random task graph generation methods for scheduling problems

DOI10.1007/978-3-030-29400-7_5MaRDI QIDQ3297563zbMATH OpenOpenAlexFDO

Authors Louis-Claude Canon, Mohamad El Sayah, Pierre-Cyrille Héam

Publication date 20 July 2020

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1902.05808

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Abstract: How to generate instances with relevant properties and without bias remains an open problem of critical importance for a fair comparison of heuristics. In the context of scheduling with precedence constraints, the instance consists of a task graph that determines a partial order on task executions. To avoid selecting instances among a set populated mainly with trivial ones, we rely on properties that quantify the characteristics specific to difficult instances. Among numerous identified such properties, the mass measures how much a task graph can be decomposed into smaller ones. This property, together with an in-depth analysis of existing random task graph generation methods, establishes the sub-exponential generic time complexity of the studied problem. Empirical observations on the impact of existing generation methods on scheduling heuristics concludes our study.

Recommendations

• Benchmark-problem instances for static scheduling of task graphs with communication delays on homogeneous multiprocessor systems
• On the heterogeneity bias of cost matrices when assessing scheduling algorithms
• Generating Experimental Data for Computational Testing with Machine Scheduling Applications
• Benchmarking and comparison of the task graph scheduling algorithms
• Optimal parallel processing of random task graphs

Cites work

• scientific article; zbMATH DE number 3150484 (Why is no real title available?)
• scientific article; zbMATH DE number 2109192 (Why is no real title available?)
• scientific article; zbMATH DE number 3409391 (Why is no real title available?)
• A comparison of list schedules for parallel processing systems
• A machine assignment mechanism for compile-time list-scheduling heuristics
• A standard task graph set for fair evaluation of multiprocessor scheduling algorithms
• Heuristic Algorithms for Scheduling Independent Tasks on Nonidentical Processors
• Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
• NP-complete scheduling problems
• On the Number of Maximal Vertices of a Random Acyclic Digraph
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Random Generation of Directed Acyclic Graphs
• Random orders
• The Transitive Reduction of a Directed Graph
• `` Strong NP-Completeness Results

Cited in

(3)

• Asymptotic analysis and efficient random sampling of directed ordered acyclic graphs
• Ant colony algorithm for single processor scheduling with minimization of peak resource usage
• On the heterogeneity bias of cost matrices when assessing scheduling algorithms

Describes a project that uses

Uses Software

• TGFF

This page was built for publication: A comparison of random task graph generation methods for scheduling problems

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