"Resource Scheduling for Composite Multimedia Objects"
by Minos N. Garofalakis, Yannis E. Ioannidis,
and Banu Özden.
Proceedings of VLDB'98,
New York City, USA, August 1998, pp. 74-85.
Scheduling algorithms for composite multimedia presentations need to
ensure that the user-defined synchronization constraints for the
various presentation components are met.
This requirement gives rise to task models that are significantly more
complex than the models employed in scheduling theory and practice.
In this paper, we formulate the resource scheduling problems for composite
multimedia objects and develop novel efficient scheduling algorithms drawing
on a number of techniques from pattern matching and multiprocessor scheduling.
Our formulation is based on a novel sequence packing problem, where the
goal is to superimpose numeric sequences (representing the objects' resource needs
as a function of time) within a fixed capacity bin (representing the server's
Given the intractability of the problem, we propose heuristic solutions using
a two-step approach.
First, we present a "basic step" method for packing two composite object sequences
into a single, combined sequence.
Second, we show how this basic step can be employed within different scheduling
algorithms to obtain a playout schedule for multiple objects.
More specifically, we present an algorithm based on Graham's list-scheduling
method that is provably near-optimal for monotonic object sequences.
We also suggest a number of optimizations on the base list-scheduling
Preliminary experimental results confirm the effectiveness of our
my talk slides
Copyright © 1998, VLDB Endowment.
Permission to copy without fee all or part of this material is granted provided
that the copies are not made or distributed for direct commercial advantage, the
VLDB copyright notice and the title of the publication and its date appear, and
notice is given that copying is by permission of the Very Large Data Base
Endowment. To copy otherwise, or to republish, requires a fee and/or special
permission from the Endowment.