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

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

0.00 Avg rating0 Votes
Article ID: iaor2007400
Country: Netherlands
Volume: 11
Issue: 2
Start Page Number: 177
End Page Number: 187
Publication Date: Mar 2006
Journal: Journal of Combinatorial Optimization
Authors: , , , , ,
Keywords: timetabling, scheduling, combinatorial optimization
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(k3(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(nk-m+1) time when k is fixed and m = 1 with the straightforward implementation of the dynamic programming approach.

Reviews

Required fields are marked *. Your email address will not be published.