Lower bound algorithms for multiprocessor task scheduling with ready times |
| |
| Authors: | Massimiliano Caramia Paolo Dell'Olmo Antonio Iovanella |
| |
| Affiliation: | Istituto per le Applicazioni del Calcolo "M. Picone", Viale del Policlinico, 137-00161 Rome, Italy ; Dipartimento di Statistica, Probabilitàe Statistiche applicate, University of Rome "La Sapienza", Piazzale Aldo Moro, 5-00185 Rome, Italy ; Dipartimento di Informatica, Sistemi e Produzione, University of Rome "Tor Vergata", Via del Politecnico, 1-00133 Rome, Italy |
| |
| Abstract: | In this paper, we deal with multiprocessor task scheduling with ready times and prespecified processor allocation. We consider an on‐line scenario where tasks arrive over time, and, at any point in time, the scheduler only has knowledge of the released tasks. An application of this problem arises in wavelength division multiplexing broadcasting where the main future will be in the so‐called one‐to‐many transmission. We propose algorithms to find lower bounds of the minimum makespan, and present experiments on various scenarios. |
| |
| Keywords: | algorithm lower bound multiprocessor task scheduling |
|
|
