On scheduling atomic and composite continuous media objects

In multiuser multimedia information systems (e.g., movie-on-demand, digital-editing), scheduling the retrievals of continuous media objects becomes a challenging task. This is because of both intra and inter lobject time dependencies. Intraobject time dependency refers to the real-time display requirement of a continuous media object. Interobject time dependency is the temporal relationships defined among multiple continuous media objects. In order to compose tailored multimedia presentations, a user might define complex time dependencies among multiple continuous media objects with various lengths and display bandwidths. Scheduling the retrieval tasks corresponding to the components of such a presentation in order to respect both inter and intra task time dependencies is the focus of this study. To tackle this task scheduling problem (CRS), we start with a simpler scheduling problem (ARS) where there is no inter task time dependency (e.g., movie-on-demand). Next, we investigate an augmented version of ARS (termed ARS⁺) where requests reserve displays in advance (e.g., reservation-based movie-on-demand). Finally, we extend our techniques proposed for ARS and ARS⁺ to address the CRS problem. We also provide formal definition of these scheduling problems and proof of their NP-hardness