TY - GEN
T1 - On job scheduling with preemption penalties
AU - Zheng, Feifeng
AU - Xu, Yinfeng
AU - Poon, Chung Keung
PY - 2009
Y1 - 2009
N2 - This paper studies the problem of online job scheduling in a model with preemption penalty introduced by Zheng et al. [11]. In such a model with preemption penalty parameter ρ, the scheduler has to pay a penalty of ρ times the weight of each aborted job. We consider two cases according to the scheduler's knowledge of Δ (ratio of length between longest and shortest jobs). In the first case where the exact value of Δ is known at the beginning, we re-investigate the WAL algorithm of Zheng et al. and prove that it is ((1 + ρ)Δ + o(Δ))-competitive for sufficiently large Δ. In particular, when ρ= 1, the previous competitive ratio of 3Δ + o(Δ) proved in [11] is improved to 2Δ + o(Δ). In the second case where the online strategy only knows beforehand that Δ ≥ k 3(ρ + 1)3 for some parameter k > 1, a (k(1+p)/k-1Δ+o(Δ))-competitive deterministic strategy is presented. For large Δ, the competitive ratio approaches that of WAL as k increases. © 2009 Springer Berlin Heidelberg.
AB - This paper studies the problem of online job scheduling in a model with preemption penalty introduced by Zheng et al. [11]. In such a model with preemption penalty parameter ρ, the scheduler has to pay a penalty of ρ times the weight of each aborted job. We consider two cases according to the scheduler's knowledge of Δ (ratio of length between longest and shortest jobs). In the first case where the exact value of Δ is known at the beginning, we re-investigate the WAL algorithm of Zheng et al. and prove that it is ((1 + ρ)Δ + o(Δ))-competitive for sufficiently large Δ. In particular, when ρ= 1, the previous competitive ratio of 3Δ + o(Δ) proved in [11] is improved to 2Δ + o(Δ). In the second case where the online strategy only knows beforehand that Δ ≥ k 3(ρ + 1)3 for some parameter k > 1, a (k(1+p)/k-1Δ+o(Δ))-competitive deterministic strategy is presented. For large Δ, the competitive ratio approaches that of WAL as k increases. © 2009 Springer Berlin Heidelberg.
UR - https://www.scopus.com/pages/publications/70350637399
UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-70350637399&origin=recordpage
U2 - 10.1007/978-3-642-02158-9_27
DO - 10.1007/978-3-642-02158-9_27
M3 - RGC 32 - Refereed conference paper (with host publication)
SN - 3642021573
SN - 9783642021572
VL - 5564 LNCS
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 315
EP - 325
BT - Algorithmic Aspects in Information and Management
PB - Springer Verlag
T2 - 5th International Conference on Algorithmic Aspects in Information and Management, AAIM 2009
Y2 - 15 June 2009 through 17 June 2009
ER -