Broadcast scheduling with multiple concurrent costs

Abstract

Data dissemination via periodic broadcasting considers a set of items, each with a given request probability, size and scheduling cost. The goal is to construct a broadcast schedule that minimizes the mean query serving time and the mean scheduling cost at the same time. This task has been proven to be NP-Hard, and related studies have gradually discarded the scheduling cost attribute in an effort to simplify the problem. The present study reinstates the cost attribute, as well as any number of additional cost attributes per data item. The proposed, MULTIOPT scheduling algorithm then achieves optimal mean serving time and mean values for all costs concurrently. Comparison with brute-force results and related approaches yield optimality in all tested cases. © 2012 IEEE.