Abstract
In this talk, I will describe some recent progress made on the problem of minimizing weighted flow-time in the online non-clairvoyant scheduling model, arguably the most general model of machine scheduling. In this problem, a set of jobs $J$ arrive over time to be scheduled on a set of $M$ machines. Each job $j$ has processing length $p_j$, weight $w_j$, and is processed at a rate of $\ell_{ij}$ when scheduled on machine $i$. The online scheduler knows the values of $w_j$ and $\ell_{ij}$ upon arrival of the job, but is not aware of the quantity $p_j$. We present the first online algorithm that achieves a constant competitive ration for the total weighted flow-time objective. The key algorithmic idea is to let jobs migrate selfishly until they converge to an equilibrium. Towards this end, we define a game where each job's utility which is closely tied to the instantaneous increase in the objective the job is responsible for, and each machine declares a policy that assigns priorities to jobs based on when they migrate to it, and the execution speeds. The selfish migrate framework has also found applications in designing online algorithms for various other scheduling problems, including energy efficient scheduling and multidimensional scheduling.