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.
EnglishA set of tasks has to be scheduled on three processors and each task requires that a set of the processors be available for a given processing time. The objective of the problem is to determine a nonpreemptive schedule with minimum makespan. The problem is known to be NP-hard in the strong sense. A normal schedule is such that all tasks requiring the same set of processors are scheduled consecutively. We show that, under a certain (uniform) probability distribution on the problem instances, in more than 95% of the instances the best normal schedule is optimal when the number of tasks grows to infinity. For the hard cases it is shown that the relative error produced by the best normal schedule is bounded by 5/4. This result improves the bound of 4/3 known in the literature and the improved bound is shown to be tight.
Efficiency and Effectiveness of Normal Schedules on Three Dedicated Processors / Dell'Olmo, Paolo; Speranza, M. G.; Tuza, Zs. - In: DISCRETE MATHEMATICS. - ISSN 0012-365X. - STAMPA. - 164(1997), pp. 67-79.
Scheda prodotto non validato
Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo
| Titolo: | Efficiency and Effectiveness of Normal Schedules on Three Dedicated Processors |
| Autori: | |
| Data di pubblicazione: | 1997 |
| Rivista: | |
| Citazione: | Efficiency and Effectiveness of Normal Schedules on Three Dedicated Processors / Dell'Olmo, Paolo; Speranza, M. G.; Tuza, Zs. - In: DISCRETE MATHEMATICS. - ISSN 0012-365X. - STAMPA. - 164(1997), pp. 67-79. |
| Handle: | http://hdl.handle.net/11573/48625 |
| Appartiene alla tipologia: | 01a Articolo in rivista |
File allegati a questo prodotto
Copyright © 2020