Windows scheduling of arbitrary length jobs on parallel machines
Amotz Bar-Noy, Richard E. Ladner, Tami Tamir, Tammy VanDeGrift · 2005
The generalized windows scheduling problem for n jobs on multiple machines is defined as follows: Given is a sequence, I =\ang(w1, l1),(w2, l 2),...,(wn, ln) of n pairs of positive integers that are associated with the jobs 1,2,...,n, respectively. The processing length of job i is li 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 wi slots. This problem arises in push broadcast systems in which data is transmitted on parallel channels.