Institutional Repository [SANDBOX]
Technical University of Crete
EN  |  EL

Search

Browse

My Space

Resource scheduling for composite multimedia objects

Garofalakis Minos, Ioannidis, Yannis, 1930-, Ozden Banu

Full record


URI: http://purl.tuc.gr/dl/dias/70752150-26DA-43E0-A081-F8B3C4B5A116
Year 1998
Type of Item Conference Publication
License
Details
Bibliographic Citation M. N. Garofalakis, Y. E. Ioannidis and Banu Ozden, "Resource scheduling for composite multimedia objects", in 24th VLDB Conference, August 1998, pp. 74-85.
Appears in Collections

Summary

Scheduling algorithms for composite multimediapresentations need to ensure that the user-definedsynchronization constraints for the various presentationcomponents are met. This requirement givesrise to task models that are significantly more complexthan the models employed in scheduling theoryand practice. In this paper, we formulate the resourcescheduling problems for composite multimedia objectsand develop novel efficient scheduling algorithmsdrawing on a number of techniques from patternmatching and multiprocessor scheduling. Ourformulation is based on a novel sequence packingproblem, where the goal is to superimpose numericsequences (representing the objects’ resource needsas a function of time) within a fixed capacity bin(representing the server’s resource capacity). Giventhe intractability of the problem, we propose heuristicsolutions using a two-step approach. First, wepresent a “basic step” method for packing two compositeobject sequences into a single, combined sequence.Second, we show how this basic step can beemployed within different scheduling algorithms toobtain a playout schedule for multiple objects. Morespecifically, we present an algorithm based on Graham’slist-scheduling method that is provably nearoptimalfor monotonic object sequences. We alsosuggest a number of optimizations on the base listschedulingscheme. Preliminary experimental resultsconfirm the effectiveness of our approach.

Services

Statistics