@inproceedings{464cf4ef08034af6bc1bb9574974e41a,
title = "On-line scheduling of parallel jobs with runtime restrictions",
abstract = "Consider the execution of a parallel application that dynamically generates parallel jobs with specified resource requirements during its execution. We assume that there is not sufficient knowledge about the running times and the number of jobs generated in order to precompute a schedule for such applications. Rather, the scheduling decisions have to be made on-line during runtime based on incomplete information. We present several on-line scheduling algorithms for various interconnection topologies that use some a priori information about the job running times or guarantee a good competitive ratio that depends on the runtime ratio of all generated jobs. All algorithms presented in this paper have optimal competitive ratio up to small additive constants.",
author = "Stefan Bischof and Mayr, {Ernst W.}",
year = "1998",
doi = "10.1007/3-540-49381-6_14",
language = "English",
isbn = "3540653856",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "119--129",
booktitle = "Algorithms and Computation - 9th International Symposium, ISAAC'98, Proceedings",
note = "9th Annual International Symposium on Algorithms and Computation, ISAAC'98 ; Conference date: 14-12-1998 Through 16-12-1998",
}