






















With multiple identical unit speed servers, the online problem of scheduling jobs that migrate between two phases, limitedly parallelizable or completely sequential, and choosing their respective speeds to minimize the total flow time is considered. In the limited parallelizable regime, allocating $k$ servers to a job, the speed extracted is $k^{1/α}, α>1$, a sub-linear, concave speedup function, while in the sequential phase, a job can be processed by at most one server with a maximum speed of unity. A LCFS based algorithm is proposed for scheduling jobs which always assigns equal speed to the jobs that are in the same phase (limitedly parallelizable/sequential), and is shown to have a constant (dependent only on $α> 1$) competitive ratio. For the special case when all jobs are available beforehand, improved competitive ratio is obtained.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。