Lower bound algorithms for multiprocessor task scheduling with ready times

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.