A Unifying Optimal Control Framework for Online Job Scheduling with General Cost Functions

S. Rasoul Etesami

We consider the problem of online job scheduling on a single or multiple unrelated machines with general heterogeneous cost functions. In this model, each job $j$ has a length $v_{ij}$ and arrives with a nonnegative nondecreasing cost function $g_{ij}(t)$, if it is dispatched to machine $i$, and this information is revealed to the system upon its arrival at time $r_j$. The goal is to dispatch the jobs to the machines and process them preemptively on the machines so as to minimize the generalized completion time $\sum_{j}g_{i(j)j}(C_j)$. Here $i(j)$ refers to the machine that job $j$ is dispatched to it and $C_j$ is the completion time of job $j$. It is assumed that jobs cannot migrate between machines and each machine has a unit processing speed which 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, i.e., the one which knows all the job specifications a priori. We first show that for the case of single machine and special cost functions $g_j(t)=w_jg(t)$, with nonnegative nondecreasing $g(t)$, the highest density first rule is optimal for the fractional generalized completion time. We then extend this result in the case of a single machine by giving a speed-augmented competitive algorithm for the general nondecreasing cost functions $g_j(t)$ using a novel optimal control formulation and network flow. Our approach provides a unifying and principled method of determining dual variables in various settings of online job scheduling which were done previously in an ad hoc manner or without giving much insight. Building upon this we also provide a speed-augmented competitive algorithm for multiple unrelated machines with nondecreasing convex functions $g_{ij}(t)$.

Knowledge Graph



Sign up or login to leave a comment