Scheduling algorithms for the broadcast delivery of digital products

We provide scheduling algorithms that attempt to maximize the profits of a broadcast-based electronic delivery service for digital products purchased, for example, at e-commerce sites on the World Wide Web. Examples of such p roducts include multimedia objects such as CDs and DVDs. Other examples inc lude software and, with increasing popularity, electronic books as well. We consider two separate alternatives, depending in part on the sophisticatio n of the set-top box receiving the product at the customer end. The first, more restrictive option, assumes that the atomic unit of transmission of th e product is the entire object, which must be transmitted in order from sta rt to finish. We provide a solution based in part on a transportation probl em formulation for this so-called noncyclic scheduling problem. The second alternative, which is less restrictive, assumes that the product may be tra nsmitted cyclically in smaller segments, starting from an arbitrary point i n the object. Three heuristics are provided for this difficult cyclic sched uling problem. Both scenarios assume that the broadcasts of the same digita l product to multiple customers can be "batched." We examine the effectiven ess of these algorithms via simulation experiments under varying parametric assumptions. Each of the three cyclic scheduling algorithms perform better than the noncyclic algorithm. Moreover, one of the cyclic scheduling algor ithms emerges as the clear winner.