论文标题
安排多相的可行作业
Scheduling for Multi-Phase Parallelizable Jobs
论文作者
论文摘要
有了多个相同的单元速度服务器，安排在两个阶段之间迁移的在线工作问题，这些阶段有限，可行的或完全顺序的，并选择各自的速度以最大程度地减少总流动时间。在有限的可行性制度中，将$ k $服务器分配到工作中，提取的速度为$ k^{1/α}，α> 1 $，一个子线性的，凹点的加速功能，而在顺序阶段，作业最多可以由最大的统一速度来处理。提出了一种基于LCFS的算法，用于调度工作，该作业总是为在同一阶段（有限并行/顺序）的作业分配相等的速度，并且被证明具有常数（仅取决于$ $α> 1 $）的竞争比率。对于事先提供所有工作的特殊情况，可以获得改善的竞争比率。
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.
