A dynamic programming approach of finding an optimal broadcast schedule in minimizing total flow time

Abstract

We study the problem of (off-line) broadcast scheduling in minimizing total flow time and propose a dynamic programming approach to compute an optimal broadcast schedule. Suppose the broadcast server has k pages and the last page request arrives at time n. The optimal schedule can be computed in O(k 3(n + k)k-1) time for the case that the server has a single broadcast channel. For m channels case, i.e., the server can broadcast m different pages at a time where m < k, the optimal schedule can be computed in O(nk-m) time when k and m are constants. Note that this broadcast scheduling problem is NP-hard when k is a variable and will take O(n k-m+1) time when k is fixed and m ≥ 1 with the straightforward implementation of the dynamic programming approach. © Springer Science + Business Media, LLC 2006.