Article ID: | iaor2008181 |
Country: | United Kingdom |
Volume: | 7 |
Issue: | 3 |
Start Page Number: | 223 |
End Page Number: | 241 |
Publication Date: | May 2004 |
Journal: | Journal of Scheduling |
Authors: | Erlebach Thomas, Hall Alexander |
Keywords: | communications, networks: flow |
We consider the version of broadcast scheduling where a server can transmit W messages of a given set at each time-step, answering previously made requests for these messages. The goal is to minimize the average response time (ART) if the amount of requests is known in advance for each time-step and message. We prove that this problem is NP-hard, thus answering an open question stated by Kalyanasundaram