An Optimal Control Framework for Online Job Scheduling with General Cost Functions

• 成果类型: Article; Early Access
• 署名作者: Etesami, S. Rasoul
• 署名单位: University of Illinois System; University of Illinois Urbana-Champaign; University of Illinois System; University of Illinois Urbana-Champaign
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2022.2321
• 发表日期: 2022
• 关键词: online job scheduling; generalized completion time; competitive ratio; speed augmentation; optimal control; network flow; linear programming duality

摘要

We consider the problem of online job scheduling on a single machine or multiple unrelated machines with general job and machine-dependent cost functions. In this model, each job has a processing requirement and arrives with a nonnegative nondecreasing cost function and this information is revealed to the system on arrival of that job. The goal is to dispatch the jobs to the machines in an online fashion and process them preemptively on the machines to minimize the generalized integral completion time. It is assumed that jobs cannot migrate between machines and that each machine has a fixed unit processing speed that can work on a single job at any time instance. In particular, we are interested in finding an online scheduling policy whose objective cost is competitive with respect to a slower optimal offline benchmark, that is, the one that knows all the job specifications a priori and is slower than the online algorithm. We first show that for the case of a single machine and special cost functions the highest-density-first rule is optimal for the generalized fractional completion time. We then extend this result by giving a speed-augmented competitive algorithm for the general nondecreasing cost functions by using a novel optimal control framework. This approach provides a principled method for identifying dual variables in different settings of online job scheduling with general cost functions. Using this method, we also provide a speed-augmented competitive algorithm for multiple unrelated machines with nondecreasing convex functions, where the competitive ratio depends on the curvature of the cost functions.