An Optimal Control Framework for Online Job Scheduling with General Cost Functions
论文为单机和多机环境下最小化广义完成时间的在线作业调度问题，设计了基于最优控制理论的在线算法，并给出了多个特例下最优的竞争比。
The paper “An Optimal Control Framework for Online Job Scheduling with General Cost Functions,” by Etesami devises online speed-augmented competitive algorithms for minimizing the generalized completion time on a single and multiple unrelated machines for a very general class of cost functions. To that end, a novel optimal control formulation for the offline version of the problem is developed. Such a formulation allows using tools from optimal control theory, such as the minimum principle and Hamilton-Jacobi-Bellman equation, to set the dual variables as close as possible to the optimal dual variables and leverage them to design primal-dual online algorithms as an iterative application of the offline problem. The analysis can achieve state-of-the-art competitive ratios for several special cases and provide new competitive ratios which are the first in their settings. In particular, the analysis offers a principled method of estimating dual variables in a general setting of online job scheduling.