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.
Titolo: | The Largest-Z-ratio-First algorithm is 0.8531-approximate for scheduling unreliable jobs on m parallel machines |
Autori: | |
Rivista: | |
Citazione: | 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. |
Anno: | 2020 |
Appare nelle tipologie: | 1.1 Articolo in rivista |
File in questo prodotto:
File | Descrizione | Tipologia | Licenza | |
---|---|---|---|---|
List scheduling is 0.8531-approximate for scheduling unreliable jobs on m parallel machines.pdf | PDF editoriale | NON PUBBLICO - Accesso privato/ristretto | Administrator Richiedi una copia |
http://hdl.handle.net/11365/1124582