A two-machine flowshop problem with processing time-dependent buffer constraints-An application in multimedia presentations

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

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

20 Scopus citations

Abstract

To have a quality multimedia presentation through networks, its presentation lag needs to be controlled. One way to reduce the lag is to prefetch the media objects before their due dates. This paper explores techniques for optimizing the object sequence in a prefetch-enabled TV-like presentation. An optimal solution is the one with which the presentation lag is minimized. We formulate the problem into a two-machine flowshop scheduling problem with a single chain precedence constraint and a player-side buffer constraint. The player-side buffer is "processing time-dependent" and distinguished from the conventional item-based intermediate buffer constraints discussed in previous flowshop studies. We prove the problem to be strongly NP-hard. A branch and bound algorithm equipped with four lower bounds and an NEH-based upper bound is developed. The simulation results show that the average gaps between the overall lower bounds and the NEH-based upper bound are less than 3% for problems with a large buffer size, and less than 13% for problems with a small buffer size and high density of precedence constraints. For applications where the media objects are delivered through extremely busy servers with which only very restricted CPU resources can be allocated for computation, the CDS-based algorithm provides better sequences than the NEH-based algorithm.

Original languageEnglish
Pages (from-to)1158-1175
Number of pages18
JournalComputers and Operations Research
Volume36
Issue number4
DOIs
StatePublished - Apr 2009

Keywords

  • Buffer constraint
  • Multimedia presentation
  • Object sequence optimization
  • Two-machine flowshop

Fingerprint Dive into the research topics of 'A two-machine flowshop problem with processing time-dependent buffer constraints-An application in multimedia presentations'. Together they form a unique fingerprint.

Cite this