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

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.