A Comparison of Random Task Graph Generation Methods for Scheduling Problems

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