In this paper we analyze the worst-case performance of a greedy algorithm called Largest-Z-ratio-First for the problem of scheduling unreliable jobs on m parallel machines. Each job is characterized by a success probability and a reward earned in the case of success. In the case of failure, the jobs subsequently sequenced on that machine cannot be performed. The objective is to maximize the expected reward. We show the algorithm provides an approximation ratio of ≃0.853196, and that the bound is tight.
Agnetis, A., Lidbetter, T. (2020). The Largest-Z-ratio-First algorithm is 0.8531-approximate for scheduling unreliable jobs on m parallel machines. OPERATIONS RESEARCH LETTERS, 48(4), 405-409 [10.1016/j.orl.2020.05.006].
The Largest-Z-ratio-First algorithm is 0.8531-approximate for scheduling unreliable jobs on m parallel machines
Agnetis, A.;
2020-01-01
Abstract
In this paper we analyze the worst-case performance of a greedy algorithm called Largest-Z-ratio-First for the problem of scheduling unreliable jobs on m parallel machines. Each job is characterized by a success probability and a reward earned in the case of success. In the case of failure, the jobs subsequently sequenced on that machine cannot be performed. The objective is to maximize the expected reward. We show the algorithm provides an approximation ratio of ≃0.853196, and that the bound is tight.File | Dimensione | Formato | |
---|---|---|---|
List scheduling is 0.8531-approximate for scheduling unreliable jobs on m parallel machines.pdf
non disponibili
Tipologia:
PDF editoriale
Licenza:
NON PUBBLICO - Accesso privato/ristretto
Dimensione
252.71 kB
Formato
Adobe PDF
|
252.71 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
https://hdl.handle.net/11365/1124582