Institutional Repository
Technical University of Crete
Technical University of Crete
EN
|
EL
| URI: | http://purl.tuc.gr/dl/dias/70752150-26DA-43E0-A081-F8B3C4B5A116 | ||
| Year | 1998 | ||
| Type of Item | Conference Publication | ||
| License |
|
||
| 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 |
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.
Copyright © DIAS 2013
