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

Hu, 1961, Parallel sequencing and assembly line problems, Operations Research, 9, 841, 10.1287/opre.9.6.841 Garey, 1979 Ullman, 1975, NP-complete scheduling problems, Journal of Computer and System Science, 10, 384, 10.1016/S0022-0000(75)80008-0 Coffman, 1972, Optimal scheduling for two processor systems, Acta Informatica, 1, 200, 10.1007/BF00288685 Krishnamoorthy, 1996, Task scheduling with and without communication delays, European Journal of Operational Research, 89, 366, 10.1016/0377-2217(94)00255-X Varvarigou, 1996, Scheduling in and out forests in the presence of communication delays, IEEE Transactions Parallel and Distributed Systems, 7, 1065, 10.1109/71.539738 Djordjević, 1996, A compile-time scheduling heuristic for multiprocessor architectures, The Computer Journal, 39, 663, 10.1093/comjnl/39.8.663 Kwok, 1996, Dynamic critical path scheduling, IEEE Transactions on Parallel and Distributed Systems, 7, 506, 10.1109/71.503776 Manoharan, 1991, Assigning dependency graphs onto processor networks, Parallel Computing, 17, 63, 10.1016/S0167-8191(05)80018-3 Sarje, 1991, Heuristic model for task allocation in distributed computer systems, IEE Proceedings-E, 138, 313 Sih, 1993, A compile-time scheduling heuristic for interconnection-constrained heterogeneous processor architectures, IEEE Transactions on Parallel and Distributed Systems, 4, 175, 10.1109/71.207593 Blazewicz, 2000, Management of resources in parallel systems, 263 Pinedo, 2002 Coll PE, Ribeiro CC, de Sousa CC. Test instances for scheduling unrelated processors under precedence constraints. http://www-di.inf.puc-rio.br/∼celso/grupo/readme.ps; 2002. Kwok, 1999, Benchmarking and comparison of the task graph scheduling algorithms, Journal of Parallel and Distributed Computing, 59, 381, 10.1006/jpdc.1999.1578 Tobita, 2002, A standard task graph set for fair evaluation of multi-processor scheduling algorithms, Journal of Scheduling, 5, 379, 10.1002/jos.116 Hall, 2001, Generating experimental data for computational testing with machine scheduling applications, Operations Research, 49, 854, 10.1287/opre.49.6.854.10014 Davidović, 2000, Exhaustive list-scheduling heuristic for dense task graphs, YUJOR, 10, 123 Kwok, 1995, Bubble scheduling, 36 Kwok, 1997, Efficient scheduling of arbitrary task graphs to multiprocessors using a parallel genetic algorithm, Journal of Parallel and Distributed Computing, 47, 58, 10.1006/jpdc.1997.1395 Davidović, 2003, Mathematical programming formulation for the multiprocessor scheduling problem with communication delays, 331 Khan, 1994, A comparison of multiprocessor scheduling heuristics, 243 Chen, 1993, A note on lpt scheduling, Operations Research Letters, 14, 139, 10.1016/0167-6377(93)90024-B Malloy, 1994, Scheduling DAG's for asynchronous multiprocessor execution, IEEE Transactions Parallel and Distributed Systems, 5, 498, 10.1109/71.282560 Ahmad I, Kwok Y-K. Optimal and near-optimal allocation of precedence-constrained tasks to parallel processors: defying the high complexity using effective search technique. In: Proceedings of the 1998 international conference on parallel processing, 1998. p. 424–31. Davidović, 2001, Scheduling by VNS, 319 Davidović, 2001, Variable neighborhood search for multiprocessor scheduling problem with communication delays, 737 Davidović T, Crainic TG. New benchmarks for static task scheduling on homogeneous multiprocessor systems with communication delays. Publication CRT-2003-04, Centre de Recherche sur les Transports, Université de Montréal, 2003.