CINECA IRIS Institutional Research Information System
IRIS è la soluzione IT che facilita la raccolta e la gestione dei dati relativi alle attività e ai prodotti della ricerca. Fornisce a ricercatori, amministratori e valutatori gli strumenti per monitorare i risultati della ricerca, aumentarne la visibilità e allocare in modo efficace le risorse disponibili.
EnglishIn 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
Copyright © 2021