Optimal online scheduling of parallel jobs with dependencies
Anja Feldmann, Ming‐Yang Kao, Jiřı́ Sgall, Shang‐Hua Teng · 1993
We study the following general online scheduling problem. Parallel jobs arrive dynamically according to the dependencies between them. Each job requests a certain number of processors with a specific communication configuration, but its running time is not known until it is completed. We present optimal online algorithms for PRAMs, hypercubes and one-dimensional meshes, and obtain optimal tradeoffs between the competitive ratio and the largest number of processors requested...