2009 | OriginalPaper | Buchkapitel
On Job Scheduling with Preemption Penalties
verfasst von : Feifeng Zheng, Yinfeng Xu, Chung Keung Poon
Erschienen in: Algorithmic Aspects in Information and Management
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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
$(\frac{k(1+\rho)}{k-1}\Delta+o(\Delta))$
-competitive deterministic strategy is presented. For large
Δ
, the competitive ratio approaches that of WAL as
k
increases.