The generalized windows scheduling problem for $n$ jobs on
multiple machines is defined as follows: Given is a sequence,
$I=\ang{(w_1,\ell_1),(w_2,\ell_2),\ldots,(w_n,\ell_n)}$ of $n$
pairs of positive integers that are associated with the jobs
$1,2,\ldots,n$, respectively. The processing length of job $i$ is
$\ell_i$ slots (a slot is the processing time of one length unit).
The goal is to repeatedly and non-preemptively schedule all the
jobs on the fewest possible parallel machines such that the gap
(window) between two consecutive executions of the first slot of
job $i$ is at most $w_i$ slots. This problem arises in push
broadcast systems in which data is transmitted on parallel
channels.

The problem is NP-hard even for unit-length jobs and a
$(1+\varepsilon)$-approximation algorithm is known for this case
by approximating the natural lower bound $W(I)=\sum_{i=1}^n
(1/w_i)$. The techniques used for approximating unit-length jobs
cannot be applied for arbitrary-length jobs mainly because the
optimal number of machines might be arbitrarily larger than the
generalized lower bound $W(I)=\sum_{i=1}^n(\ell_i/w_i)$.

Our main result is an $8$-approximation algorithm for the
generalized windows scheduling problem using new methods,
different from those used for the unit-length case.

We also present an algorithm that uses $2(1+\eps)W(I)+\log
w_{max}$ machines and a greedy algorithm that is based on a new
tree representation of schedules. The greedy algorithm is optimal
for some special and simulations show that it performs very well
in practice.