On-Line Scheduling of Parallel Jobs with Runtime Restrictions
Consider the execution of a parallel application that dynamically
generates parallel jobs with specified resource requirements during
its execution. Generally, 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 a
variety of 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 have optimal competitive ratio up to
small additive constants, and are easy to implement.
