In this talk we will consider a new general online scheduling problem where the goal is to minimize sum_j w_j g(F_j), where w_j is the weight/importance of job J_j, F_j is the flow time of the job in the schedule, and g is an arbitrary non-decreasing cost function. Numerous natural scheduling objectives are special cases of this general framework. We show that the scheduling algorithm Highest Density First (HDF) is (2+epsilon)-speed O(1)-competitive for all cost functions g simultaneously. We give lower bounds that show the HDF algorithm and this analysis are essentially optimal. Finally, we show scalable algorithms are achievable in some special cases.

This is joint work with Kirk Pruhs and Sungjin Im and appeared in SODA 2012.