Sequence optimization for media objects with due date constraints in multimedia presentations from digital libraries

Feng Cheng Lin, Jen Shin Hong*, Miao-Tsong Lin

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

9 Scopus citations

Abstract

This study investigates sequence optimization of media objects in a multimedia presentation that is dynamically composed from digital libraries. Each media object can be associated with a due date. The aim is to schedule the media objects in a delay-prone network environment such that the overall presentation lag and the due date penalties of the media objects of presentations can be minimized. We formulate the sequencing problem with buffer constraints in the media player into a flowshop scheduling problem and present a reduction strategy with a branch and bound algorithm to derive optimal sequences. The algorithm can be applied in applications with up to a dozen objects to be scheduled. In addition, we propose a modified NEH-based heuristic algorithm which can provide approximate solutions with an average error rate of less than 4%. The computation-efficient heuristic, when deployed in applications with heavily loaded servers, can obtain near-optimal sequences for problems with more than a dozen objects. The proposed algorithms are embedded into a prototype system for providing digital library services.

Original languageEnglish
Pages (from-to)82-96
Number of pages15
JournalInformation Systems
Volume38
Issue number1
DOIs
StatePublished - Mar 2013

Keywords

  • Buffer constraint
  • Digital library
  • Due date constraint
  • Multimedia presentation scheduling
  • Presentation lag

Fingerprint Dive into the research topics of 'Sequence optimization for media objects with due date constraints in multimedia presentations from digital libraries'. Together they form a unique fingerprint.

Cite this