Exploiting incomplete information to manage multiprocessor tasks with variable arrival rates

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.cor.2006.09.005 Byline: Paolo Dell'Olmo (a), Antonio Iovanella (b), Guglielmo Lulli (c), Benedetto Scoppola (d) Abstract: In this paper a semi-online algorithm for scheduling multiprocessor tasks with partial information is proposed. We consider the case in which it is possible to exploit probabilistic information and use this information to obtain better solutions in comparison with standard non clairvoyant on-line algorithms. A wide computational analysis shows the effectiveness of our algorithm. Moreover, we also consider a test framework with a continuous generation of tasks in order to study the behavior of the proposed approach in real applications, which confirms the efficiency of our approach. Author Affiliation: (a) Dipartimento di Statistica, Probabilita e Statistiche Applicate, Universita di Roma "La Sapienza", Piazzale Aldo Moro, 5 - 00185 Rome, Italy (b) Dipartimento di Ingegneria dell'Impresa, Universita di Roma "Tor Vergata", Via del Politecnico, 1 - 00133 Rome, Italy (c) Dipartimento di Informatica, Sistemistica e Comunicazione, Universita di Milano "Bicocca", Via Bicocca degli Arcimboldi, 8 - 20126 Milan, Italy (d) Dipartimento di Matematica, Universita di Roma "Tor Vergata", Via della Ricerca Scientifica - 00133 Rome, Italy