We consider a general online scheduling problem where the goal is to minimize ∑ⱼ wⱼ g(Fⱼ), where wⱼ is the weight/importance of job Jⱼ, Fⱼ is the flow time of the job in the schedule, and g is an arbitrary nondecreasing 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+ε)-speed $O(1)$-competitive for all cost functions g simultaneously. We give lower bounds that show that the HDF algorithm and this analysis are essentially optimal. Finally, we show that scalable algorithms are achievable in some special cases.
No takes yet. Share an insight, caveat, or question.
Im et al. (2014) studied this question.
Synapse has enriched 5 related papers. Consider them for comparative context: