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

Wun-Tat Chan (), Francis Y. L. Chin (), Yong Zhang (), Hong Zhu (), Hong Shen () and Prudence W. H. Wong ()
Additional contact information
Wun-Tat Chan: University of Hong Kong
Francis Y. L. Chin: University of Hong Kong
Yong Zhang: University of Hong Kong
Hong Zhu: Fudan University
Hong Shen: Japan Advanced Institute of Science and Technology
Prudence W. H. Wong: University of Liverpool

Journal of Combinatorial Optimization, 2006, vol. 11, issue 2, No 5, 177-187

Abstract: 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

Keywords: Broadcast scheduling; flow time minimization; dynamic programming (search for similar items in EconPapers)
Date: 2006
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-006-7128-7 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:11:y:2006:i:2:d:10.1007_s10878-006-7128-7

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-006-7128-7

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().