Algorithms for multiplex scheduling of object-based audio-visual presentations

Object-based representation of audio-visual (AV) presentations provides a flexible scheme to create interactive content that lends itself to resource-driven adaptation. The content adaptation needs of mobile devices can be met well with the use of object-based AV presentations. The main distinguishing feature of object-based AV presentations is the scene composition at the user terminal. In this paper, we discuss the problem of scheduling the delivery of object-based AV presentations under resource constraints. We explore the similarities with the problem of job sequencing on a single machine. We present a family of algorithms to determine the schedulability of AV presentations, and for unschedulable presentations, we present algorithms to compute a schedule that minimizes the additionally acquired resources. We present algorithms for computing incremental schedules for applications such as content authoring that require immediate feedback on resource consumption. The algorithms can be used to schedule object-based MPEG-4 presentations. We discuss the algorithms and results by considering a relatively complex MPEG-4 presentation with 16 objects, including audio, video, and images.