Minimize presentation lag by sequencing media objects for auto-assembled presentations from digital libraries

When delivering and presenting a multimedia document through a high-delay network, presentation lag is a major and critical factor affecting the service quality of the presentation. A dynamically generated multimedia document from a digital library often includes sets of both unconstrained objects and temporally-constrained objects. The order of the objects in a prefetch-enabled presentation environment has an impact on the overall presentation lag. This study explores techniques for optimizing the object sequence for an auto-assembled multimedia presentation to minimize the overall presentation lag. We adapt techniques developed in conventional two-machine flowshop research for computing or approximating the optimal sequences. We extensively discuss a variety of settings for commonly found applications with auto-assembled multimedia presentations. For each problem setting, the formulation and solutions were explored. We implemented a prototype system with which a number of problems have been evaluated. The numerical simulations and real-life experiments with 3G wireless networks show clearly that a computed optimal or near-optimal sequence significantly reduces the presentation lag as compared to random sequences.