Online deadline scheduling with preemption penalties

This paper presents a study of the problem of online deadline scheduling under the preemption penalty model of Zheng, Xu, and Zhang (2007). In that model, each preemption incurs a penalty of ρ times the weight of the preempted job, where ρ ≥ 0 is the preemption penalty parameter. The objective is to maximise the total weight of jobs completed on time minus the total penalty. When the scheduler knows the ratio of longest to shortest job length, Δ, we show that the WAL algorithm of Zheng et al. (2007) is ((1 + ρ)Δ + o(Δ))-competitive for sufficiently large Δ. This improves the bound shown in Zheng et al. (2007). When the scheduler only knows that Δ ≥ (k(1 + ρ))³ for some k > 1, we propose a ((k(1 + ρ)Δ/(k - 1)) + o(Δ))-competitive algorithm. When ρ = 0, we give an optimal, O(Δ/log Δ)-competitive algorithm that, unlike previous algorithms, does not require knowledge of Δ. This settles an open problem mentioned in Ting (2008).