Minimizing the maximum flow time in batch scheduling

We consider the maximum flow time minimization problem in batch scheduling, which is a capacitated version of broadcast scheduling. In this setting, n different pages of information are available at the server which receives requests from clients over time for specific pages. The server can transmit at most one page p at each time to satisfy a batch of requests for the same page p, up to a certain capacity B-p. In this paper we give the first (1 + epsilon)-approximations for this problem with arbitrarily small resource augmentation, using either more capacity or more speed. (C) 2016 Elsevier B.V. All rights reserved.