Scheduling for Weighted Flow Time and Energy with Rejection Penalty

Sze-Hang Chan, Tak-Wah Lam & Lap-Kei Lee
This paper revisits the online problem of flow-time scheduling on a single processor when jobs can be rejected at some penalty [Bansal et al. 2003]. The user cost of a job is defined as the weighted flow time of the job plus the penalty if it is rejected before completion. For jobs with arbitrary weights and arbitrary penalties, [Bansal et al. 2003] gave an online algorithm that is O((log W + log C)^2)-competitive for minimizing...